Mersenneprimtal

Mersenneprimtal är primtal på formen 2^n - 1 och de har fått namn av munken Marin Mersenne som studerade dem på 1600-talet. För att 2^n-1 ska kunna vara ett primtal vet man att n måste vara ett primtal, så ibland skrivs de 2^p-1. Man använder även beteckningen M5 för talet 2^5-1, där M står för Mersenne.

Det finns 40 kända mersenneprimtal och de första är:

• 3
• 7
• 31
• 127
• 8191
• 131071
• ...

Vi ser att 3 = 2^2-1, 7=2^3-1, 31=2^5-1, 127=2^7-1, 8191=2^13-1 och exponenterna 2, 3, 5, 7 och 13 är som förväntat primtal. Av Fermats lilla sats följer att alla tal av formen 2^p-1 där p är primtal antingen är Mersenneprimtal eller så är samtliga faktorer av formen 2p*n+1.

Mersenneprimtalen är vanligen de största kända primtalen för att de är relativt enkla att hitta. Att kontrollera att 2^n-1 är ett primtal kan göras på sätt som är polynomiska med avseende på n, istället för polynomiska med avseende på talet självt. Trots det tar det en modern PC ett antal veckor att kontroller ett enda tal stort nog att vara störst primtal i världen. Det test som används är Lucas-Lehmer-testet döpt efter Edouard Lucas och D.H.Lehmer.

Intresserade kan själv hämta programvara för testning hos GIMPS: http://www.mersenne.org/ vilket är den organisation som organiserat hittandet av de senaste rekordprimtalen. Först att hitta ett primtal med 10 000 000 siffror får 100 000 dollar av EFF.

Mersenneprimtal är knutna till de jämna perfekta talen. Om 2^n-1 är ett mersenneprimtal så är (2^n-1)*2^(n-1) ett perfekt tal och faktum är att det kan bevisas att alla jämna perfekta tal är på den formen. (Huruvida det finns udda perfekta tal är ännu okänt)

Redigera?

Artikeln skriven 2009-01-18 av Learning4sharing

Inga kategorier för denna artikel än...

Intresserad av fler artiklar?

Athlon 64
Slut
Lina Sandell gården
Slaget samman Cable Street
Guvernant
Mejeri
Jenisej
Laura Palmer
Prequel