Primtal

Wikipedia

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^32 582 657 − 1. Talet hittades den 4 september 2006 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 808 358 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 (sekvens A000040 i OEIS):

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

I äldre litteratur (före ca 1920) räknas ofta talet 1 som primtal.

[redigera] 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 det finns ändligt många primtal och att de är $n$ stycken. Kalla primtalen $p_1,p_2, \ldots, p_n$ och bilda talet $P = p_1p_2 \cdots p_n + 1$ . Eftersom $P$ dividerat med $p k$ ger resten 1 för varje $k=1,2,\ldots,n$ så delas inte $P$ av något av primtalen i listan. Detta betyder att $P$ antingen är ett primtal som inte är med i listan, eller en produkt av primtal som saknas i listan. Alltså går det inte att skapa en ändlig lista med alla primtal, så antalet primtal är oändligt.

[redigera] 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.

[redigera] 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?

[redigera] Se även

[redigera] Litteratur

Riesel, Hans, En bok om primtal, Lund 1968

[redigera] Externa länkar

Den här artikeln är hämtad från http://sv.wikipedia.org../../../p/r/i/Primtal.html

Kategori: Talteori