Tilbake
2.1
Alle fag for Høyskole

2.1 Eulers ϕ-funksjon og Eulers teorem

ϕ(n) via faktorisering (ϕ(pᵏ)=pᵏ−pᵏ⁻¹ og multiplikativitet), Eulers teorem aᵠ⁽ⁿ⁾≡1 med gcd-betingelsen, og eksponentreduksjon for å regne aᴺ mod n — den hyppigste restberegningsteknikken i faget.

60 min
10 oppgaver
Eulers ϕ-funksjonEulers teorem
Din fremgang i kapitlet
0 / 10 oppgaver
Kapitlets plass i kurset

Forkunnskaper

Fra boka: kap. 1.1 (primtallsfaktorisering, relativt primiske tall), kap. 1.2 (Euklids algoritme — du trenger den for gcd⁡\gcd-sjekken) og kap. 1.4 (kongruens, regnereglene, modulær invers).

Sist du var her. De tre resultatene dette kapitlet står på, ferdig oppfrisket:

Kongruensregnereglene. Er a≡b(modm)a\equiv b\pmod m og c≡d(modm)c\equiv d\pmod m, så
a+c≡b+d,ac≡bd,ak≡bk(modm).a+c\equiv b+d,\qquad ac\equiv bd,\qquad a^k\equiv b^k\pmod m.
Potensregelen er den vi lever av her: du kan redusere grunntallet før du opphøyer.

Relativt primiske tall. gcd⁡(a,n)=1\gcd(a,n)=1 betyr at aa og nn ikke har noen primfaktor felles. Det er nøyaktig betingelsen for at aa har en invers modulo nn (kap. 1.4), og det blir vilkåret i Eulers teorem.

Å splitte modulusen. Når gcd⁡(m,n)=1\gcd(m,n)=1:
a≡b(modmn)  ⟺  a≡b(modm)  og  a≡b(modn).a\equiv b\pmod{mn}\iff a\equiv b\pmod m\ \text{ og }\ a\equiv b\pmod n.
Vi bruker den i siste løkke, der Eulers teorem ikke kan brukes direkte.

Fra videregående er ingenting påkrevd.

Et tall med 200 siffer, og fire timers eksamen

Oppgaven er: finn det siste sifferet i 720267^{2026}.

Tallet 720267^{2026} har over 1700 siffer. Kalkulatoren din gir opp lenge før den kommer dit, og du har ingen datamaskin. Likevel er dette en oppgave du skal kunne gjøre på under to minutter med penn og papir — og oppgaver av nøyaktig denne typen står i 14 av 15 eksamenssett.

Nøkkelen er at du ikke skal regne ut 720267^{2026}. Du skal finne resten når det deles på 1010, og rester gjentar seg. Sjekk selv: 717^1 ender på 77, 72=497^2=49 ender på 99, 73=3437^3=343 ender på 33, 74=24017^4=2401 ender på 11 — og så starter mønsteret på nytt. Fire steg, og du er tilbake til 11.

Hjulet gikk rundt. Det er hele idéen i kapitlet: for hver modulus nn finnes det et tall som forteller hvor mange steg hjulet bruker på en hel runde. Eulers teorem sier at ϕ(n)\phi(n) alltid er en slik rundetid — og ϕ(n)\phi(n) kan du regne ut fra faktoriseringen av nn uten å prøve deg frem. Da blir en eksponent på 2026 redusert til noe du kan regne i hodet.

Vi bygger det i tre trinn: først hva ϕ(n)\phi(n) er og hvordan du regner den ut, så Eulers teorem som sier hva den kan brukes til, og til slutt føringsmalen som gjør det til en oppgavebesvarelse sensor kan følge.

Tidsanslag for kapitlet: ~60 minutter lesetid, fordelt på seks løkker à 8–12 minutter. Regner du med penn underveis, som du bør, legg til omtrent halvparten.

Løkke 1: Hva ϕ(n)\phi(n) teller, og formelen for primtallspotenser

~10 minutter.

Vi begynner med definisjonen og den ene formelen som må sitte: verdien av ϕ\phi på en primtallspotens. Alt annet bygges av den.

Eulers ϕ-funksjon
For et positivt helt tall nn er ϕ(n)\phi(n) antallet tall i 1,2,…,n1,2,\dots,n som er relativt primiske til nn — altså antallet aa i det intervallet med gcd⁡(a,n)=1\gcd(a,n)=1.

Med symboler:
ϕ(n)=#{a:1≤a≤n, gcd⁡(a,n)=1}.\phi(n)=\#\{a: 1\le a\le n,\ \gcd(a,n)=1\}.

Funksjonen kalles Eulers ϕ\phi-funksjon (eller «Eulers totientfunksjon»), og skrives ϕ\phi — boka bruker den skrivemåten gjennomgående.

Tell den for hånd én gang, så sitter idéen. For n=12n=12 ser vi på 1,…,121,\dots,12: tallene 1,5,7,111,5,7,11 er relativt primiske til 1212, mens 2,3,4,6,8,9,10,122,3,4,6,8,9,10,12 deler en faktor med 1212. Altså ϕ(12)=4\phi(12)=4.

Merk grensene. Intervallet er 1≤a≤n1\le a\le n, og a=na=n teller bare når n=1n=1 (siden gcd⁡(n,n)=n\gcd(n,n)=n). Derfor er ϕ(1)=1\phi(1)=1.

Hva ϕ(n) teller — tre likeverdige beskrivelser

Samme tall, sett fra tre sider. Alle tre brukes i faget, og det lønner seg å kjenne dem igjen:

1. Antall tall ≤n\le n som er relativt primiske til nn. Dette er definisjonen, og den du teller med.
2. Antall restklasser modulo nn som har en invers. Fra kap. 1.4: aa har invers modulo nn nøyaktig når gcd⁡(a,n)=1\gcd(a,n)=1. Så ϕ(n)\phi(n) teller de inverterbare restklassene.
3. Størrelsen på et redusert restsystem modulo nn. Se kortet under.

Hvorfor beskrivelse 2 er verdt å ha: den forklarer hvorfor ϕ\phi dukker opp i RSA. Krypteringseksponenten ee må ha en invers modulo ϕ(n)\phi(n), og det er nettopp den inversen som er den private nøkkelen dd.

Og hvorfor beskrivelse 3 er verdt å ha: den er nøkkelen i beviset for Eulers teorem i løkke 3.

ϕ(p) for et primtall
For et primtall pp er
ϕ(p)=p−1.\phi(p)=p-1.

Grunnen er kort: et primtall har ingen andre divisorer enn 11 og seg selv, så hvert av tallene 1,2,…,p−11,2,\dots,p-1 er relativt primisk til pp. Bare pp selv faller ut. Det gir p−1p-1 tall.

Dette utledes på stedet — det er tilfellet k=1k=1 av formelen i neste kort, og det er én setning å begrunne.

Der du får bruk for det oftest: i RSA, der n=pqn=pq og ϕ(n)=(p−1)(q−1)\phi(n)=(p-1)(q-1), og i Fermats lille teorem, som er Eulers teorem med ϕ(p)=p−1\phi(p)=p-1 satt inn (kap. 2.2).

Eksempler: ϕ(7)=6\phi(7)=6, ϕ(13)=12\phi(13)=12, ϕ(83)=82\phi(83)=82, ϕ(101)=100\phi(101)=100.

ϕ(pᵏ) = pᵏ − pᵏ⁻¹
For et primtall pp og k≥1k\ge 1:
ϕ(pk)=pk−pk−1=pk−1(p−1).\phi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).

Utledningen er en tellemetode du bør kunne gjenskape. Hvilke tall i 1,…,pk1,\dots,p^k er ikke relativt primiske til pkp^k? Nøyaktig de som er delelige med pp — for pp er den eneste primfaktoren i pkp^k. Multiplene av pp i intervallet er
p, 2p, 3p, …, pk−1⋅p,p,\ 2p,\ 3p,\ \dots,\ p^{k-1}\cdot p,
altså pk−1p^{k-1} stykker. Trekker vi dem fra alle pkp^k tallene, står vi igjen med pk−pk−1p^k-p^{k-1}. ■\blacksquare

