Modulo-snacks

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Modulo-snacks

Innlegg Aleks855 » 25/12-2017 03:40

Jeg ble tilsendt noen oppgaver av en student som trengte hjelp med å pusse opp litt på kongruens-regninga før eksamen som var nå i desember. Dessverre kom det på litt for kort varsel, akkurat idet jeg skulle reise på ferie, så jeg fikk ikke hjulpet til. Derimot ble jeg likevel sittende med oppgavene. Jeg synes slike oppgaver er morsomme, da de som regel krever en liten blanding av regneregel-rytting, og litt kreativitet. Så her er litt smågodt for de som føler for å prøve seg. Men jeg må innrømme at jeg hittil mangler løsning på enkelte av oppgavene.

1) Finn $158^{158} \mod 31$

2) Finn $25! \mod 78125$

3) Finn $21^{323} \mod 200$

4) Finn $5^{21!+20} \mod 529$

5) Finn $38! \mod 41$

6) Finn en invers til $55! \mod 61$

7) Finn $(2 \cdot 4 \cdot 6 \cdots 56) \mod 29$

Løs følgende likninger, eller vis at ingen løsning finnes:

8) $x^2 + 1 \equiv 0 \pmod{103}$

9) $x^2 + 1 \equiv 0 \pmod{29}$

10) $2x^2-44 \equiv 368y + 138z) \pmod{46}$

11) $143x \equiv 28 \pmod{67}$

12) $67x + 8 \equiv 3 \pmod {143}$
Bilde
Aleks855 online
Rasch
Rasch
Innlegg: 5894
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Modulo-snacks

Innlegg Markus » 25/12-2017 13:09

(5)
$38! \pmod{41}$
Når vi tar mod et primtall, og det har noe med fakultet å gjøre (og tallene er relativt nærme hverandre), så er som regel Wilsons teorem veien å gå. Teoremet sier at $(p-1)! \equiv -1 \pmod p$. Ved å dele på $p-1 \equiv -1 \pmod p$ på begge sider, oppnås delresultatet $(p-2)! \equiv 1 \pmod p$. Så vi har at
$ 39! \equiv 1 \pmod{41} \Longrightarrow 38! \equiv 39^{-1} \equiv 20 \pmod{41}$

(siden $39x \equiv 1 \pmod{41}$ gir den diofantiske likningen $39x - 41y = 1$ med de spesifikke løsningene $x_0 = 20$ og $y_0 = 19$ ved Euklids utvidede algortime.
Sist endret av Markus den 25/12-2017 13:43, endret 2 ganger.
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Modulo-snacks

Innlegg Gustav » 25/12-2017 13:39

$39^{-1}\equiv (-2)^{-1}\equiv -21\equiv 20\pmod {41}$

7) $\equiv 2^{28}\cdot 28!\equiv 1\cdot -1\equiv 28\pmod{29}$ ved Wilson og Fermat.
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4295
Registrert: 12/12-2008 12:44

Re: Modulo-snacks

Innlegg Markus » 25/12-2017 13:54

(2)
I $25!$ er $5$ faktor i $5,10,15,20,25$, slik at $5^6$ er en faktor i $25!$, og av aritmetikkens fundamentalteorem er vi garantert at det ikke er noen flere $5$-faktorer i $25!$. Det er ingen tilfeldighet at moden er så stor, $78125 = 5^7$. La $T$ være det produktet som er igjen etter at vi har tatt vekk $5^6$ som faktor fra $25!$. Da er

$25! \equiv 5^6 \cdot T \equiv 5^6 \equiv 15625 \pmod{5^7}$

(fordi $5^7 > 5^6$ er $5^6 \equiv 5^6 \pmod{5^7}$)
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Modulo-snacks

Innlegg Aleks855 » 25/12-2017 16:05

Markus skrev:(2)
I $25!$ er $5$ faktor i $5,10,15,20,25$, slik at $5^6$ er en faktor i $25!$, og av aritmetikkens fundamentalteorem er vi garantert at det ikke er noen flere $5$-faktorer i $25!$. Det er ingen tilfeldighet at moden er så stor, $78125 = 5^7$. La $T$ være det produktet som er igjen etter at vi har tatt vekk $5^6$ som faktor fra $25!$. Da er

$25! \equiv 5^6 \cdot T \equiv 5^6 \equiv 15625 \pmod{5^7}$

(fordi $5^7 > 5^6$ er $5^6 \equiv 5^6 \pmod{5^7}$)


Dette er en av oppgavene jeg stussa på. Jeg kom så langt som å innse at $25! = 5^6 \cdot T$, men jeg ser ikke hvordan vi kan avgjøre at $T \equiv 1 \mod 5^7$. Det virker som du har skjønt noe jeg ikke har, siden $T$'en din forsvant uten videre seremoni.
Bilde
Aleks855 online
Rasch
Rasch
Innlegg: 5894
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Modulo-snacks

Innlegg Markus » 25/12-2017 17:33

Dette er en av oppgavene jeg stussa på. Jeg kom så langt som å innse at $25! = 5^6 \cdot T$, men jeg ser ikke hvordan vi kan avgjøre at $T \equiv 1 \mod 5^7$. Det virker som du har skjønt noe jeg ikke har, siden $T$'en din forsvant uten videre seremoni.


