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. O. Ore, Number Theory and its History, Dover Publications, New York (1988). ISBN 0-486-65620-9.

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. C.B. Boyer, A History of Mathematics, Princeton University Press, New Jersey (1985). ISBN 0-691-02391-3.

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. R. Courant and H. Robbins, What is Mathematics: An Elementary Approach to Ideas and Methods, Oxford University Press, Oxford (1996). ISBN 978-0-19-510519-3. 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. S. Singh, The Code Book, Random House, New York (1999). ISBN 0-385-49532-3.

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

Kategori:Tallteori