Om Mersennes tal

Detta är ett redigerat utdrag ur originalartikeln, som egentligen behandlade programmering och presenterade ett program (i Modula-2) vilket beräknade tal av Mersennetyp och s k Perfekta tal (som är besläktade med Mersennetalen).

Primtal och datorer

Alltsedan urminnes tider har människan fascinerats av tal och talföljder med mer eller mindre säregna egenskaper. Vissa av dessa "magiska tal" har ett ringa talteoretiskt intresse. Detta gäller dock inte primtalen, som faktiskt intar en hedersplats inom talteorin.

Det mer vetenskapliga intresset för primtal vaknade under antiken och de flesta matematiskt intresserade har nog hört talas om Erathostenes primtalssåll och Euklides bevis för att det finns oändligt många primtal. Från denna tid och fram till idag har en lång rad matematiker (och "amatörer") kämpat med att försöka röja primtalens alla hemligheter. Den populärvetenskapliga litteraturen ger många belägg för detta - se t ex E T Bells artikel "Matematikens drottning" i band 4 av det klassiska samlingsverket "Sigma" (brukar finnas på de flesta skolbibliotek).

Var kommer då datorerna in i sammanhanget? Det är ingalunda så att deras intåg på arenan medfört något talteoretiskt "genombrott". Vad jag vet har inga fundamentala talteoretiska problem "lösts" eller "bevisats" med datorer. Däremot har de gjort det möjligt att testa talteoretiska hypoteser och tillämpa talteoretiska satser på problemställningar av en storleksordning och i en omfattning som tidigare var otänkbar.

Till de problemområden där datoranvändningen firat stora triumfer hör bestämning av primtal, liksom det besläktade problemet att finna faktorer till stora tal som inte är primtal.

Mersennetal

Mersennetalen, som uppkallats efter amatörmatematikern M Mersenne, definieras enligt 2ⁿ - 1. De har anknytningar till talteorin i allmänhet och primtalsteorin i synnerhet.

De största kända primtalen är av mersennetyp, men långt ifrån alla mersennetal är primtal. Med exponenten 4 erhålls t ex 15, som är ett sammansatt tal. Detta förhållande gäller f ö för samtliga jämna exponenter större än 2, eftersom exponenten då kan skrivas som 2j och mersennetalet faktoruppdelas enligt modellen 2^2j - 1 = (2^j + 1)(2^j - 1).

Resultatet kan generaliseras: Om exponenten är sammansatt är även motsvarande mersennetal sammansatt.

För att ett mersennetal ska kunna utgöra ett primtal måste alltså exponenten vara ett primtal. Inte heller detta villkor är dock tillräckligt. Exempelvis är 2¹¹ - 1 (= 2047) inget primtal, ty 2047 = 23*89.

Ett tag trodde man att alla mersennetal med mersenneprimtal som exponenter var primtal, vilket stämmer för 2⁷ - 1, 2³¹ - 1 och 2¹²⁷ - 1. Eftersom 2¹³ - 1 (8191) är ett primtal borde enligt denna hypotes också 2⁸¹⁹¹ - 1 (2466-siffrigt!) vara det. Denna fromma illusion brast när man kunde undersöka saken med dator.

Flera liknande primtalshypoteser har sett dagens ljus, men samtliga har kunnat förpassas till papperskorgen. Det finns således ingen allmän tumregel eller "formel", med vilken man kan vaska fram mersenneprimtal.

Vad är det då som gör mersenneprimtalen så speciella? Jo, en viktig anledning är att det trots allt är "relativt lätt" att avgöra om ett mersennetal är ett primtal eller inte.

Bortsett från några specialfall (de tal som slutar på 0, 5 eller är jämna, liksom de vars siffersumma är jämnt delbar med 3, kan t ex inte vara primtal) finns inga "enkla" sätt att avgöra om ett godtyckligt tal är ett primtal eller inte. Även om det i det allmänna fallet finns bättre metoder än att tillgripa testdivision med samtliga primtal upp till kvadratroten ur talet, så krävs ofta ett enormt räknearbete för att kontrollera primtalsegenskapen. Om detta mindre trevliga perspektiv skriver matematikern L E Dickson (1874-1954):

För att avgöra huruvida ett tal med 15 eller 20 siffror är ett primtal eller ej, skulle all tid vara otillräcklig, hur mycket man än utnyttjade allt som redan är känt.

Även om Dicksons spådom fått stryka på foten i och med att vi med datorerna fått räkneredskap som man inte kunde drömma om för ett halvsekel sedan, kvarstår faktum att det, även med den kraftfullaste superdator till förfogande, i praktiken är ogörligt att primtalstesta tal bestående av tusentals siffror.

För mersennetal är läget annorlunda. På dessa kan man nämligen applicera ett speciellt kriterium, som amatörmatematikern E Lucas uppställde i slutet av 1800-talet:

Bilda talföljden l[0] = 4, l[i+1] = (l[i]² - 2) MOD (2^p - 1)
För p > 2 är 2^p - 1 ett primtal om och endast om l[p-2] = 0, dvs om mersennetalet går jämnt upp i termen med ordningsnumret p-2.

Också denna metod kräver ett mycket stort räknearbete när vi har att göra med mersennetal som består av tiotusentals (och ännu fler) siffror, men i motsats till de algoritmer som måste användas i det allmänna fallet för att avgöra om ett tal är primtal eller inte, är den praktiskt utförbar.

Före datoråldern (dvs fram till början av 50-talet) kände man till 11 mersenneprimtal, av vilka det största var 2¹²⁷ - 1 (39-siffrigt) och man visste inte om det existerade några fler primtal i denna familj. Idag (=1989, se anmärkningen nedan) är antalet 31 och det största 2²¹⁶⁰⁹¹ - 1, upptäckt 1985 med en Cray superdator (enligt 1988 års upplaga av Guinness rekordbok).

Efterskrift 1998

I originalartikeln som ovan ges i utdrag skrev jag bl a:

Ingen av oss lär hamna i "Guiness rekordbok" genom att låta en persondator stå i veckor/månader/år och tugga fram "nya" enorma mersenneprimtal, ty själva primtalstesten kräver superdatorprestanda.

Ovanstående skrevs hösten 1989 och var sant vid den tidpunkten. Idag är situationen annorlunda och tusentals persondatorer världen över är inbegripna i ett internationellt samarbetsprojekt som systematiskt söker efter mersenneprimtal.

Projektet, som kallas "The GREAT Internet Mersenne Prime Search", förkortat GIMPS, påbörjades i början av 1996 och har som målsättningen att fram till år 2000 undersöka alla intressanta exponenter upp till över 5 miljoner. Detta projekt har möjliggjorts av den snabba utvecklingen av persondatorerna i kombination med spridningen av Internet som gör det möjligt att samordna beräkningskapaciteten från tiotusentals datorer.

Uppdatering oktober 2008

GIMPS-projektet har fram till idag upptäckt 13 mersenneprimtal: 2^1398269 - 1, 2^2976221 - 1, 2^3021377 - 1, 2^6972593 - 1, 2^13466917 - 1, 2^20996011 - 1, 2^24036583 -1, 2^25964951 -1, 2^30402457 -1, 2^32582657-1, 2^37156667-1, 2^42643801-1 och 2^43112609-1 (det största består av nära 13 miljoner siffror!).

Tabellen nedan listar samtliga kända mersenneprimtal (46 st).

Om du vill veta mer om GIMPS och det aktuella forskningsläget kan du klicka på knappen nedan.