Fermats lille teorem

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

  
    
      
        
          a
          
            p
          
        
        ≡
        a
         
        (
        mod
        ⁡
         
        p
        )
      
    
    {\displaystyle 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
          
        
        ≡
        1
        
        (
        mod
        ⁡
         
        p
        )
      
    
    {\displaystyle a^{p-1}\equiv 1\;(\operatorname {mod} \ p)}
  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.


== 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
          
        
        =
        2
        a
        ,
        
        
          m
          
            3
          
        
        =
        3
        a
        ,
        …
        ,
        
          m
          
            p
            −
            1
          
        
        =
        (
        p
        −
        1
        )
        a
      
    
    {\displaystyle 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
          
        
        ⋅
        
          m
          
            2
          
        
        ⋅
        …
        ⋅
        
          m
          
            p
            −
            1
          
        
        =
        (
        p
        −
        1
        )
        !
        
          a
          
            p
            −
            1
          
        
      
    
    {\displaystyle 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
          
        
        ≡
        1
        
        (
        mod
        ⁡
         
        p
        )
      
    
    {\displaystyle 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

  
    
      
        
          
            a
          
          
            ϕ
            (
            n
            )
          
        
        =
        
          1
        
      
    
    {\displaystyle \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
          
            ϕ
            (
            n
            )
          
        
        ≡
        1
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle 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 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

  
    
      
        e
        d
        ≡
        1
        
        
        
        (
        
          mod
        
        
        ϕ
        (
        n
        )
        )
      
    
    {\displaystyle 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
        ≡
        
          x
          
            e
          
        
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle y\equiv x^{e}{\pmod {n}}}
  og sendes avgårde til Alice. Hun kan da dekryptere den ved beregningen

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

  
    
      
        
          x
          
            e
            d
          
        
        =
        
          x
          
            1
            +
            k
            ϕ
            (
            n
            )
          
        
        =
        x
        
          x
          
            k
            ϕ
            (
            n
            )
          
        
        ≡
        x
        
        
        (
        
          mod
        
        
        n
        )
      
    
    {\displaystyle x^{ed}=x^{1+k\phi (n)}=xx^{k\phi (n)}\equiv x\;\;({\text{mod}}\;n)}
  da Eulers teorem sier at 
  
    
      
        
          x
          
            ϕ
            (
            n
            )
          
        
        ≡
        1
        
        
        (
        
          mod
        
        
        n
        )
      
    
    {\displaystyle x^{\phi (n)}\equiv 1\;\;({\text{mod}}\;n)}
  .


== Referanser ==


== Eksterne lenker ==
E.W. Weisstein, Fermat's Little Theorem, Wolfram MathWorld