5.1 Orden modulo n og «orden deler ϕ(n)»

$$a^k\equiv 1\pmod n.$$

I klarspråk: hvor mange ganger du må gange med $a$ før du kommer tilbake til $1$.

Ordet «minste» er hele definisjonen. At $a^{12}\equiv 1$ betyr ikke at ordenen er $12$ — den kan være $1$, $2$, $3$, $4$, $6$ eller $12$. Å oppgi en $k$ med $a^k\equiv 1$ uten å utelukke de mindre, er den mest belagte feilen i sjangeren, og den koster uttelling selv når tallet er riktig.

Definisjonen må sitte utenat, med ordet «minste», og notasjonen skrives $\operatorname{ord}_n(a)$ — alltid med modulusen som indeks. «$\operatorname{ord}(a)$» er meningsløst uten modulus, siden samme tall har ulik orden modulo ulike $n$: $\operatorname{ord}_{17}(2)=8$, men $\operatorname{ord}_{13}(2)=12$.

Eksempel med tall. Modulo $17$: $3^1=3$, $3^2=9$, $3^4\equiv 13$, $3^8\equiv 16$, $3^{16}\equiv 1$. Ordenen er $16$ — ingen mindre eksponent gir $1$, som vi kontrollerer i eksempel 1.

Grunnen, i én linje: var $a^k\equiv 1\pmod n$, ville $a^k-1=mn$ for et helt tall $m$, altså $a\cdot a^{k-1}-n m=1$ — og da ville $\gcd(a,n)$ måtte dele $1$ etter lineærkombinasjonsregelen fra kap. 1.1.

Konkret hva som skjer uten vilkåret: ta $a=3$, $n=12$, der $\gcd(3,12)=3$. Potensene er
$$3,\ 9,\ 3,\ 9,\ 3,\ 9,\dots$$
De blir periodiske, men de treffer aldri $1$. Følgen «henger seg opp» i en syklus som ikke inneholder $1$.

Vilkåret må sitte utenat, og det skal skrives ut i besvarelsen. Første linje i en ordensoppgave er «siden $\gcd(a,n)=1$, finnes ordenen» — det er en gratis begrunnelse, og instruksen på hvert eksamenssett er at alle svar skal begrunnes.

Praktisk: i eksamensoppgaver er $n$ oftest et primtall, og da er vilkåret oppfylt for alle $a$ som ikke er delelig med $n$. Men si det likevel.

Prosedyren for å finne $\operatorname{ord}_n(a)$ med penn og papir. Den må sitte utenat.

1. Sjekk $\gcd(a,n)=1$ og si det.
2. Regn $\phi(n)$ fra faktoriseringen av $n$ (kap. 2.1).
3. List alle divisorene av $\phi(n)$, i stigende rekkefølge.
4. Test dem stigende: regn $a^d\bmod n$ for hver divisor $d$, med kvadrer-og-multipliser. Den første som gir $1$, er ordenen — og fordi du gikk stigende, har du samtidig utelukket alle mindre.
5. Konkludér i ord: «Altså er $\operatorname{ord}_n(a)=d$, og ingen mindre eksponent gir $1$, siden ordenen må dele $\phi(n)$.»

Hvorfor du bare trenger teste divisorene: ordenen deler $\phi(n)$ (løkke 2). Det er den innsnevringen som gjør oppgaven regnbar — uten den måtte du testet alle $k$ fra $1$ til $\phi(n)$.

Arbeidsmengden er liten. $\phi(n)$ har typisk 4–8 divisorer, og potensene bygger på hverandre: har du $a^2$, får du $a^4$ ved én kvadrering. Under kode D er dette en oppgave på fem minutter.

Kontrollen: endte du på en $d$ som ikke deler $\phi(n)$, har du regnet feil — ordenen er alltid en divisor.

For primtallsmodulus: $\operatorname{ord}_p(a)\mid p-1$.

Utledes på stedet, én linje: Eulers teorem gir $a^{\phi(n)}\equiv 1$, og ordenslemmaet oversetter det til «ordenen deler $\phi(n)$».

Dette er den mest brukte konsekvensen i hele kapitlet, og den brukes på tre måter:

1. Som innsnevring: du trenger bare teste divisorene av $\phi(n)$ når du leter etter ordenen.
2. Som kontroll: fikk du en orden som ikke deler $\phi(n)$, har du regnet feil.
3. Som argument i bevis: «siden ordenen deler $\phi(n)=28$ og ikke er $1$, $2$, $4$, $7$ eller $14$, må den være $28$» — det er hele strukturen i en primitiv-rot-verifikasjon (kap. 5.2).