Formelen må sitte utenat. Den er den best belagte fellen i hele sjanger E: løsningsforslagene advarer mot å regne ϕ(pk)=pk−1\phi(p^k)=p^k-1, som er formelen for k=1k=1 brukt der k>1k>1.

Kontrollen som avslører feilen på fem sekunder: ϕ(9)\phi(9). Tallene 1,…,91,\dots,9 som er relativt primiske til 99, er 1,2,4,5,7,81,2,4,5,7,8 — seks stykker. Formelen gir 9−3=69-3=6 ✓. Den gale formelen ville gitt 88.

Eksempler: ϕ(27)=27−9=18\phi(27)=27-9=18, ϕ(49)=49−7=42\phi(49)=49-7=42, ϕ(32)=32−16=16\phi(32)=32-16=16, ϕ(125)=125−25=100\phi(125)=125-25=100.

✏️ϕ på primtallspotenser, og en telling som kontroll
a) Regn ut ϕ(27)\phi(27) og ϕ(49)\phi(49).
b) Kontroller ϕ(27)\phi(27) ved å telle direkte hvor mange av tallene 1,…,271,\dots,27 som er relativt primiske til 2727.
a) Begge tallene er primtallspotenser, så vi bruker ϕ(pk)=pk−pk−1\phi(p^k)=p^k-p^{k-1} — må sitte utenat:

ϕ(27)=ϕ(33)=33−32=27−9=18.\phi(27)=\phi(3^3)=3^3-3^2=27-9=18.
ϕ(49)=ϕ(72)=72−7=49−7=42.\phi(49)=\phi(7^2)=7^2-7=49-7=42.

b) Kontroll ved telling. De tallene i 1,…,271,\dots,27 som ikke er relativt primiske til 27=3327=3^3, er nøyaktig multiplene av 33:
3,6,9,12,15,18,21,24,27,3,6,9,12,15,18,21,24,27,
altså 99 stykker — som er 32=33−13^{2}=3^{3-1}, akkurat som utledningen sier. Da er det 27−9=1827-9=18 tall igjen, og ϕ(27)=18\phi(27)=18 ✓.

Sluttsvar: ϕ(27)=18\phi(27)=18 og ϕ(49)=42\phi(49)=42.

Legg merke til hva kontrollen viste: utledningen og formelen er samme sak. Skulle du glemme formelen på eksamen, kan du telle multiplene av pp og trekke fra — det tar tjue sekunder, og du får den riktige formelen tilbake.

📝Oppgave 1

Regn ut ϕ(13)\phi(13), ϕ(32)\phi(32) og ϕ(121)\phi(121).

Løkke 2: Multiplikativitet — ϕ\phi av et sammensatt tall

~11 minutter.

Nå har vi ϕ\phi på primtallspotenser. Sammensatte tall er produkter av primtallspotenser, og det viser seg at ϕ\phi oppfører seg pent mot slike produkter. Det er den egenskapen som gjør at du kan regne ϕ(360)\phi(360) i hodet.

— naturlig pausepunkt —

Multiplikativ funksjon
En tallteoretisk funksjon ff kalles multiplikativ dersom
f(mn)=f(m)f(n)for alle m,n med gcd⁡(m,n)=1.f(mn)=f(m)f(n)\qquad\text{for alle }m,n\text{ med }\gcd(m,n)=1.

Merk vilkåret. Kravet er ikke at det gjelder for alle par, bare for relativt primiske par. Det er derfor ϕ(2⋅4)≠ϕ(2)ϕ(4)\phi(2\cdot 4)\ne \phi(2)\phi(4): her er gcd⁡(2,4)=2≠1\gcd(2,4)=2\ne 1. (Sjekk: ϕ(8)=4\phi(8)=4, men ϕ(2)ϕ(4)=1⋅2=2\phi(2)\phi(4)=1\cdot 2=2.)

Hvorfor begrepet er verdt et eget kort: det gir en oppskrift som gjelder mange funksjoner samtidig. Faktoriser nn i primtallspotenser, regn funksjonen på hver potens, og gang sammen. Samme grep virker for ϕ\phi her, og for antall divisorer τ\tau og divisorsummen σ\sigma i Del 5.

En multiplikativ funksjon er altså fullstendig bestemt av verdiene sine på primtallspotenser.

ϕ er multiplikativ
For alle m,nm,n med gcd⁡(m,n)=1\gcd(m,n)=1:
ϕ(mn)=ϕ(m)ϕ(n).\phi(mn)=\phi(m)\phi(n).

Dette må sitte utenat, med vilkåret. Uten gcd⁡(m,n)=1\gcd(m,n)=1 er påstanden gal.

Intuisjon: et tall er relativt primisk til mnmn nøyaktig når det er relativt primisk til mm og til nn. Splittingsregelen fra kap. 1.4 sier at en restklasse modulo mnmn svarer til nøyaktig ett par av restklasser (én modulo mm, én modulo nn) når gcd⁡(m,n)=1\gcd(m,n)=1 — og da svarer de inverterbare klassene modulo mnmn til parene av inverterbare klasser. Antallet blir produktet. Den presise versjonen av dette argumentet er det kinesiske restteoremet i kap. 2.4.

Kontroll med små tall, som er verdt å gjøre én gang: ϕ(15)\phi(15). Direkte telling: 1,2,4,7,8,11,13,141,2,4,7,8,11,13,14 er relativt primiske til 1515 — åtte stykker. Og ϕ(3)ϕ(5)=2⋅4=8\phi(3)\phi(5)=2\cdot 4=8 ✓. Her er gcd⁡(3,5)=1\gcd(3,5)=1, så regelen gjelder.

Oppskrift: ϕ(n) fra faktoriseringen
Slik regner du ϕ(n)\phi(n) for hånd, hver gang. Dette er den prosedyren du skal bruke på eksamen.

1. Faktoriser nn i primtallspotenser: n=p1k1p2k2⋯prkrn=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}.
2. Regn ϕ\phi på hver potens med ϕ(pk)=pk−pk−1\phi(p^k)=p^k-p^{k-1}.
3. Gang sammen — lovlig fordi de ulike primtallspotensene er parvis relativt primiske, og ϕ\phi er multiplikativ.
4. Kontroller at svaret er mindre enn nn, og (for n≥3n\ge 3) at det er et partall.

Med symboler:
ϕ(n)=∏i=1r(piki−piki−1).\phi(n)=\prod_{i=1}^{r}\left(p_i^{k_i}-p_i^{k_i-1}\right).

Prosedyren må sitte utenat. Den er raskere for hånd enn den generelle brøkformelen i neste kort, fordi du aldri får brøker å holde orden på.

Faktoriseringen er det eneste virkelige arbeidet. Under kode D betyr det prøvedivisjon: del på 22, så 33, så 55, 77, 1111, 1313 … opp til n\sqrt n. Eksamensmodulene er valgt slik at dette går på et halvt minutt.

Den generelle ϕ-formelen
ϕ(n)=n∏p∣n(1−1p),\phi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),

der produktet går over de distinkte primtallene som deler nn (ikke over potensene).

Denne utledes på stedet, i to linjer. Skriv n=p1k1⋯prkrn=p_1^{k_1}\cdots p_r^{k_r}. For hver faktor er
piki−piki−1=piki(1−1pi),p_i^{k_i}-p_i^{k_i-1}=p_i^{k_i}\left(1-\frac{1}{p_i}\right),
og ganger vi de rr faktorene sammen, samler alle pikip_i^{k_i}-ene seg til nn:
ϕ(n)=∏ipiki(1−1pi)=n∏p∣n(1−1p).■\phi(n)=\prod_i p_i^{k_i}\left(1-\frac1{p_i}\right)=n\prod_{p\mid n}\left(1-\frac1p\right).\qquad\blacksquare

Under et minutt, og du trenger bare ϕ(pk)\phi(p^k) for å komme dit. Derfor står denne formelen i «utledes på stedet»-listen og ikke i utenat-listen.

Når den likevel er den raskeste: når nn har mange små primfaktorer og brøkene forkorter pent. For n=360=23⋅32⋅5n=360=2^3\cdot 3^2\cdot 5:
ϕ(360)=360⋅12⋅23⋅45=96.\phi(360)=360\cdot\frac12\cdot\frac23\cdot\frac45=96.
Fellen i den: produktet går over distinkte primtall. Skriver du en faktor (1−12)\displaystyle \left(1-\frac12\right) tre ganger fordi 232^3 står i faktoriseringen, blir svaret galt.

