Fermats lille teorem

Fermats lille teorem sier at hvis p er et primtall, så vil for hvilket som helst heltall a

 

når det uttrykkes ved modulær aritmetikk. Det betyr at om man tar et tall a, multipliserer det med seg selv p ganger og subtraherer a, så er resultatet delbart med p.  Teoremet ble etablert av Pierre de Fermat rundt 1636. Det  kalles hans lille teorem for å skille det fra Fermats store teorem.

For eksempel, for  p = 3 og a = 6 finner man at 63 -  6 = 210  som er delelig med 3. Hvis primtallet p er stort, er teoremet mer kraftfullt.
 
Når a i tillegg er relativt primisk med p, kan teoremet skrives som

 

En enkel illustrasjon er å velge  p = 5 og a = 7. Da er 74 = 2401 = 5×480 + 1 som viser at det er oppfylt.

Fermat ga ikke noe bevis for teoremet. Det gjorde først Leibniz noen tiår senere i et brev til en kollega. Euler ga sitt eget bevis i 1736 og publiserte noen år senere en viktig  generalisering til ikke-primiske tall p. Det opprinnelige teoremet ble først kalt Fermats lille teorem i boken Zahlentheorie av Kurt Hensel som kom ut i 1913.

Bevis
Det lille teoremet til Fermat kan bevises på flere måter. Mest direkte kan man benytte at p - 1 av restklassene modulo p til et tall a danner en syklisk gruppe når p er et primtall som ikke er en faktor i a. 

En annen mulighet er å betrakte tallene

 

som alle er forskjellige. De vil være kongruente modulo p til tallene 1, 2, 3, ... , p - 1, men generelt opptre i en annen rekkefølge. Hvis man så multipliserer dem sammen, må man derfor ha

 

der (p - 1)! = 1⋅2⋅... ⋅(p - 1). Men dette er samtidig verdien av produktet på venstresiden modulo p. Derfor må man ha

 

som er innholdet av teoremet.

Eulers teorem

Når man betrakter modulær aritmetikk med en modulus n som ikke er et primtall, vil hvert tall a i settet {1, 2, 3, ..., n - 1} som er relativt primisk til n, utgjøre en restklasse a. Antall slike tall er gitt ved Eulers totientfunksjon φ(n). De tilsvarende restklassene utgjør en abelsk gruppe (Z/nZ)× med 1 som multiplikativt enhetselement.

Denne gruppen inneholder i alt φ(n) element. Da den er abelsk, sier Lagranges teorem at for hvert element a vil

 

Dette er en form av Eulers teorem. Skrevet som en kongruensrelasjon, vil det tilsvare den ekvivalente måten

 

der tallene a og n ikke har noen felles faktorer. I det spesielle tilfellet at n er et primtall, vil φ(n) =  n - 1 og teoremet går over til Fermats lille teorem.

Som et eksempel kan man betrakte modulus n = 14. De relativt primiske tallene er da {1, 3, 5, 9, 11, 13} som definerer de seks restklassene som utgjør gruppen. Dette antall  element  stemmer med at φ(14) = 14(1 - 1/2)⋅(1 - 1/7) = 6. Hvis man så velger å betrakte elementet 9, vil man ha 92 = 11 da 92 = 81  ≡ 11 (mod 14) slik at 94 = 9 på samme måte. Det betyr at 96 = 9⋅11 = 1 i overensstemmelse med teoremet.

RSA-kryptering

For at Alice skal kunne motta hemmelige meldinger fra Bob ved RSA-kryptering, finner hun to store primtall p og q og danner produktet n = pq. Dette tallet blir gjort offentlig sammen med et annet tall e. De to tallene n og e utgjør den offentlige nøkkelen til Alice. Samtidig beregner hun et tall d som oppfyller

 

Da primtallene  p og q er forskjellige, er φ(n) = φ(pq) = φ(p)⋅φ(q) = (p - 1)⋅(q - 1). Dette tallet d er den private nøkkelen som hun beholder.

Når Bob skal sende en melding til Alice, omformer han denne først til et tall x. Den krypterte meldingen beregnes så ved

 

og sendes avgårde til Alice. Hun kan da dekryptere den ved beregningen

 

Det fungerer fordi  hvor   for et eller annet heltall k. Derfor er

 

da Eulers teorem sier at .

Referanser

Eksterne lenker

 E.W. Weisstein, Fermat's Little Theorem, Wolfram MathWorld

Tallteori