Merk at det ikke går andre veien. At $d\mid\phi(n)$ betyr ikke at det finnes et element av orden $d$ — men for primtallsmodulus gjør det faktisk det, og antallet er $\phi(d)$ (kap. 5.2).

Som eksamensoppgave: «Vis at $\operatorname{ord}_n(a)$ deler $\phi(n)$» er en bevisoppgave på fire linjer — ordenslemmaets $\Rightarrow$-retning pluss Eulers teorem. Den er verdt å kunne føre kaldt.

$$\{t\ge 1: a^t\equiv 1\pmod n\}=\{d,\ 2d,\ 3d,\ \dots\},\qquad d=\operatorname{ord}_n(a).$$

I klarspråk: eksponentene som «treffer $1$», ligger jevnt fordelt med avstand $d$. Ingen andre treffer.

Slik brukes det på eksamen, tre typiske spørsmål:

- «Finn alle $t\le 100$ med $a^t\equiv 1$.» Svar: multiplene av $d$ opp til $100$.
- «Er $a^{45}\equiv 1$?» Svar: ja nøyaktig når $d\mid 45$.
- «Gitt at $a^{12}\equiv 1$ og $a^{18}\equiv 1$ — hva kan du si om ordenen?» Svar: $d$ deler både $12$ og $18$, altså deler $d$ tallet $\gcd(12,18)=6$. Det er et grep verdt å kjenne: ordenen deler enhver eksponent som gir $1$, derfor deler den også deres gcd.

Og motsatt, den vanligste fellen: at $a^{12}\equiv 1$ betyr ikke at ordenen er $12$. Den er en divisor av $12$, og du må teste de mindre divisorene for å vite hvilken.

Kontrollregel: har du funnet at $a^d\equiv 1$ for en $d$, og $d\nmid\phi(n)$, er noe galt — for ordenen deler $\phi(n)$, og $d$ må være et multiplum av ordenen.

$$a^N\equiv a^{N\bmod d}\pmod n,\qquad d=\operatorname{ord}_n(a).$$

Utledes på stedet, to linjer: skriv $N=qd+r$ med $0\le r<d$ (divisjonsalgoritmen). Da er
$$a^N=(a^d)^q\cdot a^r\equiv 1^q\cdot a^r=a^r\pmod n.$$

Sammenlign med Euler-reduksjonen fra kap. 2.1, der du reduserte eksponenten modulo $\phi(n)$. Begge er riktige, men ordenen er minst mulig periode, og derfor gir den den kraftigste reduksjonen:

Hvorfor: desimalutviklingen av $\tfrac 1n$ gjentar seg etter $k$ siffer nøyaktig når $10^k\cdot\tfrac 1n$ og $\tfrac 1n$ har samme desimaldel, altså når $n\mid 10^k-1$, altså når $10^k\equiv 1\pmod n$. Den minste slike $k$ er ordenen.

Eksempler, alle etterprøvbare med divisjon:

$$\operatorname{ord}_n(a^k)=\frac{d}{\gcd(k,d)}.$$

Utledes på stedet, tre linjer. Sett $g=\gcd(k,d)$. Vi spør: hva er det minste $m\ge 1$ med $(a^k)^m\equiv 1$? Ved ordenslemmaet er $(a^k)^m=a^{km}\equiv 1$ nøyaktig når $d\mid km$. Skriv $d=g\,d'$ og $k=g\,k'$ med $\gcd(k',d')=1$. Da er
$$d\mid km\iff g d'\mid g k' m\iff d'\mid k'm\iff d'\mid m,$$
der siste steg bruker at $\gcd(k',d')=1$ (Euklids lemma). Det minste slike $m$ er $m=d'=d/g$. $\blacksquare$

To spesialtilfeller verdt å lese av med én gang:

- $\gcd(k,d)=1$: da er $\operatorname{ord}_n(a^k)=d$ — potensen har samme orden som $a$. Dette er nøkkelen til at alle primitive røtter er $r^k$ med $\gcd(k,\phi(n))=1$ (kap. 5.2).
- $k\mid d$: da er $\gcd(k,d)=k$ og $\operatorname{ord}_n(a^k)=d/k$ — en ryddig måte å lage et element av en ønsket orden.