✏️ϕ(360) på to måter, og ϕ(1000)
a) Regn ut ϕ(360)\phi(360) fra faktoriseringen.
b) Regn ut ϕ(360)\phi(360) på nytt med den generelle formelen, og sammenlign.
c) Regn ut ϕ(1000)\phi(1000).
a) Vi faktoriserer og bruker oppskriften.

360=23⋅32⋅5.360=2^3\cdot 3^2\cdot 5.

ϕ\phi på hver potens, med ϕ(pk)=pk−pk−1\phi(p^k)=p^k-p^{k-1}:
ϕ(23)=8−4=4,ϕ(32)=9−3=6,ϕ(5)=4.\phi(2^3)=8-4=4,\qquad \phi(3^2)=9-3=6,\qquad \phi(5)=4.

De tre primtallspotensene er parvis relativt primiske, så multiplikativiteten gir
ϕ(360)=4⋅6⋅4=96.\phi(360)=4\cdot 6\cdot 4=96.

b) Med den generelle formelen, som utledes på stedet: de distinkte primfaktorene er 2,3,52,3,5, så
ϕ(360)=360(1−12)(1−13)(1−15)=360⋅12⋅23⋅45.\phi(360)=360\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)=360\cdot\frac12\cdot\frac23\cdot\frac45.
Vi regner stegvis: 360⋅12=180\displaystyle 360\cdot\frac12=180, 180⋅23=120\displaystyle 180\cdot\frac23=120, 120⋅45=96\displaystyle 120\cdot\frac45=96. Samme svar ✓.

c) 1000=23⋅531000=2^3\cdot 5^3, så
ϕ(1000)=(8−4)(125−25)=4⋅100=400.\phi(1000)=(8-4)(125-25)=4\cdot 100=400.

Kontroll. Alle tre svarene er mindre enn tallet og er partall, som de skal være. Og ϕ(1000)=400\phi(1000)=400 stemmer med den generelle formelen: 1000⋅12⋅45=400\displaystyle 1000\cdot\frac12\cdot\frac45=400 ✓.

Sluttsvar: ϕ(360)=96\phi(360)=96 og ϕ(1000)=400\phi(1000)=400.

Hvilken vei er raskest? For hånd er faktoriseringsveien i a) tryggest, fordi du aldri får brøker. Brøkformelen er raskest når tallet er rundt og brøkene forkorter — som i c). Begge er fullgode, og fasitene i arkivet honorerer dem likt.

📝Oppgave 2

Regn ut ϕ(84)\phi(84) og ϕ(200)\phi(200) fra faktoriseringene.

📝Oppgave 3
a) Regn ut ϕ(675)\phi(675).
b) Finn alle nn med ϕ(n)=n−1\phi(n)=n-1, og begrunn svaret.

Løkke 3: Eulers teorem

~10 minutter.

Nå kommer resultatet som gjør ϕ\phi til et regneverktøy. Det sier at ϕ(n)\phi(n) er en «rundetid»: opphøyer du et tall som er relativt primisk til nn i ϕ(n)\phi(n), kommer du tilbake til 11.

📜Eulers teorem
For alle hele tall aa og n≥1n\ge 1 med gcd⁡(a,n)=1\gcd(a,n)=1:
aϕ(n)≡1(modn).a^{\phi(n)}\equiv 1\pmod n.

Vilkåret gcd⁡(a,n)=1\gcd(a,n)=1 er en del av teoremet. Uten det er påstanden gal, og feilen er dokumentert som en av de vanligste i faget: gcd⁡(6,9)=3\gcd(6,9)=3, og 6ϕ(9)=666^{\phi(9)}=6^6 er ikke ≡1(mod9)\equiv 1\pmod 9 — det er ≡0(mod9)\equiv 0\pmod 9, siden 666^6 er delelig med 363^6.

Bevis. La r1,r2,…,rϕ(n)r_1,r_2,\dots,r_{\phi(n)} være et redusert restsystem modulo nn — altså de ϕ(n)\phi(n) tallene i 1,…,n1,\dots,n som er relativt primiske til nn.

Steg 1: multiplikasjon med aa stokker om systemet. Betrakt tallene
ar1, ar2, …, arϕ(n).ar_1,\ ar_2,\ \dots,\ ar_{\phi(n)}.
Hvert av dem er relativt primisk til nn: både aa og rir_i er det, og et produkt av to tall uten felles primfaktor med nn har heller ingen. Og de er parvis inkongruente: er ari≡arj(modn)ar_i\equiv ar_j\pmod n, kan vi forkorte med aa (lovlig, etter forkortingsregelen i kap. 1.4, siden gcd⁡(a,n)=1\gcd(a,n)=1) og få ri≡rjr_i\equiv r_j, altså i=ji=j.

Dermed er ar1,…,arϕ(n)ar_1,\dots,ar_{\phi(n)} nøyaktig de samme ϕ(n)\phi(n) restklassene som r1,…,rϕ(n)r_1,\dots,r_{\phi(n)}, bare i en annen rekkefølge.

Steg 2: gang alt sammen. Produktet av de to listene er derfor kongruent modulo nn:
(ar1)(ar2)⋯(arϕ(n))≡r1r2⋯rϕ(n)(modn).(ar_1)(ar_2)\cdots(ar_{\phi(n)})\equiv r_1r_2\cdots r_{\phi(n)}\pmod n.
Venstresiden er aϕ(n)⋅r1r2⋯rϕ(n)a^{\phi(n)}\cdot r_1r_2\cdots r_{\phi(n)}. Sett R=r1r2⋯rϕ(n)R=r_1r_2\cdots r_{\phi(n)}; da er
aϕ(n)R≡R(modn).a^{\phi(n)}R\equiv R\pmod n.

Steg 3: forkort med RR. Hver rir_i er relativt primisk til nn, så gcd⁡(R,n)=1\gcd(R,n)=1, og forkorting er lovlig. Det gir
aϕ(n)≡1(modn).■a^{\phi(n)}\equiv 1\pmod n.\qquad\blacksquare

Intuisjon: å gange med aa er å stokke om en kortstokk med ϕ(n)\phi(n) kort. Gjør du det ϕ(n)\phi(n) ganger og ganger alle kortene sammen, må du ende der du startet — og det tvinger aϕ(n)a^{\phi(n)} til å være 11.

Teoremet må sitte utenat, og det må navngis. Fasitene skriver «fra Eulers teorem» der reduksjonen gjøres, og det er teoremnavnet som bærer argumentet.

Vilkåret i Eulers teorem — og hva du gjør uten det

Eulers teorem krever gcd⁡(a,n)=1\gcd(a,n)=1. Det er ikke en teknikalitet, det er hele forutsetningen — og det er den mest belagte fellen i sjanger E.

Sjekken skal stå i besvarelsen, som én setning: «Siden gcd⁡(a,n)=1\gcd(a,n)=1, gir Eulers teorem …». Fasitene i arkivet skriver den ut, og en besvarelse som reduserer eksponenten uten å ha sagt det, har hoppet over premisset.

Hvordan du sjekker den raskt: du har allerede faktorisert nn (steg 1 i oppskriften). Se om noen av primfaktorene i nn deler aa. Er n=100n=100 og a=3a=3, er primfaktorene 22 og 55, og ingen av dem deler 33 — ferdig.

Er gcd⁡(a,n)≠1\gcd(a,n)\ne 1? Da kan du ikke bruke Euler på nn. Det er ikke en blindvei, men en annen vei: splitt modulusen i primtallspotenser og behandle hver del for seg. Det er løkke 6.

Merk en presisering det er verdt å ha: vilkåret gjelder aa og nn, ikke aa og eksponenten. Eksponenten kan være hva som helst.

Redusert restsystem modulo n

En liste med ϕ(n)\phi(n) tall som er parvis inkongruente modulo nn og alle relativt primiske til nn — altså én representant for hver inverterbar restklasse.

Det naturlige valget er tallene i 1,…,n1,\dots,n som er relativt primiske til nn. For n=12n=12: {1,5,7,11}\{1,5,7,11\}. For n=10n=10: {1,3,7,9}\{1,3,7,9\}.

