Fermats lille teorem

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

a^{p}\equiv a\ (\operatorname {mod} \ p)

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 6³ - 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

a^{p-1}\equiv 1\;(\operatorname {mod} \ p)

En enkel illustrasjon er å velge p = 5 og a = 7. Da er 7⁴ = 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

m_{1}=a,\;m_{2}=2a,\;m_{3}=3a,\ldots ,m_{p-1}=(p-1)a

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

m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p-1}=(p-1)!a^{p-1}

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

a^{p-1}\equiv 1\;(\operatorname {mod} \ p)

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

\mathbf {a} ^{\phi (n)}=\mathbf {1}

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

a^{\phi (n)}\equiv 1{\pmod {n}}

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 9² = 11 da 9² = 81 ≡ 11 (mod 14) slik at 9⁴ = 9 på samme måte. Det betyr at 9⁶ = 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

ed\equiv 1\;\;\;({\text{mod}}\;\phi (n))

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

y\equiv x^{e}{\pmod {n}}

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

x\equiv y^{d}{\pmod {n}}

Det fungerer fordi $y^{d}\equiv x^{ed}\;\;({\text{mod}}\;n)$ hvor $ed=1+k\phi (n)$ for et eller annet heltall k. Derfor er

x^{ed}=x^{1+k\phi (n)}=xx^{k\phi (n)}\equiv x\;\;({\text{mod}}\;n)

da Eulers teorem sier at $x^{\phi (n)}\equiv 1\;\;({\text{mod}}\;n)$ .

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.