Appendix B - Mersenne-priemgetallen
Fermat's Kleine Stellling ][ Mersenne-priemgetallen
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