Appendix B - Mersenne-priemgetallen

Fermat's Kleine Stellling  ][  Mersenne-priemgetallen


De Kleine Stelling van Fermat

Stelling (Kleine stelling van Fermat)
ALS p is een priemgetal dat niet deelbaar is op het gehele getal a, DAN a(p-1) º 1 (mod p)

Bewijs
We bekijken de rij bestaande uit (p - 1) positieve veelvouden van het getal a:
   a, 2a, 3a, ... , (p - 1)a
Stel nu dat
   ra º sa (mod p)
Dan geldt ra = mp + R en sa = np + R (R is hier de rest bij deling door p)
Waaruit (r - s) a = (m - n) p.
Dus p is deelbaar op r - s; met andere woorden r - s º 0 (mod p) of r º s (mod p).
De hierboven staande p - 1 veelvouden van a zijn dus alle verschillend. Ze moeten dus alle congruent zijn met
   1, 2, 3, ..., p-1
in een of andere volgorde. Vermenigvuldigen we beide series, dan hebben we dus
   a · 2a · 3a · ... · (p - 1) a º 1 · 2 · 3 · ... · (p - 1) (mod p)
Of beter
   a(p-1) · (p - 1)! º (p - 1)! (mod p)
Deling van beide leden door (p-1)! geeft dan het gewenste resultaat. ¨

Opmerkingen
[1]
De Kleine stelling van Fermat wordt ook wel eens in de volgende vorm weergeven.

Gevolg (van de Kleine stelling van Fermat)
ALS p is een priemgetal en a is een willekeurig geheel getal, DAN ap = a (mod p)

Bewijs
Als p deelbaar is op a, dan is het resultaat triviaal (beide kanten zijn gelijk aan 0).
Als p niet deelbaar is op a, volstaat het beide kanten van de congruentie in de Kleine stelling van Fermat met a te vermenigvuldigen om het gewenste resultaat te krijgen. ¨

Ter toelichting van dit laatste een getallenvoorbeeld (in Maple):

Voorbeeld

> restart:
> p:=23: a:=48:
> (a^p) mod p = a mod p;
2 = 2

[2]
Voor een ander bewijs van de Kleine stelling van Fermat zie de pagina "Congruenties"
[einde Opmerkingen


begin pagina
[mersenne_b.htm] laatste wijziging op: 30-11-2002