Egenskapen som brukes i beviset for Eulers teorem: ganger du hele systemet med et tall aa som er relativt primisk til nn, får du samme system om igjen, bare i en annen rekkefølge. Prøv med n=10n=10 og a=3a=3: 3⋅{1,3,7,9}={3,9,21,27}≡{3,9,1,7}3\cdot\{1,3,7,9\}=\{3,9,21,27\}\equiv\{3,9,1,7\} — samme fire restklasser ✓.

Hvorfor det er verdt å kjenne begrepet: det er nøyaktig samme omstokkings-idé som brukes i beviset for Wilsons teorem (kap. 2.3), der faktorene parer seg med sine inverser. To av fagets fire store teoremer hviler på den.

✏️Eulers teorem kontrollert på to moduler
a) Verifiser Eulers teorem for a=3a=3, n=10n=10 ved direkte regning.
b) Verifiser den for a=2a=2, n=9n=9.
c) Hva skjer med a=6a=6, n=9n=9?
a) 10=2⋅510=2\cdot 5, så ϕ(10)=1⋅4=4\phi(10)=1\cdot 4=4. Og gcd⁡(3,10)=1\gcd(3,10)=1 ✓, så Eulers teorem sier 34≡1(mod10)3^4\equiv 1\pmod{10}.

Direkte: 34=81=10⋅8+13^4=81=10\cdot 8+1, altså 34≡1(mod10)3^4\equiv 1\pmod{10} ✓.

b) 9=329=3^2, så ϕ(9)=9−3=6\phi(9)=9-3=6. Og gcd⁡(2,9)=1\gcd(2,9)=1 ✓, så teoremet sier 26≡1(mod9)2^6\equiv 1\pmod 9.

Direkte: 26=64=9⋅7+12^6=64=9\cdot 7+1, altså 26≡1(mod9)2^6\equiv 1\pmod 9 ✓.

c) Her er gcd⁡(6,9)=3≠1\gcd(6,9)=3\ne 1, så vilkåret svikter og teoremet gjelder ikke. Vi ser hva som faktisk skjer:
62=36≡0(mod9),6^2=36\equiv 0\pmod 9,
og da er 6k≡0(mod9)6^k\equiv 0\pmod 9 for alle k≥2k\ge 2 — spesielt 66≡06^6\equiv 0, ikke 11.

Sluttsvar: teoremet holder i a) og b); i c) er vilkåret brutt, og 6ϕ(9)≡0(mod9)6^{\phi(9)}\equiv 0\pmod 9.

Punkt c) er verdt å se én gang med egne øyne, for det er nettopp denne situasjonen fasitene advarer mot. Når aa og nn deler en primfaktor, vokser den felles faktoren i potensene i stedet for å gå i ring — så aka^k nærmer seg 00 modulo nn og kommer aldri tilbake til 11.

📝Oppgave 4
a) Regn ut ϕ(20)\phi(20), og verifiser Eulers teorem for a=7a=7, n=20n=20 ved direkte regning.
b) Kan Eulers teorem brukes på a=10a=10, n=20n=20? Begrunn.

Løkke 4: Eksponentreduksjon — teoremet brukt som verktøy

~9 minutter.

Eulers teorem sier at aϕ(n)≡1a^{\phi(n)}\equiv 1. Konsekvensen er at eksponenten bare betyr noe modulo ϕ(n)\phi(n) — og det er hele grunnen til at en eksponent på 455 kan behandles for hånd.

Eksponentreduksjon modulo ϕ(n)
Er gcd⁡(a,n)=1\gcd(a,n)=1 og N=ϕ(n)⋅q+rN=\phi(n)\cdot q+r med 0≤r<ϕ(n)0\le r<\phi(n), så
aN=(aϕ(n))q⋅ar≡1q⋅ar=ar(modn).a^N=\left(a^{\phi(n)}\right)^{q}\cdot a^{r}\equiv 1^{q}\cdot a^{r}=a^{r}\pmod n.

Med andre ord: del eksponenten på ϕ(n)\phi(n) og behold bare resten.

Regelen må sitte utenat, og utledningen over er den du skriver i besvarelsen — den er tre symboler lang og gjør reduksjonen begrunnet i stedet for postulert.

Merk at rr kan være 00. Da er aN≡a0=1(modn)a^N\equiv a^0=1\pmod n. Det er riktig svar, ikke et tegn på at noe er galt.

Og merk at reduksjonen bare gjelder eksponenten. Grunntallet aa reduseres modulo nn (vanlig kongruensregning), eksponenten modulo ϕ(n)\phi(n). De to modulene blandes lett, og det er den nest vanligste feilen i sjangeren.

Hvorfor eksponenten reduseres mod ϕ(n) og ikke mod n

Dette er den forvekslingen som koster mest, og den er verdt et eget kort.

To ulike moduler er i spill samtidig:

Det du redusererModulusHjemmel
grunntallet aannvanlige kongruensregneregler (kap. 1.4)
eksponenten NNϕ(n)\phi(n)Eulers teorem, og bare når gcd⁡(a,n)=1\gcd(a,n)=1

Se på et eksempel der forskjellen er tydelig. Skal du finne 3455 mod 1003^{455}\bmod 100, er ϕ(100)=40\phi(100)=40. Riktig reduksjon: 455≡15(mod40)455\equiv 15\pmod{40}, altså 3455≡315≡73^{455}\equiv 3^{15}\equiv 7. Gal reduksjon modulo 100100: 455≡55455\equiv 55, og 355≡47(mod100)3^{55}\equiv 47\pmod{100} — et helt annet svar.
Minnekroken: eksponenten teller runder på hjulet, og hjulet har ϕ(n)\phi(n) hakk, ikke nn. Modulusen nn hører til tallene, ϕ(n)\phi(n) hører til eksponentene.
Praktisk vane som forebygger feilen: skriv ϕ(n)\phi(n) ned som et eget tall på arket, med navn, før du rører eksponenten.

Reduser grunntallet først

Er grunntallet større enn modulusen, reduser det først. Det er lovlig etter potensregelen for kongruenser i kap. 1.4: er a≡b(modn)a\equiv b\pmod n, så er aN≡bN(modn)a^N\equiv b^N\pmod n.

Eksempel: 12350 mod 11123^{50}\bmod 11. Først 123=11⋅11+2123=11\cdot 11+2, så 123≡2(mod11)123\equiv 2\pmod{11}, og oppgaven er blitt 250 mod 112^{50}\bmod 11.

Hvorfor det er verdt å gjøre først: små grunntall gir små kvadrater. 22=42^2=4 er lettere å holde i hodet enn 1232=15 129123^2=15\,129, og hvert kvadrat du regner med et lite tall er en feil mindre.

En bonus: reduksjonen gjør ofte gcd⁡\gcd-sjekken lettere å se. gcd⁡(123,11)\gcd(123,11) er ikke åpenbart; gcd⁡(2,11)=1\gcd(2,11)=1 er det.

Men vær nøyaktig med hva du reduserer. Grunntallet modulo nn, eksponenten modulo ϕ(n)\phi(n) — aldri omvendt.

✏️Restberegning etter malen: 3^455 modulo 100

Finn resten når 34553^{455} deles på 100100.

(i) Faktoriser modulusen. 100=22⋅52100 = 2^{2} \cdot 5^{2}.

(ii) gcd⁡\gcd-sjekken. gcd⁡(3,100)=1\gcd(3,100)=1, siden 33 ikke har noen primfaktor felles med 100100. Vilkåret er oppfylt, så teoremet kan brukes.

(iii) Regn ut ϕ(n)\phi(n). Fra faktoriseringen: ϕ(100)=(22−21)⋅(52−51)=2⋅20=40\phi(100)=(2^{2}-2^{1})\cdot (5^{2}-5^{1}) = 2\cdot 20=40.

(iv) Reduser eksponenten. Fra Eulers teorem er 340≡1(mod100)3^{40}\equiv 1\pmod{100}, så vi kan redusere eksponenten modulo ϕ(100)=40\phi(100)=40:

