© h.hofstede (h.hofstede@hogeland.nl)

De kleine stelling van Fermat.
       

Als p een priemgetal is, dat niet in de ontbinding van a voorkomt, dan geldt:

ap - 1 ☰ 1  (mod p)

       
Bewijs.
  Bekijk de rij  a, 2a, 3a, ..., (p - 1)a
Twee getallen uit die rij zijn nooit aan elkaar gelijk (mod p)
Immers als  ma = na (mod p)  dan is  (m - n)a = 0  (mod p) en omdat p geen deler is vanzou p dan een deler zijn van  (m - n). Maar dat kan niet, want p > (m - n).

Dus zijn alle resten van die getallen modulo p ongelijk aan elkaar.
Die resten zijn dus (op volgorde gezet) precies de getallen   1, 2, 3, ..., (p - 1)
Als je nu al die getallen met elkaar vermenigvuldigt, dan krijg je:
a • 2a • 3a •  ... • (p - 1)aap - 1 • (p - 1)!

Maar als je alle resten vermenigvuldigt dan krijg je  (p - 1)!
Dus moet gelden   ap - 1 • (p - 1)!  ☰ (p - 1)! (mod p)
Daaruit volgt direct de stelling.
q.e.d.  
       
De kleine stelling van Fermat maakt het mogelijk om snel en efficiënt machten modulo p te bepalen.
Stel bijvoorbeeld dat je wilt weten hoe groot  3201  mod 11  is.
Fermat geeft  310 ☰ 1  (mod 11), want 11 komt niet voor in de ontbinding van 3
3200 = (310)20 = 120 = 1
3201 = 3200 • 3 = 1 • 3 = 3
       
Een direct gevolg van de kleine stelling van Fermat zie je als je beide kanten met a vermenigvuldigt:
       

ap  ☰  a  (mod p)

       
Orde.
       
Het kleinste gehele getal n > 0 waarvoor geldt dat  an ☰ 1 (mod b)  noemen we de  "orde van a modulo b".
We noteren dat voortaan als  n = ordb(a).
Wanneer bestaat er eigenlijk een orde?  Dat zegt de volgende stelling:
       

a heeft een orde modulo b   ⇔  ggd(a, b) = 1

       
Bewijs.
  Als a orde b heeft,  dan bestaat er dus een getal n zodat an ☰ 1  (mod b)
Maar   an (mod b) (a (mod b)n  en als dat 1 (mod b) is, dan is ook  a (mod b) ☰ 1
 
Als ggd(a, b) = 1
q.e.d.  
       
Een gevolg daarvan is, dat als n = ordb(a) dan is  ak ak + n  , en n is het kleinste getal waarvoor dit geldt.
In dat geval is de rij van alle resten van  ak (mod b) periodiek met periode n.
Bekijk bijvoorbeeld de resten bij b = 13 en a = 5 :
51 , 52, 53 , 54 , 55,  56,  57,  58, .... 
geeft   5, 12, 8, 1, 5, 12, 8, 1, ...  en die is periodiek met periode ord13(5) = 4
(Bij die eerste 1 in de rij hadden we natuurlijk direct kunnen stoppen, immers als 54 (mod 13) ☰ 1 dan is  55 ☰ 54 • 5 ☰ 1 • 5 = 5, en dan is  56 ☰ 52,  57 ☰ 53 enz.)
Hé grappig; dan kun  je nu je weet dat de orde 4 is, ook op een andere manier de inverse van 5 (mod 13)  berekenen:
5-1 ☰ 5-1 + 4 ☰ 53 ☰ 8  en inderdaad is  8 • 5 ☰ 40 ☰ 1

De vergelijking  am = 1  (mod b)  geldt dus alleen als ordb(a) een deler is van m, immers op die plaatsen kwamen de enen in het rijtje met resten.
En am = an  (mod b)  kan dus om dezelfde reden alleen als  m =(mod b).  
Dat heeft het volgende gevolg:
 

als ggd(ordn(a), ordn(b)) = 1 dan geldt:

 ordn(ab) = ordn(a) • ordn(b)

       
Deze beschouwingen over de orde kunnen we natuurlijk mooi combineren met de kleine stelling van Fermat:
       

Voor elk priemgetal p geldt dat ordp(a) een deler is van (p - 1)

       
Immers Fermat zegt dat  ap - 1 ☰ 1 (mod p)  en hierboven zagen we dat   am = 1  (mod p)  alleen geldt  als ordp(a) een deler is van m.
       
Stelling van Euler.
       
't Is natuurlijk een beetje jammer dat de kleine stelling van Fermat alleen maar geldt voor priemgetallen.  De stelling van Euler geeft een soortgelijke eigenschap voor samengestelde getallen.
Komt 'íe:
       

Als ggd(a, b) = 1  dan geldt:

a
φ(b) = 1  (mod b)
 

       
Uiteraard weer voor gehele a en b en  b > 0.

Die  φ  is de  totiëntfunctie uit deze les.  Snel gezegd: het aantal getallen onder b dat geen priemfactor met b gemeenschappelijk heeft.

Ik hoop dat je ziet dat deze stelling eigenlijk een uitbreiding van de kleine stelling van Fermat is:  neem voor b een priemgetal dan geldt  φ(b) = b - 1, immers alle getallen onder b zijn dan copriem met b, en dan staat er gewoon de kleine stelling van Fermat.

Uit deze stelling volgt dan direct weer dat  ordb(a) een deler is van  φ(b).

       

© h.hofstede (h.hofstede@hogeland.nl)