Primtal – testa om ett tal är primtal

Vad är ett primtal?

Ett primtal är ett heltal större än 1 som bara är delbart med 1 och med sig självt. 2, 3, 5, 7 och 11 är primtal. 6 är inte ett primtal, eftersom 6 = 2 · 3. Tal som inte är primtal, och som är större än 1, kallas sammansatta tal.

Talet 1 räknas inte som ett primtal. Talet 1 har bara en delare, sig självt, och uppfyller alltså inte definitionen. Att hålla 1 utanför gör dessutom att varje heltal större än 1 får exakt en uppdelning i primtal. Den uppdelningen kallas primtalsfaktorisering och räknas ut av kalkylatorn för primtalsfaktorisering.

2 är det enda jämna primtalet. Alla andra jämna tal är delbara med 2 och därmed sammansatta. På samma sätt är 5 det enda primtalet som slutar på 5, eftersom alla andra tal som slutar på 0 eller 5 är delbara med 5. Därför slutar alla primtal utom 2 och 5 på 1, 3, 7 eller 9.

Så testar man om ett tal är ett primtal

Det enklaste sättet är att pröva att dela talet med 2, 3, 5, 7 och så vidare. Går någon division jämnt upp är talet sammansatt. Det räcker att pröva upp till roten ur talet. Har talet en delare som är större än roten, måste den andra faktorn vara mindre än roten, och då hade du redan hittat den.

Exempel: är 97 ett primtal? $\sqrt{97}\approx \mathrm{9,8}$, så du behöver bara pröva 2, 3, 5 och 7. Ingen av dem går jämnt upp, och kalkylatorn svarar att 97 är ett primtal. Närmaste primtal är 89 och 101.

Är 91 ett primtal? Många gissar ja, eftersom 91 är udda och inte delbart med 3 eller 5. Men $91=7·13$, så 91 är sammansatt med minsta delaren 7. Samma fälla gäller 119, som är 7 · 17, och 1 001, som har faktorerna 7 · 11 · 13.

För stora tal blir det för många delare att pröva för hand. Talet 2 147 483 647, alltså $2^{31}-1$, har en rot på drygt 46 000. Kalkylatorn använder i stället Miller–Rabins test, som avgör saken säkert för alla tal upp till ungefär 9 biljarder. För det talet blir svaret att det är ett primtal.

Snabba tester för delbarhet

Innan du börjar dela kan du utesluta många tal med delbarhetsreglerna:

• Delbart med 2 om sista siffran är jämn.
• Delbart med 3 om siffersumman är delbar med 3. 111 har siffersumman 3, så 111 = 3 · 37.
• Delbart med 5 om talet slutar på 0 eller 5.
• Delbart med 11 om skillnaden mellan summan av siffrorna på udda och jämna platser är delbar med 11.

Klarar talet alla dessa tester återstår 7, 13, 17 och större primtal upp till roten.

Eratosthenes såll

Vill du hitta alla primtal upp till ett visst tal är Eratosthenes såll smidigast. Skriv upp talen från 2. Ringa in 2 och stryk alla multipler av 2. Ringa in nästa tal som inte är struket, 3, och stryk alla multipler av 3. Fortsätt tills du kommit förbi roten ur det största talet. De tal som är kvar är primtal. Det är samma metod kalkylatorn använder i listläget.

Mellan 1 och 100 finns 25 primtal, mellan 1 och 1 000 finns 168 och under 10 000 finns 1 229. Primtalen glesnar alltså ju högre upp man kommer, men de tar aldrig slut. Att det finns oändligt många primtal går att bevisa: anta att det bara finns ändligt många, multiplicera ihop alla och lägg till 1. Det nya talet är inte delbart med något av primtalen i listan, så listan kan inte ha varit komplett.

Vanliga fel

• Att räkna 1 som primtal. Det är det inte.
• Att tro att alla udda tal är primtal. 9, 15, 21, 27 och 91 är udda men sammansatta.
• Att sluta pröva för tidigt. 119 är inte delbart med 2, 3 eller 5, men 119 = 7 · 17.
• Att pröva längre än nödvändigt. Du behöver aldrig pröva delare större än roten ur talet.

Typiska uppgifter

En vanlig uppgift är att avgöra om ett tal som 143 är ett primtal. Lösningsgången är att räkna ut roten, ungefär 12, och sedan pröva 2, 3, 5, 7 och 11. Eftersom 143 = 11 · 13 är svaret nej. En annan typ är att lista alla primtal mellan två tal, till exempel mellan 50 och 70: 53, 59, 61 och 67. En tredje typ ber dig förklara varför ett jämnt tal större än 2 aldrig kan vara ett primtal.

Primtal hänger också ihop med största gemensamma delare och minsta gemensamma nämnare. Två olika primtal har alltid SGD 1, och deras MGN är produkten av dem.

Var används primtal?

Primtal är grunden för mycket av den kryptering som skyddar internet. Det är lätt att multiplicera två stora primtal, men mycket svårt att gå baklänges och hitta faktorerna om man bara har produkten. Räkning med rester, som modulokalkylatorn visar, är en del av samma matematik. Datorer arbetar dessutom ofta med tal i andra talbaser, som talbasomvandlaren räknar om.

Primtal dyker upp även i andra talföljder. I Fibonaccis talföljd är till exempel 2, 3, 5, 13 och 89 primtal, men de flesta större Fibonaccital är sammansatta. Att dela ett tal med rest, som kalkylatorn för kvot och rest gör, är det som ligger bakom varje provdivision.

Så gör du på räknaren

• Räkna ut roten ur talet för att veta hur långt du behöver pröva.
• Dela talet med varje primtal upp till roten. Blir svaret ett heltal har du hittat en delare.
• Vissa räknare kan primtalsfaktorisera direkt. Visar den bara talet självt är talet ett primtal.

Fler kalkylatorer om delare, rester och talföljder finns bland kalkylatorerna för talteori och aritmetik och på matematiksidan.