Appendix D - Mersenne-priemgetallen

Wat theorie | Andere stellingen ][ Mersenne-priemgetallen

NB.
Op deze pagina wordt in de bewijzen gebruik gemaakt van enkele resultaten uit de theorie der Congruenties en uit die der Kwadraatresten.

1. Wat theorie
Om de stellingen in de volgende paragraaf te kunnen bewijzen, hebben we nog wat andere stellingen uit de Getallentheorie nodig

In het onderstaande is a steeds een positief geheel getal, terwijl "|" betekent "is deelbaar op" en (a,b) = 1 betekent "de ggd van a en b is gelijk aan 1" (in dit geval heten de getallen a en b ook wel relatief priem of ook wel onderling ondeelbaar).

Stelling 1
ALS (a,m) = 1 en r is de orde van a (mod m), DAN aⁿ º 1 (mod m) DESDA r | n.

Opmerking
Een bewijs van deze (en de volgende stelling) staat op de pagina "Congruenties en restklassen".
[einde Opmerking]

Een gevolg van deze stelling is dan

Stelling 2
ALS r is de orde van a (mod m), DAN r | f(m) (hierin is f(m) de indicator van Euler).

Met als

Gevolg
ALS (a,p) = 1 en p is een priemgetal, DAN is de orde r van a (mod) p deelbaar op p - 1.

Bewijs:
Voor p is priem geldt f(p) = p - 1. Immers het aantal getallen m kleiner of gelijk aan p met (m, p) = 1 is gelijk aan p - 1.
Volgens stelling 2 hebben we dus r | p - 1. ¨

De volgende stelling kunnen we hier best zonder bewijs geven:

Stelling 3
ALS p is een oneven priemgetal, DAN uit 2^{^a} = 1 (mod p) volgt dat 2^{^a}= 2k^.p + 1 (voor zekere gehele waarde van k)

2. Andere stellingen
Bij het onderzoek naar Mersenne-priemgetallen kunnen ook enkele andere stellingen (ze behoren natuurlijk ook tot de getallentheorie) over priemgetallen worden gebruikt.
We kunnen bijvoorbeeld eerst op zoek gaan naar kleine delers van het te onderzoeken Mersenne-getal.
Bij dit onderzoek is vooral de onderstaande stellling van nut (Euler ontdekte het eerste deel van de stelling; Fermat ontdekte en gebruikte het tweede deel).

Stelling 4
Zijn p en q oneven priemgetallen.
ALS p | Mq = 2^{^q} - 1, DAN p º +/-1 (mod 8) EN p º 1 (mod q).

Bewijs:
Als p deelbaar is op Mq, dan is 2^{^q} º 1 (mod p)
Uit stelling 3 volgt nu eenvoudig, dat p º 1 (mod q).
Maar volgens stelling 1 in paragraaf 1 volgt uit die deelbaarheid ook, dat de orde r van 2 (mod p) dan deelbaar is op (het priemgetal) q.
Dus moet r gelijk zijn aan q (immers p is ongelijk aan 2).
Uit het gevolg van stelling 2 vinden we: r (= q) is ook deelbaar op p - 1, zodat p - 1 = 2k ^. q. Dit geeft

2^{^{(p - 1)/2}} = 2 ^{^qk} º 1 (mod p)

Dus is 2 een kwadraatrest mod p. Daaruit volgt, dat p º +/-1 (mod 8), waarmee het bewijs geleverd is. ¨

Voorbeeld
Stel p is deelbaar op M₃₁.
Volgens de stelling is dan p º 1 of p º 2k ^. 31 + 1 = 63 (mod 248)
In 1772 gebruikte Euler dit resultaat om aan te tonen, dat M₃₁ inderdaad een priemgetal is.
[einde voorbeeld]

Stelling 5
ALS p een priemgetal met p º 3 (mod 4), DAN 2p + 1 is priem DESDA 2p+1 | M_p

Bewijs:
Stel q =2p + 1 is priem. Hieruit volgt, dat q º 7 (mod 8). En daaruit volgt dan weer, dat 2 een kwadraatrest mod q is.
Dit betekent dus, dat er een getal natuurlijk getal x bestaat, waarvor x² º 2 (mod q) ten minste één oplossing heeft.
Dus
   2^{^p} = 2^{^(q-1)/2} = x^{^q-1} º 1 (mod q)
waaruit volgt, dat q | M_p; met andere woorden 2p + 1 | M_p.
Omgekeerd.
Zij 2p + 1 een factor van M_p = 2^{^p} - 1.
Stel nu (voor een bewijs uit het ongerijmde), dat 2p + 1 samengesteld (dus niet priem) is. Zij nu q de kleinste priemfactor van 2p + 1.
Nu is q dus ook een factor van M_p; met andere woorden 2^{^p}º 1 (mod q), waarbij voor de orde r van 2 modulo q geldt r | p en r | p-1.
Hieruit volgt dus dat q > p en dus ook q² > p²; zodat uit
   (2p + 1) + 1 > q²
volgt
   2p + 2 > p² en dus p² - 2p - 2 < 0.
Deze ongelijkheid is alleen waar voor p = 1 en p = 2. En dit geeft een tegenspraak, omdat p > 2.
Dus is 2p + 1 een priemgetal. ¨

Opmerking
Deze stelling is voor het eerst geformuleerd door Euler in 1750 en bewezen door Lagrange 1775
[einde opmerking]

Gevolg
Als nu p = 3 (mod 4) EN 2p + 1 beide priemgetallen zijn, dan geldt p = 3 of M_p is samengesteld.

Volmaakte getallen
Er is een verband tussen volmaakte getallen (Engels: perfect numbers) en de priemgetallen van Mersenne (zie ook de pagina Volmaakte getallen)

Definitie
Een volmaakt getal is een getal waarvan de som van de delers (met uitzondering van dat getal zelf) gelijk is aan dat getal.
Voorbeeld
28 = 1 ^. 2 ^. 4 ^. 7 ^. 14 = 1 + 2 + 4 + 7 + 14
[einde voorbeeld]

Op deze definitie is gebaseerd de

Stelling 6
Ieder volmaakt getal P_n is te schrijven als P_n = 2^n-1 . M_n, waarbij M_n een Mersenne-priemgetal is.

Bewijs:
Dus P_n = 2^{n - 1} (2ⁿ - 1), met n is priem
We verwijzen voor het bewijs eveneens naar de pagina Volmaakte getallen. ¨

De volgende stelling over volmaakte getallen maakt het mogelijk voor relatief kleine Mersenne-getallen primaliteitsonderzoek te doen.

Stelling 7
Zij P_n een even volmaakt getal ongelijk aan 6.
ALS S₁, S₂, S₃, ... de rij getallen die ontstaat als de som T van de cijfers van die getallen, waarbij S _i = T(S _{i - 1}) en S₁= T(P_n)
DAN is er altijd een k waarvoor S_k = 1.

Voorbeelden
28 ® 10 ® 1;
496 ® 19 ® 10 ® 1, en
8128 ® 19 ® 10 ® 1
[einde voorbeelden]

Bewijs:
Zij nu S_n de som van de cijfers van het getal n. Bekend is dat dan S_n = n (mod 9).
We hoeven dus alleen aan te tonen, dat voor elk volmaakt getal P_n geldt P_n = 1 (mod 9).
Als n een volmaakt getal is, dan heeft dat getal op grond van de definitie de vorm 2^{p - 1}(2^p - 1), waarbij p priem is.
p is dus gelijk aan 2 of 3, of voor p geldt p = 1 (mod 6) of p = 5 mod 6).
Merk op dat we n = 6 (voor p = 2) hebben uitgesloten.
Om dat 2^⁶ = 1 (mod 9) repeteren de machten van 2 (2^p-1) dus met een periode 6 (bekeken modulo 9).
Voor de rest van het bewijs hoeven we dus alleen te kijken naar de getallen
2^1-1(2¹-1)
2^3-1(2³-1) en
2^5-1(2⁵-1)
En deze zijn alle gelijk aan 1 modulo 9. ¨

[mersenne_d.htm] laatste wijziging op: 27-12-04