Modulo-snacks

[Aleks855]

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}$

[Markus]

(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.

[Gustav]

$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.

[Markus]

(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}$)

[Aleks855]

(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.

[Markus]

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]

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}$

[Aleks855]

Utmerket!

[Markus]

(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]