Hitta primtal på formen 2^n-1

Våra första och största primtal

Primtal är något som människan har varit medveten om mycket länge. En primtal definieras som ett tal som är större än 1 och enbart är delbart med sig självt och 1. Talet går alltså inte att dela upp i faktorer av några andra tal. Primtal är fundamentala för matematiken eftersom alla naturliga tal >1 antingen är primtal eller faktorer av primtal, enligt aritmetikens fundamentalsats. 

Vi vet också att det finns oändligt många primtal efter ett bevis som finns i Euklides Elementa som formulerades 300 f.kr. (du kan försöka bevisa det med lite vägledning i följande dokument). I och med att det finns oändligt många primtal har människan alltid varit intresserad av vilken som är det största möjliga primtal som vi människor kan hitta. Metoderna har varit olika genom historien. Tidigt undersökte man primtal genom att testa vilka delare ett tal hade. Det var en tidskrävande aktivitet men gav säkra resultat. Fram till 1400-talet hade man inte hittat särskilt många primtal men 1456 hittade en anonym matematiker primtalet 8191. Ungefär 100 år senare kunde den franska matematikern Martin Mersenne (1588-1648) visa på att primtal kunde skrivas på formen 2^n-1 . Primtal som går att skrivas på den formen kallas idag för Mersenneprimtal. En matematiker som var samtida med Mersenne var Cataldi (1548-1636) som hittade två primtal som kunde skrivas på formen  2^n-1 nämligen  2^{17}-1=131071 och  2^{19}-1=524287 . Leonhard Euler kunde senare visa att  2^{31}-1=2147483647  var ett primtal. 

Progressionen fortsatte under 100 år men stannade till slut när den franska matematikern Edouard Lucas efter 19 år av undersökning lyckades visa att 2^{127}-1=170141183460469231731731687303715884105727  var ett primtal. Idag är det primtalet fortfarande det största som människan tagit fram för hand. 

Under 1950-talet hade människan börjat producera maskiner som kunde utföra matematiska beräkningar i en takt som den mänskliga hjärnan inte kunde. Det resulterade också i att man kunde undersöka stora tal om de var primtal mycket mer effektivt. Man utnyttjade faktumet att man visste att flera primtal kunde gå att skrivas på formen 2^n-1. Under 1952 hittade man 4 nya Mersenneprimtal det största var 2^{2281}-1 som jag inte kommer skriva ut eftersom talet innehåller mer än 687 siffror. 

I och med att datorerna har blivit bättre har också datorernas förmåga att hitta stora primtal förbättrats. Mellan 1957 – 2018 har man hittat 33 nya Mersenneprimtal där det största primtalet är 2^{82589933}-1 , primtalet innehåller 24862048 siffror. Tänk vad fantastiskt att ett tal som är så stort fortfarande bara kan dela sig själv och 1. Under de senaste åren har ett projekt som heter GIMPS varit aktivt som enbart har som uppgift att hitta stora primtal. Man använder de mest avancerade datorerna för att möjliggöra beräkningarna som krävs för att undersöka om talen är primtal. Det tar också såklart längre och längre tid desto större talen blir. Samtidigt vi vet som sagt att det finns oändligt många därför kommer vi med rätt metoder alltid hitta nya primtal. 

 

Euklides – Mannen som (eventuellt) bevisade att det finns oändligt med primtal 

Martin Mersenne 

Graf som visar på när man fann primtal och dess storlek. Man kan konstatera att de hittar färre desto större primtalen blir.