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 an º 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 2a = 1 (mod p) volgt dat 2a = 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 = 2q - 1, DAN p º +/-1 (mod 8) EN p º 1 (mod q).

Bewijs:
Als p deelbaar is op Mq, dan is 2q º 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 M31.
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 M31 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 | Mp

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 x2 º 2 (mod q) ten minste één oplossing heeft.
Dus
   2p = 2(q-1)/2 = xq-1 º 1 (mod q)
waaruit volgt, dat q | Mp; met andere woorden 2p + 1 | Mp.
Omgekeerd.
Zij 2p + 1 een factor van Mp = 2p - 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 Mp; met andere woorden 2p º 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 q2 > p2; zodat uit
   (2p + 1) + 1 > q2
volgt
   2p + 2 > p2 en dus p2 - 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 Mp 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 Pn is te schrijven als Pn = 2n-1 . Mn, waarbij Mn een Mersenne-priemgetal is.

Bewijs:
Dus Pn = 2n - 1 (2n - 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 Pn een even volmaakt getal ongelijk aan 6.
ALS S1, S2, S3, ... de rij getallen die ontstaat als de som T van de cijfers van die getallen, waarbij i = T(S i - 1) en S1 = T(Pn)
DAN is er altijd een k waarvoor Sk = 1.

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

Bewijs:
Zij nu Sn de som van de cijfers van het getal n. Bekend is dat dan Sn = n (mod 9).
We hoeven dus alleen aan te tonen, dat voor elk volmaakt getal Pn geldt Pn = 1 (mod 9).
Als n een volmaakt getal is, dan heeft dat getal op grond van de definitie de vorm 2p - 1(2p - 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 26 = 1 (mod 9) repeteren de machten van 2 (2p-1) dus met een periode 6 (bekeken modulo 9).
Voor de rest van het bewijs hoeven we dus alleen te kijken naar de getallen
21-1(21-1)
23-1(23-1) en
25-1(25-1)
En deze zijn alle gelijk aan 1 modulo 9. ¨


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