Oisann, der har du helt rett. Jeg innså fort at mitt opprinnelige argument for at $T$ forsvinner er feil, og det er en amatørmessig feil som står bak. Det var det at $5^6 \equiv a \cdot 5^6 \pmod{ 5^7}$ (for et vilkårlig positivt heltall $a$, men dette stemmer jo åpenbart ikke. Mulig oppgaven må angripes på en annen måte, jeg skal i alle fall se litt mer på den senere.
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Modulo-snacks

Innlegg Markus » 26/12-2017 02:35

Denne metoden tror jeg skal holde vann.
Det viser seg at det er en regel i modulær aritmetikk som sier at hvis $an \equiv bn \pmod{N} \Longrightarrow a \equiv b \pmod{\frac{N}{\gcd(n,N)}}$

Definer $T$ som $\frac{25!}{5^6}$. La både $a$ og $b$ være lik $T$ og $n = 5^6$.

Da kan vi skrive $25! \equiv T \cdot 5^6 \pmod{5^6}$ som $T \equiv T \pmod{\frac{5^7}{5^6}}$, siden $\gcd(5^7,5^6) = 5^6$

Så vi har altså at $T \equiv T \pmod{5}$.

Det som nå er fint er at faktorene i $T$ har en fin syklus mod $5$. Dette fordi

$1 \equiv 1 \pmod 5$
$2 \equiv 2 \pmod 5$
$\vdots$
$4 \equiv 4 \pmod 5$
$6 \equiv 1 \pmod 5$
$7 \equiv 2 \pmod 5$
$\vdots$
$9 \equiv 4 \pmod 5$
$11 \equiv 1 \pmod 5$
Regner med at mønsteret forstås nå.

Siden at $5^6$ ikke er med i $T$, er det kun de andre faktorene til $5,10,15$ og $20$ vi står igjen med, altså $1,2,3,4$, som er det samme mod $ 5$.
Altså er $T \equiv (1 \cdot 2 \cdot 3 \cdot 4)^6 \equiv (4!)^6 \equiv 24^5 \equiv (4)^6 \equiv (-1)^6 \equiv 1 \pmod 5$

Bruker vi nå samme regel som den vi startet med, baklengs, oppnår vi det ønskede resultatet
$T \equiv 1 \pmod 5 \enspace \Longrightarrow \enspace T \equiv 1 \enspace \left (\text{mod } \frac{5^7}{\gcd(5^6, 5^7)}\right ) \enspace \Longrightarrow \enspace T \cdot 5^6 \equiv 1 \cdot 5^6 \pmod {5^7} \enspace \Longrightarrow \enspace 25! \equiv 5^6 \pmod{5^7}$
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Modulo-snacks

Innlegg Aleks855 » 26/12-2017 18:22

Utmerket!
Bilde
Aleks855 online
Rasch
Rasch
Innlegg: 5894
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Modulo-snacks

Innlegg Markus » 26/12-2017 23:09

(1) $158^{158} \pmod{31}$
Observerer at $158 \equiv 3 \pmod{31} \Longrightarrow 158^{158} \equiv 3^{158} \pmod{31}$

Legg merke til at $31$ er primtall, slik at vi kan bruke Fermats lille teorem: $a^p \equiv a \pmod p$.
$3^{31} \equiv 3 \pmod{31} \Longrightarrow 3^{30} \equiv 1 \pmod{31} \Longrightarrow 3^{150} \equiv 1^5 \equiv 1 \pmod{31}$

Så da vet vi at $158^{158} \equiv 3^{150} \cdot 3^8 \equiv 1 \cdot 3^8 \pmod{31}$, slik at det gjenstår å evaluere $3^8 \pmod{31}$

Vi har videre at
$3^4 \equiv 81 \equiv -12 \pmod{31} \Longrightarrow 3^8 \equiv (-12)^2 \equiv 144 \equiv -11 \equiv 20 \pmod{31}$

Og da oppnår vi det ønskede resultatet nemlig at
$3^{158} \equiv 20 \pmod{31} \Longrightarrow \boxed{158^{158} \equiv 20 \pmod{31}}$


(3) $21^{323} \pmod{200}$
Siden $\gcd(21,200) = 1$, gir Fermat-Euler $21^{\varphi(200)} \equiv 1 \pmod{200}$ og $\varphi(200) = 80$, så vi har at $21^{80} \equiv 1 \pmod{200}$

Som gir videre at
$(21^{80})^4 \equiv 21^{320} \equiv 1^4 \pmod{200}$

Og da gjenstår kun å evaluere $21^3 \pmod {200}$:
$21^2 = 441 \equiv 41 \pmod{200} \Longrightarrow 21^3 \equiv 41 \cdot 21 \equiv 861 \equiv 61 \pmod{200}$

Og da oppnår vi det ønskede resultatet, nemlig at
$21^{320} \cdot 21^3 \equiv 1 \cdot 61 \pmod{200} \Longrightarrow \boxed{21^{323} \equiv 61 \pmod{200}}$

Edit:
[tex]\varphi(200)[/tex] kan fint regnes ut uten tabell.
For [tex]n > 1[/tex], gitt primtallsfaktoseringen [tex]n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}[/tex], har vi generelt at [tex]\varphi(n) = n\left(1-\frac{1}{p_1} \right ) \left ( 1 - \frac{1}{p_2} \right ) \cdots \left(1 - \frac{1}{p_r} \right)[/tex].
Primtallsfaktorisering av [tex]200[/tex] gir [tex]200 = 2^3 \cdot 5^2[/tex], så [tex]\varphi(200) = 200 \cdot \frac{1}{2} \cdot \frac{4}{5} = \frac{400}{5} = 80[/tex]
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 4 gjester