Eksempel med tall. Modulo $17$ er $\operatorname{ord}_{17}(3)=16$. Da er
$$\operatorname{ord}_{17}(3^6)=\frac{16}{\gcd(6,16)}=\frac{16}{2}=8.$$
Kontroll: $3^6=729=42\cdot 17+15$, altså $3^6\equiv 15$, og $\operatorname{ord}_{17}(15)=8$ — som vi kan sjekke: $15\equiv -2$, så $15^2\equiv 4$, $15^4\equiv 16\equiv -1$, $15^8\equiv 1$ ✓.

Regelen bør sitte utenat for tempoets skyld, men den utledes på stedet i tre linjer om den glipper — og utledningen er verdt å kunne, for den er en typisk delpunkt-a i en bevisoppgave.

Orden $1$: $\operatorname{ord}_n(a)=1$ betyr $a^1\equiv 1$, altså $a\equiv 1\pmod n$. Det er nøyaktig ett slikt element.

Orden $2$: $\operatorname{ord}_n(a)=2$ betyr $a^2\equiv 1$ men $a\not\equiv 1$. For primtallsmodulus $p$ har $x^2\equiv 1$ nøyaktig to løsninger, $x\equiv\pm 1$ (kap. 4.1), så det er nøyaktig ett element av orden $2$, nemlig
$$a\equiv -1\equiv p-1\pmod p.$$

Praktisk konsekvens — snarveien du bruker hele tiden: lander en potens på $-1$, er ordenen det dobbelte av eksponenten:
$$a^m\equiv -1\pmod p\ \Longrightarrow\ \operatorname{ord}_p(a)=2m.$$
Utledningen er to linjer: $a^{2m}\equiv 1$, så ordenen deler $2m$; og ordenen deler ikke $m$ (for $a^m\equiv -1\not\equiv 1$), så den må være $2m$ selv eller en divisor av $2m$ som ikke deler $m$ — og for $m$ en toerpotens er $2m$ den eneste. (For generell $m$ gir argumentet at ordenen deler $2m$ men ikke $m$; det holder til å utelukke halvparten av divisorene, og resten testes.)

Merk at det er annerledes for sammensatt modulus. Modulo $8$ har $x^2\equiv 1$ fire løsninger ($1,3,5,7$), så det er tre elementer av orden $2$. Det er en av grunnene til at primtallsmoduler er så mye ryddigere, og til at primitive røtter ikke finnes for alle $n$ (kap. 5.2).

Ordenen skrives $\operatorname{ord}_n(a)$, alltid med modulusen som indeks.

Hvorfor indeksen er obligatorisk: samme tall har ulik orden modulo ulike $n$. For $a=2$:

Utledes på stedet, to linjer: ved Eulers teorem er $a^{\phi(n)}\equiv 1\pmod n$ når $\gcd(a,n)=1$. Altså er mengden
$$\{k\ge 1: a^k\equiv 1\pmod n\}$$
ikke tom. En ikke-tom mengde av positive hele tall har et minste element, og det minste elementet er ordenen. $\blacksquare$

Argumentet «en ikke-tom mengde av positive hele tall har et minste element» heter velordningsprinsippet, og det er samme prinsipp som ligger under induksjon (kap. 6.2) og under termineringen av Euklids algoritme (kap. 1.2).

Hvorfor kortet er verdt en plass i bunken: «vis at ordenen finnes» er en tenkelig delpunkt-a, og den koster to linjer når du har argumentet klart. Uten Eulers teorem har du ingenting å si.

Og merk at $\gcd(a,n)=1$ er nødvendig her: uten den gjelder ikke Eulers teorem, mengden er tom, og ordenen finnes ikke.

Arbeidsbesparelser du bør bruke:

- Bygg potensene på hverandre. Har du $a^2$, får du $a^4$ ved én kvadrering.
- Se etter $-1$. Lander en potens på $-1$, er ordenen det dobbelte av den eksponenten.
- Stopp ved første $1$. Alle større divisorer gir også $1$ — de er multipler av ordenen.

Kontroller:

- Deler svaret $\phi(n)$? (Det må det.)
- Er $a^{\phi(n)}\equiv 1$? (Eulers teorem krever det.)

Kjør den nå, på $\operatorname{ord}_{19}(4)$ og $\operatorname{ord}_{23}(2)$, uten å se på oppskriften. (Svar: $\phi(19)=18$ med divisorer $1,2,3,6,9,18$; $4^9=(2^2)^9=2^{18}\equiv 1$, og $4^3=64\equiv 7$, $4^2=16$, så ordenen er $9$. For $23$: $\phi=22$, divisorer $1,2,11,22$; $2^{11}=2048=89\cdot 23+1$, så ordenen er $11$.)