455=40⋅11+15,sa˚3455=(340)11⋅315≡111⋅315=315(mod100).455 = 40\cdot 11 + 15,\qquad\text{så}\qquad 3^{455} = \left(3^{40}\right)^{11}\cdot 3^{15}\equiv 1^{11}\cdot 3^{15} = 3^{15}\pmod{100}.

(v) Binærutviklingen av eksponenten og de suksessive kvadratene. Vi skriver eksponenten som en sum av toerpotenser: 15=8+4+2+115 = 8 + 4 + 2 + 1, altså 1515 i binær er 11111111. Deretter kvadrerer vi oss oppover, og reduserer modulo 100100 etter hvert kvadrat:

PotensUtregningRest modulo 100100
313^{1}—33
323^{2}32=93^2=999
343^{4}92=819^2=818181
383^{8}812=6 56181^2=6\,561, og 6 561=100⋅65+616\,561=100\cdot 65+616161

(vi) Sett sammen produktet. Da er
315=38⋅34⋅32⋅31≡61⋅81⋅9⋅3(mod100),3^{15} = 3^{8} \cdot 3^{4} \cdot 3^{2} \cdot 3^{1} \equiv 61 \cdot 81 \cdot 9 \cdot 3 \pmod{100},
og vi multipliserer to av gangen, med reduksjon underveis: 61⋅81=4 941≡4161\cdot 81 = 4\,941\equiv 41; 41⋅9=369≡6941\cdot 9 = 369\equiv 69; 69⋅3=207≡769\cdot 3 = 207\equiv 7.
(vii) Konklusjon. Resten når 34553^{455} deles på 100100, er 7\boxed{7}.
Legg merke til hvor lite regning dette var: fire kvadrater og tre multiplikasjoner, alle med tall under 100100. Det er kode D-realistisk — og det er hele grunnen til at eksponentreduksjonen kommer FØR potensregningen.

Og legg merke til at svaret 77 er det siste sifferet i 34553^{455} pluss noe: resten modulo 100100 er de to siste sifrene, altså 0707.

📝Oppgave 5

Finn resten når 310003^{1000} deles på 1414.

📝Oppgave 6

Finn resten når 1140311^{403} deles på 2424.

Løkke 5: Kvadrer-og-multipliser, og føringsmalen

~11 minutter.

Etter reduksjonen står du med noe som 315 mod 1003^{15}\bmod 100. Det er fremdeles for stort å regne rått — 3153^{15} er nesten fjorten millioner. Prosedyren under gjør det til fire kvadrater.

— naturlig pausepunkt —

Kvadrer-og-multipliser

Prosedyren for å regne ae mod na^{e}\bmod n med få operasjoner, ved å bruke binærutviklingen av eksponenten.

Oppskriften:

1. Skriv ee som en sum av toerpotenser (ee i binær). For e=15e=15: 15=8+4+2+115=8+4+2+1.
2. Regn de suksessive kvadratene a1,a2,a4,a8,…a^1,a^2,a^4,a^8,\dots — hvert ledd er kvadratet av det forrige, redusert modulo nn etter hvert kvadrat.
3. Gang sammen de kvadratene som svarer til 11-erne i binærutviklingen, to av gangen, med reduksjon underveis.

Prosedyren må sitte utenat. Under kode D er den den eneste måten å regne ae mod na^{e}\bmod n for eksponenter over ti — kalkulatoren mister presisjonen lenge før.

Hvorfor reduksjonen etter hvert kvadrat er kritisk: uten den vokser tallene eksponentielt, og du regner med sekssifrede tall etter tre steg. Med den er hvert tall alltid mindre enn nn.

Antall operasjoner: omtrent log⁡2e\log_2 e kvadrater og like mange multiplikasjoner i verste fall. For e<32e<32 betyr det 2–5 kvadrater, som er nøyaktig kode D-nivå.

Fasitkravet: mellomstegene skal stå. Løsningsforslagene dokumenterer binærutviklingen og kvadrattabellen, og et sluttall uten dem er et svar uten metode.

Føringsmalen for restberegning — sju steg

Slik føres hver restberegning i boka, og slik bør du føre den på eksamen. Malen er identisk i alle kapitler der aN mod na^N\bmod n regnes (kap. 2.5, kap. 2.6, kap. 3.1, kap. 3.2).

(i) Faktoriser modulusen.
(ii) gcd⁡\gcd-sjekken — skriv setningen «gcd⁡(a,n)=1\gcd(a,n)=1, så vilkåret er oppfylt».
(iii) Regn ut ϕ(n)\phi(n) fra faktoriseringen.
(iv) Reduser eksponenten modulo ϕ(n)\phi(n) (Eulers teorem) eller modulo p−1p-1 (Fermats lille teorem), med teoremnavnet.
(v) Binærutviklingen av eksponenten og de suksessive kvadratene, som liten tabell.
(vi) Sett sammen produktet, to faktorer av gangen, med reduksjon underveis.
(vii) Konklusjon — «resten er …», som en setning, med sluttsvaret markert.

Malen må sitte utenat, og hvert steg bærer uttelling for seg selv. Grunnen er instruksen som står på hvert eneste sett: alle svar må begrunnes.

Steg (ii) er det som oftest mangler i en ellers riktig besvarelse — og det er det steget som avgjør om metoden i det hele tatt er lovlig.

📝Oppgave 7

Finn resten når 82478^{247} deles på 6363. Bruk føringsmalen, og kommenter til slutt om reduksjonen kunne gjøres kortere.

Løkke 6: Når gcd⁡(a,n)≠1\gcd(a,n)\ne 1

~9 minutter.

Her er tilfellet fasitene advarer mot, og som en del av oppgavene i arkivet er bygget rundt: grunntallet og modulusen deler en primfaktor. Da kan Eulers teorem ikke brukes på nn — og oppgaven er fortsatt løsbar, med en omvei.

Når gcd(a, n) ≠ 1 — splitt modulusen

Eulers teorem krever gcd⁡(a,n)=1\gcd(a,n)=1. Deler aa og nn en primfaktor, gjør du dette i stedet:

1. Faktoriser nn i primtallspotenser, n=pk⋅mn=p^k\cdot m med gcd⁡(pk,m)=1\gcd(p^k,m)=1.
2. Regn resten modulo hver del for seg. Der gcd⁡(a,delen)=1\gcd(a,\text{delen})=1 bruker du Eulers teorem som normalt. Der primtallet deler aa, blir aN≡0a^N\equiv 0 så snart eksponenten er stor nok (se neste kort).
3. Sett sammen igjen med splittingsregelen fra kap. 1.4: x≡b(modpk)x\equiv b\pmod{p^k} og x≡c(modm)x\equiv c\pmod m bestemmer xx entydig modulo nn, siden gcd⁡(pk,m)=1\gcd(p^k,m)=1.

Steg 3 er det kinesiske restteoremet, og i kap. 2.4 får du en systematisk oppskrift for det. Her klarer vi oss med å lete: skriv opp de få tallene under nn som oppfyller den ene kongruensen, og se hvilket av dem som oppfyller den andre.

Merk hva som IKKE virker: å bruke ϕ(n)\phi(n) likevel og håpe. 6ϕ(9)=66≡0(mod9)6^{\phi(9)}=6^6\equiv 0\pmod 9, ikke 11 — reduksjonen ville gitt galt svar, ikke bare et upresist et.

Hvorfor a^N ≡ 0 når primtallet deler grunntallet
Deler primtallet pp tallet aa, og er N≥kN\ge k, så
aN≡0(modpk).a^N\equiv 0\pmod{p^k}.

Utledes på stedet, én linje: skriv a=p⋅sa=p\cdot s. Da er aN=pNsNa^N=p^N s^N, og siden N≥kN\ge k er pk∣pNp^k\mid p^N, altså pk∣aNp^k\mid a^N. ■\blacksquare

Praktisk betydning: i en splitting er dette den lette delen. Skal du regne 12103 mod 4512^{103}\bmod 45 og splitter i 99 og 55, gir 3∣123\mid 12 og 103≥2103\ge 2 direkte at 12103≡0(mod9)12^{103}\equiv 0\pmod 9 — ingen ϕ\phi, ingen kvadrattabell.

