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