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.

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

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

En enkel illustrasjon er å velge  *p* = 5 og *a* = 7. Da er 74 = 2401 = 5&times;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&sdot;2&sdot;... &sdot;(*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 *&phi;*(*n*). De tilsvarende restklassene utgjør en abelsk gruppe (**Z**/*n***Z**)&times; med **1** som multiplikativt enhetselement.

Denne gruppen inneholder i alt *&phi;*(*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 *&phi;*(*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 *&phi;*(14) = 14(1 - 1/2)&sdot;(1 - 1/7) = 6. Hvis man så velger å betrakte elementet **9**, vil man ha **9**2 = **11** da 92 = 81  ≡ 11 (mod 14) slik at **9**4 = **9** på samme måte. Det betyr at **9**6 = **9**&sdot;**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 *&phi;*(*n*) = *&phi;*(*pq*) = *&phi;*(*p*)&sdot;*&phi;*(*q*) = (*p* - 1)&sdot;(*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) .

## Referanser


## Eksterne lenker

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