Men sjekk eksponenten. Kravet er N≥kN\ge k, der kk er eksponenten i primtallspotensen. For 9=329=3^2 trengs N≥2N\ge 2. Er eksponenten mindre (f.eks. 121 mod 9=312^1\bmod 9=3), regner du direkte i stedet.

Og merk at dette er grunnen til at Euler feiler her: potensen går ikke i ring, den samler opp faktorer av pp og blir stående på 00.

✏️Eksamensnivå: 12^103 modulo 45, der Euler ikke kan brukes direkte

Finn resten når 1210312^{103} deles på 4545.

Steg 1: gcd⁡\gcd-sjekken — og den svikter. 45=32⋅545=3^2\cdot 5 og 12=22⋅312=2^2\cdot 3, så
gcd⁡(12,45)=3≠1.\gcd(12,45)=3\ne 1.
Eulers teorem kan altså ikke brukes på modulus 4545. Vi splitter i stedet.

Steg 2: splitt modulusen. 45=9⋅545=9\cdot 5 med gcd⁡(9,5)=1\gcd(9,5)=1, så etter splittingsregelen fra kap. 1.4 er det nok å finne resten modulo 99 og modulo 55.

Steg 3: modulo 99. Her er 3∣123\mid 12, og eksponenten 103≥2103\ge 2, så
12103≡0(mod9).12^{103}\equiv 0\pmod 9.
(Grunn: 12=3⋅412=3\cdot 4, så 12103=3103410312^{103}=3^{103}4^{103}, og 32∣31033^2\mid 3^{103}.)

Steg 4: modulo 55. Her er gcd⁡(12,5)=1\gcd(12,5)=1 ✓, så Eulers teorem kan brukes. Vi reduserer først grunntallet: 12≡2(mod5)12\equiv 2\pmod 5. Og ϕ(5)=4\phi(5)=4, så eksponenten reduseres modulo 44:
103=4⋅25+3,sa˚12103≡2103≡23=8≡3(mod5).103=4\cdot 25+3,\qquad\text{så}\qquad 12^{103}\equiv 2^{103}\equiv 2^{3}=8\equiv 3\pmod 5.

Steg 5: sett sammen. Vi trenger xx med
x≡0(mod9),x≡3(mod5),0≤x<45.x\equiv 0\pmod 9,\qquad x\equiv 3\pmod 5,\qquad 0\le x<45.
Multiplene av 99 under 4545 er 0,9,18,27,360,9,18,27,36. Restene deres modulo 55 er 0,4,3,2,10,4,3,2,1. Bare 1818 gir rest 33.

Kontroll. 18=9⋅2+018=9\cdot 2+0 ✓ og 18=5⋅3+318=5\cdot 3+3 ✓.

Konklusjon. Resten når 1210312^{103} deles på 4545, er 18\boxed{18}.

Steg 5 er det kinesiske restteoremet gjort med bare øyne. Med fem kandidater er letingen raskere enn formelen — men blir modulusen større, trenger du systematikken i kap. 2.4.

Og merk hvorfor oppgaven i det hele tatt var vanskelig: hadde du glemt gcd⁡\gcd-sjekken og redusert 103103 modulo ϕ(45)=24\phi(45)=24, ville du fått 12712^{7}, og 127≡18(mod45)12^7\equiv 18\pmod{45} — samme svar ved ren flaks i dette tilfellet, men ingen begrunnelse som holder. Metoden er det som vurderes.

📝Oppgave 8

Finn resten når 6856^{85} deles på 7575.

📝Oppgave 9
a) Finn det siste sifferet i 720267^{2026}.
b) Finn de to siste sifrene i 720267^{2026}.
📝Oppgave 10

Eulers teorem kan brukes til å finne inverser.

a) Vis at når gcd⁡(a,n)=1\gcd(a,n)=1, er aϕ(n)−1a^{\phi(n)-1} en invers til aa modulo nn.
b) Bruk det til å finne inversen til 77 modulo 2020.
c) Finn samme invers med Euklids algoritme, og sammenlign metodene.

Begrepsbank

Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 60 minutter gjelder kjernestoffet over.

Kortene under er delt i to slag: fagkort (hva ϕ\phi er og hvordan den oppfører seg) og prosedyrekort (hvordan du regner og fører). Under kode D er begge slagene eksamensverktøy — det finnes ingen formelsamling å slå opp i, så disse kortene er hele apparatet du har med deg inn i rommet.

ϕ(n) er alltid partall for n ≥ 3

For alle n≥3n\ge 3 er ϕ(n)\phi(n) et partall.

Utledes på stedet, to tilfeller:

- Har nn en odde primfaktor pp, inneholder ϕ(n)\phi(n) faktoren ϕ(pk)=pk−1(p−1)\phi(p^k)=p^{k-1}(p-1), og p−1p-1 er et partall.
- Ellers er n=2kn=2^k med k≥2k\ge 2, og ϕ(2k)=2k−1\phi(2^k)=2^{k-1} er et partall.

■\blacksquare

Bruk det som kontroll. Får du et odde svar for ϕ(n)\phi(n) med n≥3n\ge 3, har du regnet feil — garantert. Det er den billigste feilsjekken i kapitlet, og den fanger nettopp ϕ(pk)=pk−1\phi(p^k)=p^k-1-feilen (som gir odde svar når pp er odde).

Unntakene er ϕ(1)=1\phi(1)=1 og ϕ(2)=1\phi(2)=1.

ϕ-verdier verdt å ha i fingrene

Ikke som tabell å slå opp i — den finnes ikke under kode D — men som gjenkjenning, slik at du ser når du har regnet feil.

nnϕ(n)\phi(n)Hvorfor
1010441⋅41\cdot 4
121244(4−2)⋅2(4-2)\cdot 2
1001004040(4−2)(25−5)=2⋅20(4-2)(25-5)=2\cdot 20
10001000400400(8−4)(125−25)=4⋅100(8-4)(125-25)=4\cdot 100
2k2^k2k−12^{k-1}halvparten — de odde tallene
ppp−1p-1primtall
pqpq(p−1)(q−1)(p-1)(q-1)to ulike primtall — RSA-tilfellet

Den siste linja er den viktigste, for den er hele nøkkelgenereringen i RSA (kap. 3.1). Merk at den følger av multiplikativiteten pluss ϕ(p)=p−1\phi(p)=p-1 — ikke noe nytt å pugge.
Merk også at ϕ\phi ikke er voksende: ϕ(10)=4\phi(10)=4 mens ϕ(9)=6\phi(9)=6. Et større tall kan ha færre relativt primiske tall under seg, hvis det har flere små primfaktorer.

Gauss' identitet: summen av ϕ over divisorene
For hvert positivt nn:
∑d∣nϕ(d)=n.\sum_{d\mid n}\phi(d)=n.

Kontroll for n=12n=12: divisorene er 1,2,3,4,6,121,2,3,4,6,12, og
ϕ(1)+ϕ(2)+ϕ(3)+ϕ(4)+ϕ(6)+ϕ(12)=1+1+2+2+2+4=12 ✓.\phi(1)+\phi(2)+\phi(3)+\phi(4)+\phi(6)+\phi(12)=1+1+2+2+2+4=12\ \checkmark.

Intuisjonen bak: sorter brøkene 1n,2n,…,nn\displaystyle \frac1n,\frac2n,\dots,\frac nn etter hvilken nevner de får når de forkortes helt. For hver divisor dd av nn er det nøyaktig ϕ(d)\phi(d) brøker som ender med nevner dd. Til sammen er brøkene nn stykker.

Hvor du får bruk for den: i tellingen av elementer med gitt orden i Del 5, der den forklarer hvorfor antallet primitive røtter blir ϕ(ϕ(n))\phi(\phi(n)). Den er sjelden en oppgave i seg selv i arkivet, men den er en pen kontroll og et godt tegn på at du forstår hva ϕ\phi teller.

Kontrollrutinen i sjanger E

Under kode D er selvkontroll den eneste kontrollen du har. Disse fire tar til sammen under ett minutt og fanger nesten alt.

EtterKontrollFanger
faktoriseringengang faktorene sammen igjenavskrivningsfeil
ϕ(n)\phi(n)er svaret partall (for n≥3n\ge 3) og mindre enn nn?ϕ(pk)=pk−1\phi(p^k)=p^k-1-feilen
gcd⁡\gcd-sjekkenstår setningen der?ulovlig bruk av Euler
kvadrattabellener hver rad kvadratet av forrige, redusert?kjedefeil som forplanter seg

