2.2 Fermats lille teorem

Form 1, $a^{p-1}\equiv 1\pmod p$, krever at $p$ ikke deler $a$.

Hvorfor det er samme krav som Eulers $\gcd(a,p)=1$: et primtall har bare divisorene $1$ og $p$, så $\gcd(a,p)$ er antingen $1$ eller $p$. Den er $p$ nøyaktig når $p\mid a$. Derfor er «$p\nmid a$» og «$\gcd(a,p)=1$» to måter å si det samme.

Sjekken er triviell, og skal likevel stå. Er $p=13$ og $a=5$, er $13\nmid 5$ — én setning. Er $a$ større enn $p$, reduser først: $a=1729$ og $p=7$ gir $1729=7\cdot 247$, altså $7\mid a$, og form 1 gjelder ikke.

Hva som skjer når vilkåret svikter: $a^{p-1}\equiv 0\pmod p$, ikke $1$. Se kortet «Når p deler grunntallet».

Form 2 har ingen vilkår — bruk den når du ikke vet noe om $a$.

$$\phi(p)=p-1\quad\Longrightarrow\quad a^{\phi(p)}=a^{p-1}\equiv 1\pmod p\qquad(\gcd(a,p)=1).$$

Dette utledes på stedet, og det er verdt å skrive de to linjene i besvarelsen når du bruker Fermat første gang i en oppgave: det viser at du vet hvorfor reduksjonen er lovlig, ikke bare at den er tillatt.

Merk retningen. Euler er det generelle teoremet, Fermat spesialtilfellet. Du kan altså ikke utlede Euler fra Fermat — og du kan ikke bruke Fermat på en sammensatt modulus. Prøver du med $n=15$ og $a=2$: $2^{14}=16\,384=15\cdot 1092+4$, altså $2^{14}\equiv 4\pmod{15}$, ikke $1$. (Riktig eksponent her er $\phi(15)=8$: $2^8=256\equiv 1$ ✓.)

Praktisk konsekvens: første spørsmål i en restberegning er alltid «er modulusen et primtall?». Er den det, er du i Fermat-sporet og sparer faktoriseringen.

Dette må sitte utenat, og det er den formen du bruker i delelighetsbevis (sjanger I).

Hvorfor den ikke trenger vilkår — utledningen i to linjer, som du skal kunne skrive:

- Er $p\nmid a$: gang form 1 med $a$: $a\cdot a^{p-1}\equiv a\cdot 1$.
- Er $p\mid a$: begge sider er $\equiv 0\pmod p$.

Case-analysen dekker alle $a$, så påstanden gjelder uten unntak. $\blacksquare$

En annen måte å si det: $p\mid(a^p-a)$ for alle $a$. Den formen er ofte det oppgaven ber om — «vis at $a^5-a$ er delelig med $5$ for alle hele tall $a$» er nøyaktig form 2 med $p=5$.

Merk at det virkelig kreves at $p$ er et primtall. Med $n=4$: $2^4=16$ og $16-2=14$, som ikke er delelig med $4$.

Del eksponenten på $p-1$ og behold resten. Regelen må sitte utenat, og utledningen over er den du skriver i besvarelsen.

Merk at det er $p-1$, ikke $p$. Dette er den mest belagte regnefeilen i sjangeren. Minnekroken: hjulet har $p-1$ hakk, fordi restklassen $0$ ikke er med i løkken — den kommer man aldri tilbake fra.

Malen for hele oppgaven er den samme som i kap. 2.1, med to forenklinger: faktoriseringen i steg (i) er trivielt («$p$ er et primtall»), og $\phi$ i steg (iii) er $p-1$ uten regning. Steg (ii), $\gcd$-sjekken, står fortsatt — den er her «$p\nmid a$».

Blir $r=0$? Da er $a^N\equiv 1$. Det er riktig svar.

Det ene spørsmålet som avgjør hvilket teorem du er i. Under kode D må du svare på det selv, uten primtallstabell.

Prøvedivisjon, med stopp ved kvadratrota (kap. 1.1): del på $2,3,5,7,11,13,\dots$ opp til $\sqrt n$. Går ingen opp, er $n$ et primtall.

Primtallene du møter oftest i sjanger E — verdt å kjenne igjen, ikke som tabell, men fordi de går igjen: $7,11,13,17,19,23,29,31,37,41,43,47$, og de tresifrede $101,103,107,109,113$.

Rask utelukking før du deler: er tallet like, eller ender på $5$, er det ikke et primtall (bortsett fra $2$ og $5$). Er siffersummen delelig med $3$, er tallet delelig med $3$.

Eksempel: er $91$ et primtall? Ikke like, siffersum $10$, ender ikke på $0$ eller $5$; $91/7=13$ ✓ — altså $91=7\cdot 13$, sammensatt. Her skal $\phi(91)=6\cdot 12=72$ brukes, ikke $90$.

