Fermats lille teorem

Pierre de Fermat, 1601 - 1665.

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.

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.

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. 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.

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.

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)$.

Eksterne lenker

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