Og til slutt, den beste av alle: er sluttsvaret et tall mellom 00 og n−1n-1? Får du 103103 som rest modulo 4545, har du glemt en reduksjon.
Én kontroll som ikke finnes: du kan ikke regne aNa^N rått og sammenligne. Tallet har hundrevis av siffer. Derfor må kontrollene ligge underveis, ikke til slutt.

Kode D-realisme: hva tallene ser ut som

Kalibreringskortet som forteller deg om du har regnet feil eller møtt en vanskelig oppgave.

StørrelseTypisk verdi på eksamen
modulusen nnto- til firesifret, lett å faktorisere med prøvedivisjon
ϕ(n)\phi(n)to- til tresifret
eksponenten NNto- til firesifret (ofte et årstall)
eksponenten etter reduksjonunder 32 — altså 2–5 kvadrater
tallene i kvadrattabellenalltid under nn, fordi du reduserer underveis

Bruk det som kontroll. Blir eksponenten etter reduksjon tresifret, har du sannsynligvis redusert modulo feil tall. Får du sekssifrede tall i kvadrattabellen, har du glemt å redusere etter et kvadrat.
Og bruk det når du lager egne øvingsoppgaver: velg modulusen først (et produkt av to små primtallspotenser), regn ϕ\phi, og velg en eksponent som gir en liten rest. Da vet du at oppgaven er regnbar før du begynner.

Euler og Fermat — forholdet mellom dem
Fermats lille teorem er Eulers teorem med en primtallsmodulus. Er n=pn=p et primtall, er ϕ(p)=p−1\phi(p)=p-1, og Eulers teorem
aϕ(n)≡1(modn)a^{\phi(n)}\equiv 1\pmod n
blir
ap−1≡1(modp)na˚r p∤a.a^{p-1}\equiv 1\pmod p\qquad\text{når }p\nmid a.

Det er hele utledningen — én linje. Derfor står Fermat i «utledes på stedet»-listen: kan du Euler, får du Fermat gratis. Vi tar teoremet for seg selv i kap. 2.2, fordi det har egne bruksmåter og en egen felle.

Den praktiske forskjellen ligger i hva du reduserer modulo:

ModulusReduser eksponenten moduloVilkår
primtall ppp−1p-1p∤ap\nmid a
sammensatt nnϕ(n)\phi(n)gcd⁡(a,n)=1\gcd(a,n)=1

Den vanligste blandingen: å bruke n−1n-1 som eksponentmodulus for et sammensatt nn. For n=14n=14 er ϕ(14)=6\phi(14)=6, ikke 1313.
ϕ(n) virker alltid, men er ikke alltid minst

Eulers teorem sier at aϕ(n)≡1a^{\phi(n)}\equiv 1. Den sier ikke at ϕ(n)\phi(n) er den minste eksponenten som gir 11.

Eksempel: 82=64≡1(mod63)8^2=64\equiv 1\pmod{63}, mens ϕ(63)=36\phi(63)=36. Den minste eksponenten er 22.

Den minste positive kk med ak≡1(modn)a^k\equiv 1\pmod n kalles ordenen til aa modulo nn, skrevet ord⁡n(a)\operatorname{ord}_n(a), og er temaet i Del 5. Hovedresultatet der er at ordenen alltid deler ϕ(n)\phi(n).

Hva det betyr for regningen din nå: ingenting går galt om du bruker ϕ(n)\phi(n) — reduksjonen er riktig uansett. Men ser du at en liten potens gir 11 mens du lager kvadrattabellen, kan du bruke den i stedet og spare tid. Si det da: «siden 82≡18^2\equiv 1, er 8247=(82)123⋅8≡88^{247}=(8^2)^{123}\cdot 8\equiv 8».

Praktisk vane: kast alltid et blikk på a2a^2 og a3a^3 modulo nn før du starter. Er en av dem 11 eller −1-1, er hele oppgaven kort.

Hvor Euler møter RSA
RSA hviler på Eulers teorem, og det er verdt å se koblingen før du kommer til kap. 3.1.

Oppsettet: n=pqn=pq med p,qp,q ulike primtall, så ϕ(n)=(p−1)(q−1)\phi(n)=(p-1)(q-1) ved multiplikativiteten. Krypteringseksponenten ee velges med gcd⁡(e,ϕ(n))=1\gcd(e,\phi(n))=1, og dekrypteringseksponenten dd er inversen: ed≡1(modϕ(n))ed\equiv 1\pmod{\phi(n)}.

Hvorfor det virker: ed=1+kϕ(n)ed=1+k\phi(n) for et helt tall kk, så
(me)d=med=m1+kϕ(n)=m⋅(mϕ(n))k≡m⋅1k=m(modn),(m^{e})^{d}=m^{ed}=m^{1+k\phi(n)}=m\cdot\left(m^{\phi(n)}\right)^{k}\equiv m\cdot 1^{k}=m\pmod n,
fra Eulers teorem, når gcd⁡(m,n)=1\gcd(m,n)=1. Dekrypteringen gjenoppretter meldingen.

Dette utledes på stedet — tre linjer, og du har korrekthetsbeviset for RSA. Det er en eksamensoppgave i seg selv (sjanger D), og du skal ikke pugge det som et faktum, men kunne føre det.

Tilfellet gcd⁡(m,n)≠1\gcd(m,n)\ne 1 krever litt mer, og behandles i kap. 3.1.

Hvor liten kan ϕ(n) bli?
ϕ(n)<n\phi(n)<n for alle n≥2n\ge 2, og ϕ(n)=n−1\phi(n)=n-1 nøyaktig når nn er et primtall.

Motsatt vei: ϕ(n)\phi(n) blir liten når nn har mange små primfaktorer. For n=2⋅3⋅5⋅7=210n=2\cdot 3\cdot 5\cdot 7=210:
ϕ(210)=1⋅2⋅4⋅6=48,\phi(210)=1\cdot 2\cdot 4\cdot 6=48,
altså under en fjerdedel av nn.

Hvorfor det er praktisk å vite: i en restberegning er det ϕ(n)\phi(n) som bestemmer hvor mye eksponenten kan krympe. En modulus med mange små primfaktorer gir liten ϕ\phi og dermed kort regning — og det er nettopp derfor eksamensoppgavene bruker moduler som 100100, 4545, 6363 og 210210.

Kontrollbruk: er ϕ(n)\phi(n)-svaret ditt større enn n−1n-1, er det garantert feil. Er det n−1n-1 uten at nn er et primtall, er det også feil.

Tidsbudsjettet for sjanger E

Eksamen er 4 timer på omtrent 10 likt vektede delpunkt — altså ~24 minutter per delpunkt.

Slik fordeler en restberegning seg når prosedyren sitter:

StegInnholdTid
(i)–(ii)faktoriser modulusen, gcd⁡\gcd-sjekken~2 min
(iii)ϕ(n)\phi(n)~1 min
(iv)eksponentreduksjonen med teoremnavnet~2 min
(v)–(vi)kvadrattabell og produkt~5 min
(vii)konklusjon og kontroll~1 min

Til sammen ~11 minutter — under halve budsjettet for ett delpunkt. Det er derfor sjanger E er billige poeng: prosedyren er kort når den sitter, og den sitter bare hvis du har kjørt den mange ganger.
Er du over 20 minutter, ligger det nesten alltid i faktoriseringen eller i at du regner uten å redusere underveis. Begge er vanesaker, ikke forståelsesproblemer.

Skriveraden: hva som SKAL stå i besvarelsen

Et føringskort, ikke et fagkort — men det avgjør uttellingen.

En fullgod besvarelse av «finn resten når aNa^N deles på nn» inneholder alle disse setningene:

1. faktoriseringen av nn;
2. setningen «gcd⁡(a,n)=1\gcd(a,n)=1», med begrunnelse;
3. ϕ(n)\phi(n) regnet ut, med ϕ(pk)\phi(p^k)-formelen synlig;
4. teoremnavnet: «fra Eulers teorem» / «fra Fermats lille teorem»;
5. divisjonen N=ϕ(n)q+rN=\phi(n)q+r og den reduserte potensen;
6. binærutviklingen og kvadrattabellen;
7. en konklusjonssetning med sluttsvaret.

