Fermats lille teorem
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bd/Pierre_de_Fermat_%28F._Poilly%29.jpg/240px-Pierre_de_Fermat_%28F._Poilly%29.jpg)
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.[1]
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.[2]
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.[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.[1]
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.[4]
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
- ^ a b O. Ore, Number Theory and its History, Dover Publications, New York (1988). ISBN 0-486-65620-9.
- ^ C.B. Boyer, A History of Mathematics, Princeton University Press, New Jersey (1985). ISBN 0-691-02391-3.
- ^ 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.
- ^ S. Singh, The Code Book, Random House, New York (1999). ISBN 0-385-49532-3.
Eksterne lenker
- E.W. Weisstein, Fermat's Little Theorem, Wolfram MathWorld