Priemgetallen van Mersenne

Overzicht Grootste M-priemgetal ][ Getallentheorie | Maple | GIMPS-homepage

Een inleiding tot de Mersenne-priemgetallen
met gebruikmaking van het computerprogramma Maple V, release 4 en release 9
februari 1998 (laatste update: juli 2004)

Overzicht (op deze en andere pagina's op deze website)

1. Inleiding
2. Maple
3. Mersenne's getallen
4. Grootste M-priemgetal (recent)

Overige pagina's (op deze website)

Appendix A - Bewijs van "ALS 2ⁿ - 1 is priem, DAN n is priem"
Appendix B - Kleine stelling van Fermat
Appendix C - Lucas-Lehmer-test voor Mersenne-priemgetallen
Appendix D - Enkele andere stellingen
Bronnen en informatie over priemgetallen (algemeen)

1. Inleiding
Getallen van de vorm 2ⁿ -1 heten Mersenne-getallen, naar de Franse monnik Marin Mersenne (1568-1648), die getallen van deze vorm voor het eerst uitvoerig onderzocht.
Mersenne-getallen zullen we in hetgeen volgt aangeven met M(n) = 2ⁿ - 1 of met Mn
Met M_k geven we het k-de getal in de rij gevonden Mersenne-priemgetallen aan.
Voorbeeld
M(3) = 2³ - 1 = 7 of ook M3 = 7.
Aangezien dit getal het tweede in de rij Mersenne-priemgetallen is (M₁ = 3), geldt M₂ = 7.

2. Maple
Met het computerprogramma Maple V, release 4, is het eveneens mogelijk, maar nu op een wat modernere manier, deze getallen te onderzoeken.
In de eerste plaats kunnen we ze genereren via een eenvoudige Maple-procedure, hieronder als pM gedefinieerd.

> restart:
> pM := proc(n)
> 2^n-1;
> end:

Deze procedure kunnen we in de volgende opdrachten aanroepen..
Allereerst leggen we het aantal te genereren Mersenne-getallen vast. Om deze getallen gemakkelijk te kunnen gebruiken slaan we ze op in een zogenoemd array met de naam M en vervolgens rekenen we ze uit.

> aantal:=35:
> M := array(1..aantal):
> for t to aantal do M[t] := pM(t) od:
> eval(M);

[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383,32767, 65535,/
 131071, 262143, 524287, 1048575, 2097151, 4194303,8388607, 16777215, 33554431,/
 67108863, 134217727, 268435455,536870911, 1073741823, 2147483647, 4294967295,/
 8589934591,17179869183, 34359738367]

De eerste 35 Mersenne-getallen kunnen dus via het array worden aangeroepen; de overige kunnen worden berekend met de procedure pM.

Allereerst kunnen we nagaan welke van de eerste 35 Mersenne-getallen priem zijn. Uit onderstaand stukje programma blijkt (wellicht), dat
ALS M(n) is priem, DAN n is priem

> for t to aantal do
> if isprime(M[t]) then print(t,M[t]) fi;
> od;

2, 3
3, 7
5, 31
7, 127
13, 8191
17, 131071
19, 524287
31, 2147483647

Het is inderdaad mogelijk (zie Appendix A) de volgende stelling te bewijzen.
ALS 2ⁿ - 1 is priem, DAN n is priem
Het omgekeerde van bovenstaande stelling: ALS n is priem, DAN M(n) is priem
geldt evenwel niet, zoals uit een tegenvoorbeeld duidelijk(er) blijkt.

> isprime(M[11]);

false

> ifactor(M[11])=M[11];

(23) (89) = 2047

3. Mersenne's getallen
In 1644 schreef Mersenne, in het voorwoord bij zijn boek Cogitata Physico Mathematica, dat de enige waarden van p kleiner dan of gelijk aan 257 waarvoor 2^{^p} - 1 een priemgetal is, de volgende zijn:
1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.
Mersenne heeft zich echter met deze uitspraak in een tweetal opzichten vergist.
Ten eerste heeft hij niet alle waarden van p in zijn overzicht opgenomen, waarvan (nu) bekend is dat M(p) priem is.
Bijvoorbeeld, het getal 89 (dat kleiner is dan 257) ontbreekt:

> M89 := 2^89-1;

M89 := 618970019642690137449562111

> isprime(M89);

true

En in de tweede plaats leveren niet alle door hem genoemde waarden van p een Mersenne-getal op dat priem is.

> M67:=2^67-1;

M67 := 147573952589676412927

> isprime(M67);

false

Maple levert deze waarde (false, dus ontbindbaar) binnen een fractie van een seconde, maar het heeft tot 1903 geduurd voordat de uitspraak van Mersenne met betrekking tot M(67) werd tegengesproken.
F.N. Cole (1861-1926; hoogleraar aan Columbia University), spreker op de jaarlijkse bijeenkomst van de American Mathematical Society in oktober 1903 in New York, hield zijn voordracht "On factorization of large numbers" als volgt.

Na door de voorzitter te zijn uitgenodigd om zijn voordracht te houden liep Cole -hij stond bekend als een man van weinig woorden- naar het bord waarop hij zwijgend de berekening van 2 tot de macht 67 opschreef. Van het antwoord trok hij zorgvuldig 1 af. Nog steeds zonder een woord te zeggen wandelde hij naar een leeg stuk van het bord en daar voerde hij de volgende vermenigvuldiging uit.

> 761838257287*193707721;

147573952589676412927

En inderdaad...
"De beide antwoorden waren gelijk... Cole ging weer zitten zonder dat hij een woord had gesproken. Niemand van de aanwezigen had iets te vragen", stond er in het verslag van E.T. Bell (1863-1960, USA).
Bell vroeg later aan Cole hoe lang hij ervoor nodig had gehad om deze ontbinding te vinden. Cole antwoordde: "Drie jaar lang, elke zondag".

Maple berekent in ongeveer 4 seconden (op een Compaq LTE 5100 met Pentium 100 processor):

> ifactor(M67);

(761838257287) (193707721)

Overigens geldt:

> isprime(761838257287);
> isprime(193707721);

true
true

De beide factoren waarin M67 kan worden ontbonden, zijn dus wel priemgetallen.
Het getal 61 ontbreekt overigens ook in de lijst. En mogelijk is 67 een schrijffout, want

> M61 := pM(61);

M61 := 2305843009213693951

> isprime(M61);

true

In 1883 werd dit resultaat door J Pervushin gevonden.
Naast het getal 61, ontbreken ook de getallen 89 en 107 in de door Mersenne genoemde rij.

> M89 := pM(89);
> isprime(M89);

M89 := 618970019642690137449562111
true

> M107 := pM(107);
> isprime(M107);

M107 := 162259276829213363391578010288127
true

terwijl voor n = 257 (ook door Mersenne genoemd) juist niet geldt dat 2ⁿ - 1 een priemgetal is.

> M257:=pM(257);
> isprime(M257);

M257 := 2315841784746323908471419700173758157065399693312811280789\
15168015826259279871
false

Hoewel M257 een door Maple redelijk te behandelen aantal cijfers heeft (zie hieronder), worden de factoren M257 toch niet binnen een aanvaardbare tijd gevonden. We wagen ons daarom niet aan een directe ontbinding van M257 via Maple.

> AantalCijfers:=trunc(evalf(log10(M257)))+1;
> # ifactor(M257);

AantalCijfers := 78

Het is op zich niet vreemd, dat een directe ontbinding stuk loopt, omdat de kleinste priemfactor (sfactor) van M257 nogal groot is:

> sfactor:=535006138814359:
> isprime(sfactor);

true

> q257 := M257/sfactor;

q257 := 432862656469423142931042426214547535783388063929571229938474969

> isprime(q257);

false

En opnieuw wagen we ons maar niet aan de ontbinding van q257.

De lijst van Mersenne vormde, ondanks of dankzij het ambitieuze karakter ervan, of de fouten erin, een stimulans voor wiskundigen, tot op de dag van vandaag: zie hiervoor bijvoorbeeld de pagina's van Great Internet Mersenne Prime Search (Engels / Nederlands), bij welk project (in 2000) meer dan 14.000 mensen op zoek zijn naar Mersenne-priemgetallen (klik hier voor andere Mersenne-links).

mers_ani

4. Grootste M-priemgetal
¤ 1 juni 1999: het op twee na grootste Mersenne-priemgetal (het achtendertigste) gevonden:
M₃₈ = 2^6972593 - 1
Het bestaat uit 2.098.960 cijfers.
De primaliteit van de exponent kunnen we met Maple testen:

> restart;
> mexp:=6972593;

mexp := 6972593

> isprime(mexp);

true

Er bestond op het moment van vinden echter nog geen zekerheid of er tussen M₃₇ en M₃₈ geen priemgetallen liggen.
Wel weten we:
¤ 19 mei 2000:
Double-checking toonde aan, dat M(2976221) and M(3021377) inderdaad het 36e en 37e Mersenne-priemgetal zijn.
¤ 15 maart 2000:
Alle exponenten kleiner dan 5.000.000 zijn nu ten minste één keer getest.
Ondertussen (25 juli 2001) zijn de noodzakelijke testen uitgevoerd.

¤ 14 november 2001 -- het 39ste Mersenne-priemgetal via GIMPS werd gevonden door Michael Cameron (Canada):

M₃₉ = 2^13 466 917 - 1

Het bestaat uit meer dan 4 miljoen cijfers (te weten 4 053 946)!
En, deels weer ter controle:

> restart:
> mexp := 13466917;

mexp := 13466917

> isprime(mexp);

true

¤	17 november 2003 -- het 40ste Mersenne-priemgetal werd via GIMPS gevonden door Michael Shafer (USA). Aantal cijfers: 6.320.430. Na controle werd eea. op 2 december 2003 wereldkundig gemaat.

M₄₀ = 2^20.996.011 - 1

> restart:
> mexp := 20996011;

mexp := 20996011

> isprime(mexp);

true

¤	9 maart 2004 -- Alle exponenten kleiner dan 12.000.000 zijn ten minste één keer aan een test onderworpen.

¤	15 mei 2004 -- Josh Findley, Californië, USA) vindt het 41ste; ook weer via GIMPS! M₄₁ bestaat uit 7.235.733 cijfers. Op 28 mei 2004 werd dit feit bekend gemaakt. Op dat moment waren er meer dan 240.000 computers met GIMPS verbonden.

M₄₁ = 2^24.036.583 - 1

> restart:
> mexp := 24036583:
> isprime(mexp);

true

¤ M₄₂	18 februari 2005 -- Dr. Martin Nowak from Germany, found the new largest known prime number, 2^25.964.951 - 1. The prime number has 7,816,230 digits! It took more than 50 days of calculations on Dr. Nowak's 2.4 GHz Pentium 4 computer. The new prime was independently verified in 5 days by Tony Reix of Grenoble, France using a 16 Itanium CPU Bull NovaScale 5000 HPC running the Glucas program by Guillermo Ballester Valor (Granada, Spain). A second verification was completed by Jeff Gilchrist of Elytra Enterprises Inc. (Ottawa, Canada) using 15 days of time on 12 CPUs of a Compaq Alpha GS160 1.2 GHz CPU server at SHARCNET.
¤ M₄₃	15 december 2005 -- Op deze dag hebben Dr. Curtis Cooper en Dr. Steven Boone, beiden verbonden aan Central Missouri State University (Warrensburg, USA), het 43e Mersenne priemgetal gevonden: 2^30.402.457 - 1 Dit priemgetal bestaat uit 9.152.052 cijfers en is daardoor tevens het grootste tot nu toe bekende priemgetal. Het nieuwe priemgetal werd (binnen 5 dagen) onafhankelijk geverifieerd door Tony Reix (Bull S.A., Grenoble). Cooper is deelnemer aan het GIMPS project (Great Internet Mersenne Prime Search). Op CMSU wordt met 700 PC's gezocht naar priemgetallen. Het nieuwe priemgetal is het negende dat via GIMPS gevonden is. GIMPS telt op dit moment meer dan 45.000 deelnemers. Zie voor verdere informatie: www.mersenne.org (bron: WiskundePersdienst)
¤ M₄₄	4 september 2006 -- Opnieuw vond het team van Dr. Curtis Cooper and Dr. Steven Boone een nieuw Mersenne-priem: het 44e: 2^32.582.657 - 1 Het priemgetal, van 9.808.358 cijfers, is zo'n 650.000 cijfers langer dan hun vorige record uit december 2005 (zie hierboven). Nooit eerder waren Mersenne priemgetallen zo dicht bij elkaar gegroepeerd. Wanneer we naar de exponenten kijken, verwachten we gemiddeld slechts 1,78 Mersenne priems tussen twee opvolgende machten van 2, en vóór 2003 werden hooguit 3 Mersenne priemgetallen gevonden tussen opvolgende machten van 2. De exponenten van nieuwste 5 Mersenne priemgetallen liggen alle tussen 2²⁴ en 2²⁵ -- en nog niet eens alle tussenliggende exponenten zijn getest! Het nieuwe priemgetal is onafhankelijk gecontroleerd op ondeelbaarheid door Tony Reix van Bull S.A. in Grenoble, Frankrijk. Hij gebruikte daarvoor 16 Itanium2 1.5 GHz CPUs van een Bull NovaScale 6160 HPC in het Research Center van Bull in Grenoble, waarop het Glucas programma draaide van Guillermo Ballester Valor uit Granada, Spanje.
¤ 23 april 2007 -- Alle exponenten kleiner dan 15.000.000 zijn twee keer getest.

[mersenne.htm] laatste wijziging op: 15-11-2007