Vad ett primtal är
Ett primtal är ett heltal större än 1 som bara är delbart med 1 och sig självt. Talet 7 är ett primtal eftersom inget annat heltal mellan 2 och 6 går jämnt upp i det. Talet 8 är däremot inte ett primtal, eftersom det också är delbart med 2 och 4.
Definitionen utesluter talet 1 med flit. Ett primtal ska ha exakt två delbarhetsfaktorer, 1 och talet självt, och 1 har bara en. Det gör 1 till ett specialfall som varken räknas som primtal eller sammansatt tal.
2 är det enda jämna primtalet. Alla andra jämna tal går att dela med 2 och är därför sammansatta, medan 2 självt bara är delbart med 1 och sig självt. Från och med 3 är därför varje primtal ett udda tal, även om långt ifrån alla udda tal är primtal.
Avgöra om ett tal är ett primtal
Den vanligaste metoden för hand är att pröva delbarhet med varje heltal från 2 och uppåt, men det räcker att testa upp till kvadratroten av talet. Om talet inte går att dela jämnt med något heltal upp till sin egen kvadratrot går det inte att dela jämnt med något större heltal heller, eftersom en sådan faktor alltid har en motsvarande, mindre faktor som redan skulle ha upptäckts.
Ta talet 97 som exempel. Kvadratroten av 97 är strax under 10, så det räcker att testa delbarhet med 2, 3, 5 och 7. Ingen av dem går jämnt upp i 97, vilket bekräftar att 97 är ett primtal.
För större tal blir det snabbt opraktiskt att testa för hand. Ett tal som 391 kräver att du provar delbarhet upp till 19, och då är en miniräknare ett enklare hjälpmedel än att räkna ut varje division i huvudet.
Lista över de första primtalen
De 25 första primtalen, alla under 100, är:
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
Listan visar tydligt att glappen mellan primtalen varierar. Mellan 2 och 3 är glappet bara 1, medan det mellan 23 och 29 är 6. Det finns inget enkelt mönster för vilken sista siffra ett primtal har, förutom att inget primtal större än 5 kan sluta på 0, 2, 4, 5, 6 eller 8, eftersom de siffrorna alltid gör talet delbart med 2 eller 5.
Primtal och sammansatta tal
Ett sammansatt tal är motsatsen till ett primtal: ett heltal större än 1 som har fler delbarhetsfaktorer än bara 1 och sig självt. Talet 12 är sammansatt eftersom det går att dela med 2, 3, 4 och 6, utöver 1 och 12.
Aritmetikens fundamentalsats säger att varje heltal större än 1 kan skrivas som en unik produkt av primtal, oavsett i vilken ordning faktorerna räknas fram. Den processen kallas primtalsfaktorisering.
Ett exempel: 12 kan delas upp i 2 och 6, och 6 kan delas upp vidare i 2 och 3. Kvar blir 2 × 2 × 3, där alla tre faktorerna är primtal. Ett större exempel är 60, som blir 2 × 2 × 3 × 5 när det bryts ner helt. Ingen annan kombination av primtal ger samma produkt, vilket är själva poängen med fundamentalsatsen.
Olika metoder: Eratosthenes såll
Eratosthenes såll är en gammal metod för att hitta alla primtal upp till ett visst tal N. Metoden bygger på att successivt stryka bort multiplerna av varje primtal som hittas.
- Skriv upp alla heltal från 2 till N.
- Ta det första kvarvarande talet (2) och stryk alla dess multipler (4, 6, 8 och så vidare), men inte talet självt.
- Gå till nästa kvarvarande tal (3) och stryk alla dess multipler på samma sätt.
- Upprepa för varje nytt kvarvarande tal upp till kvadratroten av N.
- Alla tal som blir kvar när sållningen är klar är primtal.
Metoden är särskilt praktisk när man vill hitta alla primtal inom ett intervall, snarare än att testa ett enda tal i taget.
Finns det oändligt många primtal?
Ja. Den grekiske matematikern Euklides bevisade det redan omkring 300 före Kristus, och beviset går att följa utan avancerad matematik.
Antag att det finns ett störst primtal. Multiplicera då alla primtal som finns, från 2 upp till det antagna största, och lägg till 1 på produkten. Det nya talet kan inte vara delbart med något av de primtal som redan räknats med, eftersom division med något av dem alltid lämnar en rest på 1. Talet måste därför ha en primtalsfaktor som inte fanns i den ursprungliga listan, vilket motsäger antagandet att listan innehöll alla primtal. Slutsatsen är att det aldrig går att peka ut ett störst primtal, och att det därför måste finnas oändligt många.