Selvtesten: kan noen som leser besvarelsen din, følge hvert steg fra aNa^N til resten uten å regne selv? Da er føringen god nok.

Det som IKKE holder: «3455≡7(mod100)3^{455}\equiv 7\pmod{100}» alene. Riktig svar, ingen metode — og instruksen på hvert sett er at alle svar må begrunnes.

To små regneregler for ϕ
Begge utledes på stedet fra multiplikativiteten, og begge sparer tid.

Regel 1: dobling av et odde tall. Er nn odde, er ϕ(2n)=ϕ(2)ϕ(n)=ϕ(n).\phi(2n)=\phi(2)\phi(n)=\phi(n).
Grunnen: gcd⁡(2,n)=1\gcd(2,n)=1 når nn er odde, og ϕ(2)=1\phi(2)=1. Så ϕ(14)=ϕ(7)=6\phi(14)=\phi(7)=6 og ϕ(50)=ϕ(25)=20\phi(50)=\phi(25)=20.

Regel 2: dobling av et partall. Er nn et partall, er
ϕ(2n)=2ϕ(n).\phi(2n)=2\phi(n).
Grunnen: da vokser bare eksponenten på 22, og ϕ(2k+1)=2k=2⋅2k−1=2ϕ(2k)\phi(2^{k+1})=2^{k}=2\cdot 2^{k-1}=2\phi(2^k). Så ϕ(20)=2ϕ(10)=8\phi(20)=2\phi(10)=8.

Merk at reglene ikke er noe nytt fagstoff — de er multiplikativiteten brukt på en spesiell faktor. Verdien deres er at de gir en rask kontroll: ϕ(50)\phi(50) skal være lik ϕ(25)\phi(25), og er den ikke det, har du regnet feil et sted.

De tre måtene ϕ spørres om på eksamen

Sjanger E og H spør om ϕ\phi på tre forskjellige måter, og det er verdt å kjenne dem igjen.

1. Direkte: «Regn ut ϕ(n)\phi(n).» Faktoriser og bruk oppskriften. Billigste delpunkt i settet.
2. Som verktøy i en restberegning: «Finn resten når aNa^N deles på nn.» ϕ(n)\phi(n) er steg (iii) av sju. Dette er den vanligste formen.
3. Baklengs: «Finn alle nn med ϕ(n)=8\phi(n)=8.» Her må du tenke på hvilke primtallspotenser som kan gange sammen til 88. Sjeldnere, men forekommer — og teknikken er den samme som «minste nn med gitt antall divisorer» i Del 5.

Til form 3, som mange ikke har sett: ϕ(n)=8\phi(n)=8 krever at hver faktor ϕ(pk)\phi(p^k) deler 88. Kandidatene er ϕ(16)=8\phi(16)=8, ϕ(32)=16\phi(32)=16 (for stor), ϕ(15)=8\phi(15)=8, ϕ(20)=8\phi(20)=8, ϕ(24)=8\phi(24)=8, ϕ(30)=8\phi(30)=8. Svaret er n∈{15,16,20,24,30}n\in\{15,16,20,24,30\} — og systematikken er å gå gjennom primtallene pp med p−1∣8p-1\mid 8, altså p∈{2,3,5}p\in\{2,3,5\}.

Notasjon: ϕ, og hva den ikke er

Boka skriver ϕ\phi for Eulers funksjon, gjennomgående. Andre framstillinger bruker den andre skrivemåten av samme greske bokstav (den med krøll på staven) — det er samme funksjon, og forskjellen er bare typografisk. Velg én form og hold deg til den; boka har valgt ϕ\phi.

Tre forvekslinger å unngå:

- ϕ(n)\phi(n) er ikke antall divisorer i nn. Det er τ(n)\tau(n), en annen funksjon (Del 5). ϕ(12)=4\phi(12)=4 og τ(12)=6\tau(12)=6.
- ϕ(n)\phi(n) er ikke det gyldne snitt, som noen framstillinger også kaller ϕ\phi. I tallteori er ϕ\phi alltid totientfunksjonen.
- ϕ(n)\phi(n) er en verdi, ikke en operasjon på en kongruens. Skriv ϕ(100)=40\phi(100)=40, aldri «ϕ(mod100)\phi\pmod{100}».

Uttalen: «fi av n», eller «Eulers fi-funksjon». Navnet «totient» brukes også, men sjelden på norsk.

Grensetilfellene ϕ(1) og ϕ(2)
ϕ(1)=1,ϕ(2)=1.\phi(1)=1,\qquad \phi(2)=1.

ϕ(1)=1\phi(1)=1: intervallet 1≤a≤11\le a\le 1 inneholder bare a=1a=1, og gcd⁡(1,1)=1\gcd(1,1)=1, så tallet teller. Konvensjonen er nyttig fordi den gjør ϕ\phi multiplikativ helt ned til n=1n=1: ϕ(1⋅n)=ϕ(1)ϕ(n)\phi(1\cdot n)=\phi(1)\phi(n).

ϕ(2)=1\phi(2)=1: bare a=1a=1 er relativt primisk til 22.

Hvor det betyr noe i praksis: i en faktorisering som 14=2⋅714=2\cdot 7 er faktoren ϕ(2)=1\phi(2)=1, som er grunnen til at ϕ(14)=ϕ(7)=6\phi(14)=\phi(7)=6. Glemmer du at ϕ(2)=1\phi(2)=1 og skriver 22, blir svaret dobbelt så stort.

Og merk at disse to er de eneste odde verdiene ϕ\phi tar — for n≥3n\ge 3 er ϕ(n)\phi(n) alltid partall.

Bevisidéen i Eulers teorem, i én setning

Verdt å kunne gjengi, fordi den samme idéen bærer Wilsons teorem (kap. 2.3) og ordensteorien i Del 5.

Setningen: å gange et redusert restsystem med aa stokker om systemet, og produktet av kortene er uendret — derfor må aϕ(n)a^{\phi(n)} være 11.

De tre stegene, som stikkord:

1. ar1,…,arϕ(n)ar_1,\dots,ar_{\phi(n)} er samme restklasser som r1,…,rϕ(n)r_1,\dots,r_{\phi(n)}, i annen rekkefølge (fordi forkorting med aa er lovlig når gcd⁡(a,n)=1\gcd(a,n)=1).
2. Produktene er derfor kongruente: aϕ(n)R≡Ra^{\phi(n)}R\equiv R.
3. Forkort med RR (lovlig, gcd⁡(R,n)=1\gcd(R,n)=1): aϕ(n)≡1a^{\phi(n)}\equiv 1.

Hvorfor det er verdt plass i bunken: en eksamensoppgave kan be deg «forklare hvorfor Eulers teorem gjelder» eller «vise Fermats lille teorem». Da er dette skjelettet du fyller ut. Og forkortingsregelen er det ene stedet vilkåret gcd⁡(a,n)=1\gcd(a,n)=1 faktisk brukes — det er verdt å kunne peke på.

Sjanger E i én oversikt

Kortet som binder kapitlet sammen — hva du gjør, avhengig av hva du ser.

SituasjonVerktøyReduser eksponenten modulo
nn primtall, p∤ap\nmid aFermats lille teoremp−1p-1
nn sammensatt, gcd⁡(a,n)=1\gcd(a,n)=1Eulers teoremϕ(n)\phi(n)
gcd⁡(a,n)≠1\gcd(a,n)\ne 1splitt nn i primtallspotenserhver del for seg
fakultet i uttrykketWilsons teorem (kap. 2.3)—
flere kongruenser samtidigdet kinesiske restteoremet (kap. 2.4)—

Første spørsmål er alltid det samme: er gcd⁡(a,n)=1\gcd(a,n)=1? Svaret bestemmer hvilken rad du er i, og det er derfor gcd⁡\gcd-sjekken er steg (ii) og ikke steg (v).
Den sammensatte varianten — der flere av radene brukes i samme oppgave — er kap. 2.5, og den er den mest belagte restberegningen i arkivet.

Repetisjonsoppgaver
Symbol- og formelliste

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.