Mersenneprimtal

Från Rilpedia

Texten från svenska Wikipedia

Ett Mersennetal M_n är inom talteorin ett heltal på formen 2ⁿ − 1. Det är uppkallat efter den franske amatörmatematikern Marin Mersenne.

Ett Mersenneprimtal är ett Mersennetal som är ett primtal.

Om Mersenneprimtal

Det är okänt huruvida det existerar ett oändligt antal Mersenneprimtal. Hittills har 46 Mersenneprimtal hittats. De största av dessa är också de största kända primtalen, med flera miljoner siffror. Anledningen till att så stora Mersenneprimtal kunnat bestämmas är att det finns en särskilt effektiv algoritm för att avgöra om tal på den här formen är prima, nämligen Lucas-Lehmers test. Det senaste Mersenneprimtalet är 2^{43 112 609}-1. Det upptäcktes den 23 augusti 2008 av Great Internet Mersenne Prime Search (GIMPS) och har 12 978 189 siffror.

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 (= 2 047) inget primtal, ty 2 047 = 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 (8 191) är ett primtal borde enligt denna hypotes också 2⁸¹⁹¹ - 1 (2 466-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.

Sökning efter 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 den amerikanske matematikern Leonard Eugene 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 den franske amatörmatematikern Édouard Lucas uppställde i slutet av 1800-talet:

Bilda talföljden l[0] = 4, l[i+1] = (l[i]2 - 2) MOD (2p - 1)
För p > 2 är 2p - 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.

Lista över alla kända Mersenneprimtal

* Det är inte känt om det finns några oupptäckta Mersenneprimtal mellan det 39:e (M_{13 466 917}) och det 46:e (M_{43 112 609}) i den här tabellen, så därför finns risk att ordningen på de sista talen inte stämmer.

Externa länkar

• http://www.mersenne.org/

 Denna artikel om algebra är bara påbörjad. Du kan hjälpa till genom att utöka den.