Fellen $91$ er ekte: den ser ut som et primtall, og $n-1=90$ ser brukbart ut. Sjekk alltid $7$ og $13$ på tosifrede og tresifrede tall.

Utledes på stedet, én linje: $a=ps$ gir $a^k=p^ks^k$, som er delelig med $p$. $\blacksquare$

Hva du gjør i praksis: ingenting mer. Svaret er $0$, og oppgaven er ferdig. Det er den enkleste restberegningen som finnes — men bare hvis du sjekker vilkåret først. Hopper du rett til reduksjon modulo $p-1$, får du et galt svar med et helt riktig utseende.

Merk at form 2 fortsatt holder: $a^p\equiv a\pmod p$ blir $0\equiv 0$, som er sant. Det er hele grunnen til at form 2 er den vilkårsfrie.

Eksempel: $14^{12}\bmod 7$. Her er $7\mid 14$, så $14\equiv 0$ og $14^{12}\equiv 0\pmod 7$. Hadde du redusert $12$ modulo $6$ og fått $14^{0}=1$, ville svaret vært galt.

Er grunntallet større enn modulusen, reduser det først. Det er lovlig etter potensregelen for kongruenser (kap. 1.4), og det gjør vilkårssjekken synlig.

Eksempel: $105^{40}\bmod 7$. Reduser: $105=7\cdot 15$, så $105\equiv 0\pmod 7$, og hele potensen er $\equiv 0$. Uten reduksjonen ville du kanskje ikke sett at $7$ deler $105$.

Og et der vilkåret holder: $102^{40}\bmod 7$. Her er $102=7\cdot 14+4$, så $102\equiv 4\pmod 7$, og oppgaven er blitt $4^{40}\bmod 7$. Fermat: $40=6\cdot 6+4$, så $4^{40}\equiv 4^{4}=256\equiv 4\pmod 7$ (siden $256=7\cdot 36+4$).

Rekkefølgen som forebygger feil:

1. reduser grunntallet modulo $p$;
2. se om resultatet er $0$ — da er du ferdig;
3. ellers reduser eksponenten modulo $p-1$.

Merk at små grunntall også gjør kvadrattabellen lettere. $4^2=16$ er enklere enn $102^2=10\,404$.

Dette utledes på stedet, én linje:
$$a\cdot a^{p-2}=a^{p-1}\equiv 1\pmod p$$
fra Fermats lille teorem — og det er nøyaktig definisjonen av invers (kap. 1.4). $\blacksquare$

Eksempel: inversen til $5$ modulo $13$ er $5^{11}\bmod 13$. Med kvadrer-og-multipliser: $5^2=25\equiv 12\equiv -1$, så $5^{4}\equiv 1$, $5^{8}\equiv 1$, og $5^{11}=5^{8}\cdot 5^{2}\cdot 5\equiv 1\cdot(-1)\cdot 5=-5\equiv 8\pmod{13}$. Kontroll: $5\cdot 8=40=39+1\equiv 1$ ✓.

Når er dette raskere enn Euklids algoritme? Nesten aldri for hånd — Euklid tar to eller tre divisjonslinjer. Begge metodene er fullgode, men Euklid er standardveien i dette faget, og den virker også for sammensatt modulus.

Der formelen likevel er den rette: i bevis og i algebraiske omskrivninger, der du vil skrive inversen som en potens og ikke som et tall. Og i Wilson-trikset i kap. 2.3, der du deler på et tall modulo $p$.

$$p-1\equiv -1,\qquad p-2\equiv -2,\qquad p-3\equiv -3\pmod p.$$

Hvorfor det hjelper: $(-1)^k$ er $1$ eller $-1$ avhengig av pariteten, og små negative tall kvadreres like lett som små positive. Ser du at $a^k\equiv -1$, er $a^{2k}\equiv 1$ — og da er hele resten av regningen kort.

Eksempel: $3^{8}\equiv 16\pmod{17}$, og $16\equiv -1$. Dermed er $3^{16}\equiv 1$ (som Fermat lovte), og $3^{9}\equiv -3\equiv 14\pmod{17}$.

Konverter tilbake til slutt. Sluttsvaret skal normalt være i $0,\dots,p-1$: skriv $-3\equiv 14\pmod{17}$, ikke bare $-3$. Spørres det om «resten», er resten et tall mellom $0$ og $p-1$.

Dette grepet er selve Wilson-trikset i kap. 2.3, der faktorene $p-1,p-2,\dots$ skrives som $-1,-2,\dots$. Å bli vant til det nå er direkte forberedelse.

Utledes på stedet, tre linjer. Fra definisjonen er
$$k!\,(p-k)!\,\binom{p}{k}=p!.$$
Høyresiden er delelig med $p$. Venstresiden har faktorene $k!$ og $(p-k)!$, som er produkter av tall mellom $1$ og $p-1$ — og etter Euklids lemma (kap. 1.1) kan primtallet $p$ ikke dele et slikt produkt, siden det ikke deler noen av faktorene. Altså må $p$ dele $\binom{p}{k}$. $\blacksquare$

