Primtal

Ett primtal är ett heltal som är större än 1 och jämnt delbart endast med sig själv och med 1. Exempel: 7 är ett primtal eftersom man inte kan dela det med något annat tal (utom 1 och 7) och få ett nytt heltal. 51 är inte ett primtal eftersom det är lika med 3 · 17. Primtal spelar en stor roll i talteorin.

Det största primtal som hittills har hittats är 2^30 402 457 − 1. Talet hittades den 15 december 2005 av Curtis Cooper och Steven Boone, som båda är professorer vid Central Missouri State University i USA. Detta tal, som är ett Mersenneprimtal, innehåller 9 152 052 siffror.

Det största kända primtalet som består av ett primtal antal siffror är 27 653 · 2^{9 167 433} + 1 som har 2 759 677 siffror, utskrivet i bas 10.

De första tjugo primtalen är: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

Antalet primtal

Det finns oändligt många primtal, så det är omöjligt att skriva upp alla i en lång lista. Att antalet primtal är oändligt bevisades redan av Euklides ca 300 f.Kr.

Antag att antalet primtal är ändligt och lika med $n$ . Kalla alla primtal $p_1 \ldots p_n$ . Bilda nu talet $P = p_1p_2 \ldots p_n + 1$ . Inget av primtalen delar $P$ eftersom det då måste dela 1. Alltså är $P$ ett primtal som inte fanns tidigare i listan, eller en produkt av sådana primtal, och vårt antagande att antalet primtal är ändligt var falskt.

Notera att denna metod i allmänhet inte kan användas för att hitta nya primtal, då den enbart garanterat fungerar om det inte finns några andra primtal mellan $p_n$ och P.

Beräkning av primtal

Eratosthenes såll heter en algoritm som plockar ut alla primtal upp till och med en vald övre gräns.

För att hitta stora primtal, till exempel för att använda kryptografiskt, är den metoden opraktisk. I stället använder man metoder som bygger på att helt enkelt gissa ett tal och kontrollera om det blev ett primtal.

Olösta problem

Det finns fortfarande många olösta gåtor angående primtalen:

Finns det oändligt många primtalstvillingar?
Finns det oändligt många primtal på formen n²+1?
Finns det alltid ett primtal mellan n² och (n + 1)²?
Hur många primtal är fermattal? (Hittills har bara 5 hittats.)
Innehåller Fibonaccitalföljden oändligt många primtal?

Se även

Litteratur

Riesel, Hans, En bok om primtal, Lund 1968

Externa länkar

http://primes.utm.edu/
http://mathworld.wolfram.com/topics/PrimeNumbers.html
Lista över stora möjliga primtal