Primtal

11 är ett primtal, men inte 12.

Ett primtal, är ett heltal p, som är större än 1 och vars enda delare är ±1 och ±p.

Den grekiske matematikern Euklides visade på 300-talet f.Kr., med Euklides sats, att det finns ett oändligt antal primtal.

Egenskaper

Exempelvis är 7, 29 och 127 primtal, men inte 45 = 3·3·5, 91 = 7·13 och 2047 = 23·89.

Bland primtalen förekommer det att två på varandra följande udda tal är primtal, exempelvis 11 och 13 och 1949 och 1951. Dessa kallas primtalstvillingar, men det är inte känt om det finns oändligt många sådana par. De enda primtalstrillingarna är 3, 5 och 7 och primtalsfyrlingar eller större finns inte. Primtalen och deras fördelning har alltid varit ett område, som intresserat matematiker. Primtal spelar även en stor roll i talteorin.

Här följer alla primtal mindre än 100 (talföljd A000040 i OEIS):

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

Tvåkvadratsteoremet

Primtalen kan, om primtalet 2 utelämnas, delas upp i två klasser. De, som kan skrivas på formen 4n + 1 och de, som kan skrivas på formen 4n + 3. De förstnämnda är 5, 13, 17, 29, 37, ... och de senare är 3, 7, 11, 19, 23, ... . Alla primtal i den förra klassen, men inget i den senare kan uttryckas som summan av två heltalskvadrater. Sambandet upptäcktes av Fermat, som nämnde det i ett brev till matematikern Mersenne 1640. Teoremet har av den engelske matematikern Hardy klassats som ett av matematikens vackraste och kan formuleras som: Det udda primtalet p kan skrivas p = x² + y² där x och y är heltal om och endast om p = 4n + 1. Exempel:

5 = 1² + 2², 13 = 2² + 3², 61 = 5² + 6², 97 = 4² + 9², 641 = 4² + 25², 1949 = 10² + 43².

Primtalsbestämning

För att avgöra om ett tal p är ett primtal, kan man dividera detta med alla naturliga tal, som ligger mellan 1 och p .

En effektivare metod är att med hjälp av en primtalslista dela med alla primtal mellan 1 och det största heltal som är mindre än $\sqrt{p}$. Om p inte är ett primtal kan det skrivas som produkten av två tal av vilka ej båda kan vara större än $\sqrt{p}$:

$p=a\cdot b \quad \rightarrow \quad a \leq \sqrt{p} \quad eller \quad b \leq \sqrt{p}$

Exempel: 103

För att undersöka om ett tal är ett primtal räcker det således att pröva med alla primtal som är mindre än kvadratroten ur talet. Kvadratroten ur 103 är cirka 10 (10,14889157...) varför det räcker med att testa om 103 är delbart med något av talen 2, 3, 5 eller 7:

• Talet är udda och är därmed inte delbart med 2.
• Talets siffersumma (1 + 0 + 3) är inte delbar med 3, då är talet inte heller delbart med 3.
• Talet slutar inte på 0 eller 5 och är därför inte delbart med 5.
• Talet är inte delbart med 7

Alltså är 103 ett primtal.

Metoden ovan är ganska effektiv, men är inte särskilt användbar inom modern kryptografi där man använder sig av primtal bestående av hundratals siffror. Med hjälp av en persondator kan man primtalstesta ett tal bestående av 100 siffror inom loppet av en sekund. Ett av många primtalstest är en algoritm kallad Eratosthenes såll, med vars hjälp man kan bestämma alla primtal som är mindre än ett önskat tal.

Det största kända primtalet

Det läggs ner mycket arbete har på försöka hitta allt större primtal. Det största primtal som hittills har hittats är 2^43 112 609 − 1. Utskrivet med siffror (i bas 10) är talet 12 978 189 siffror långt. Primtalet hittades 23 augusti 2008 inom projektet Great Internet Mersenne Prime Search av matematikinstitutionen på University of California.

Det tidigare rekordet var 2^32 582 657 − 1, från 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, vars antal siffror självt är ett primtal, är 27 653 · 2^9 167 433 + 1 som har 2 759 677 siffror, utskrivet i bas 10.

Antalet primtal

Det finns oändligt många primtal, vilket bevisades av Euklides ca 300 f.Kr i Euklides sats.

Alternativt bevis

Leonhard Euler och Leopold Kronecker visade år 1876 att antalet primtal är knutet till den harmoniska serien via följande samband:

$\sum_{k=1}^\infty \frac{1}{k} = \prod_{p}\frac{1}{1-\frac{1}{p}},$

där produkten beräknas över samtliga primtal, hur många de nu är; kom ihåg att vi ännu inte vet att det finns oändligt många av dem.

Det faktum att den harmoniska serien är divergent innebär att produkten också är divergent, vilket den endast kan vara om den består av oändligt många faktorer, vilket innebär att antalet primtal är oändligt många.

Sambandet som Euler och Kronecker fann utgör startpunkten för det område inom matematik som kallas analytisk talteori; man använder resultat från matematisk analys för att studera problem inom talteori. Detta är en oväntad koppling, eftersom talteori sysslar med heltal (diskreta objekt) och matematisk analys med reella- och komplexa tal (icke-diskreta objekt).

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?

Tillämpningar

Under lång tid ansågs talteori i allmänet och studiet av primtal i synnerhet som utmärkande för ren matematik, utan några tillämpningar utanför den egna teorin. Särskilt talteoretiker, som exempelvis G.H. Hardy, var stolta över att bedriva forskning som saknade betydelse för militären. Hans visioner raserades när det offentliggjordes att primtal användes som byggstenar inom öppen-nyckel-kryptering.

Primtal används även för hashtabeller och pseudoslumptalsgeneratorer. En pseudoslumptalssekvens kan användas för utplacering av dubbar på ett dubbdäck för att undvika resonansfenomen.

Olika grupper av primtal

Allt efter egenskaper kan primtal kategoriseras i grupper, exempelvis.:

• Primtalstvillingar, det vill säga två primtal som ligger så nära varandra som möjligt (bortsett från exemplet med 2 och 3 innebär det att vara åtskilt av två, exempelvis 5 och 7 eller 17 och 19).
• Mersenneprimtal, primtal av formen 2ⁿ − 1.
• Fermatprimtal, primtal av formen $2^{2^n}+1$.
• Pythagoriska primtal, primtal av formen 4n + 1.
• Fakultetsprimtal, primtal av formen $n! \pm 1$

Av mer underhållande karaktär är de så kallade "James Bondprimtal", som är primtal som slutar med 007. De fyra första är 7 (007), 4007, 6007 och 9007.

Se även

• Gaussiska primtal
• Mersenneprimtal
• Primtalssatsen
• Perfekt tal
• Relativt prima
• Primtalstvilling
• Aritmetikens fundamentalsats
• Ulams spiral
• Primorial
• Kategori:Primtal
• Lista över primtal på Wikibooks
• Lista över primfaktorer på Wikibooks

Litteratur

• Riesel, Hans, En bok om primtal, Lund 1968

Externa länkar

• http://mathworld.wolfram.com/topics/PrimeNumbers.html
• http://www2.math.su.se/matematik/exempel/tal/primtal.html
• Geometry of prime numbers and perfect numbers
• http://primes.utm.edu/
• Lista över stora möjliga primtal
• http://www.utm.edu/research/primes/notes/proofs/infinite/.