Kontroll for $p=5$: $\binom51=5$, $\binom52=10$, $\binom53=10$, $\binom54=5$ — alle delelige med $5$ ✓. Og merk at $\binom50=\binom55=1$ ikke er det; derfor kravet $0<k<p$.

Merk at $p$ må være et primtall. For $p=4$: $\binom42=6$, som ikke er delelig med $4$. Det er Euklids lemma som svikter, og det er presis der primtallsegenskapen brukes.

Hvor det brukes: i induksjonsbeviset for $a^p\equiv a$ under, og i delelighetsbevis i Del 6.

(1) Basissteg: $a=0$ gir $0^p=0\equiv 0\pmod p$ ✓.

(2) Induksjonshypotese: anta at $a^p\equiv a\pmod p$ for en $a\ge 0$.

(3) Induksjonssteg: binomialformelen gir
$$(a+1)^p=\sum_{k=0}^{p}\binom{p}{k}a^{k}=a^{p}+\binom{p}{1}a^{p-1}+\dots+\binom{p}{p-1}a+1.$$
Alle mellomleddene har en faktor $\binom pk$ med $0<k<p$, og de er delelige med $p$ etter forrige kort. Altså
$$(a+1)^p\equiv a^{p}+1\pmod p.$$
Her bruker vi induksjonshypotesen: $a^p\equiv a$, så
$$(a+1)^p\equiv a+1\pmod p.$$
Dermed holder påstanden for $a+1$, og ved induksjon for alle $a\ge 0$. $\blacksquare$

Negative $a$: hvert negativt tall er kongruent med et ikke-negativt modulo $p$ (legg til et multiplum av $p$), og påstanden avhenger bare av restklassen. Så resultatet gjelder for alle hele tall.

Begge bevisveier er fullgode. Euler-veien er kortest; induksjonsveien er den du bruker hvis oppgaven ber om et induksjonsbevis, eller hvis den ber deg vise Fermat uten å bruke Eulers teorem. Legg merke til at hypotesen brukes ett bestemt sted, og at stedet er markert — det er et krav i dette faget.

Den omvendte påstanden er ikke sann. At $a^{n-1}\equiv 1\pmod n$ beviser ikke at $n$ er et primtall.

Moteksempel: $n=341=11\cdot 31$ er sammensatt, men
$$2^{340}\equiv 1\pmod{341}.$$
Slike tall kalles Fermat-pseudoprimtall (til grunntallet $2$).

Verre: $n=561=3\cdot 11\cdot 17$ oppfyller $a^{560}\equiv 1\pmod{561}$ for alle $a$ med $\gcd(a,561)=1$. Tall med den egenskapen kalles Carmichael-tall, og de finnes det uendelig mange av.

Hva testen faktisk er god for: å bevise at et tall ikke er et primtall. Finner du én $a$ med $a^{n-1}\not\equiv 1\pmod n$, er $n$ sammensatt — og du har bevist det uten å faktorisere. Det er en logisk kontrapositiv, og den er helt gyldig.

Merk retningen når du skriver: «$n$ primtall $\Rightarrow$ $a^{n-1}\equiv 1$» er teoremet. Å bruke pilen baklengs er en logisk feil, ikke bare en unøyaktighet.

RSA-korrektheten $(m^e)^d\equiv m\pmod n$ hviler på Euler når $\gcd(m,n)=1$. Men når meldingen $m$ er delelig med $p$ eller $q$, svikter Euler-argumentet — og da er det Fermat, i form 2, som redder beviset.

Skissen: $n=pq$. Vis at $m^{ed}\equiv m$ modulo $p$ og modulo $q$ hver for seg, og sett sammen med splittingsregelen (formelt: det kinesiske restteoremet, kap. 2.4).

Modulo $p$ er det to tilfeller:

- $p\nmid m$: Fermat form 1 gir $m^{p-1}\equiv 1$, og siden $(p-1)\mid\phi(n)$ følger $m^{ed}=m^{1+k\phi(n)}\equiv m$.
- $p\mid m$: begge sider er $\equiv 0\pmod p$, så påstanden holder trivielt — og det er nøyaktig det form 2 sier.

Derfor gjelder RSA for ALLE meldinger, ikke bare de som er relativt primiske til $n$. Det er et poeng en oppgave kan spørre om (sjanger D), og det er et sted der form 2 er uunnværlig. Hele argumentet føres ut i kap. 3.1.

Hva det betyr for regningen din nå: ordenen kan være mindre enn $p-1$, og oppdager du det, blir regningen kortere. I eksempel 3 så vi $5^2\equiv -1\pmod{13}$, altså $5^4\equiv 1$ — ordenen er $4$, ikke $12$.

Men reduksjonen modulo $p-1$ er riktig uansett. Du taper ingenting ved å bruke $p-1$; du sparer bare tid hvis du ser en mindre eksponent.