Primtal

Vad är ett primtal?

För att förstå primtal kan vi titta på några exempel. Talet 2 är det minsta primtalet, eftersom det bara är delbart med 1 och 2. Andra primtal inkluderar 3, 5, 7, 11, 13, 17, 19 och så vidare. 

Som du ser är alla exempel vi tog upp heltal – det är ingen slump! Ett primtal måste vara ett heltal och vara större än 1. Alltså kan inte tal som -3, ½ eller 2,5 vara primtal.

Vilka primtal finns det?

Det finns oändligt många primtal, vilket är ett resultat som går tillbaka till antikens grekiska matematiker Euklides. Det finns ingen övre gräns för antalet primtal och de fortsätter att existera och upptäckas allteftersom talen blir större!

Lista på de första primtalen under 100

Eftersom att det finns oändligt många primtal är det ingen idé att försöka memorera dem allihop – men det kan underlätta att lägga några av de första på minnet!

De första primtalen ä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

När använder man primtal?

Kryptografi: Primtal används inom kryptografi, det vill säga studien av säker kommunikation och dataskydd. Specifikt används primtalsfaktorisering för att skapa säkra kryptografiska algoritmer. Till exempel används RSA-krypteringssystemet som bygger på svårigheten att faktorisera stora primtal, för att säkra kommunikationen och skydda information mot obehörig åtkomst.

Primtalsgeneratorer: Primtal används inom datavetenskap och programmering för att generera slumpmässiga tal. Primtalsgeneratorer är viktiga inom områden som simulering, kryptografisk nyckelgenerering och tillfällig primtalsbaserad aritmetik.

Talteori: Primtal är centrala inom talteorin – en gren av matematiken som studerar egenskaperna hos heltal. Forskning inom talteori syftar till att förstå primtalens fördelning, primtalstvillingar (par av primtal som endast skiljer sig med 2) och andra primtalsmönster.

Matematisk analys: Primtal används inom matematisk analys för att undersöka konvergens och divergens av vissa talserier, såsom Riemanns zeta-funktion. Riemannhypotesen, som är en olöst matematisk gåta, är starkt kopplad till primtalens fördelning och deras relation till Riemanns zeta-funktion.

Algoritmer: Primtal används inom olika algoritmer och problem inom datavetenskap, inklusive primtalsprimtal, primtalsfaktorisering och primtalstestning. Dessa algoritmer är grundläggande för många tillämpningar inom beräkningsvetenskap, inklusive kryptografi, datakomprimering och datalagring.

Metoder för att identifiera primtal

För att avgöra om ett tal är ett primtal, kan primtalsprovning användas. Det finns olika algoritmer för primtalsprovning, såsom Miller-Rabin testet.

I enkla termer fungerar testet genom att man gör upprepade slumpmässiga tester på det givna talet för att se om det verkar vara ett primtal eller inte.

Algoritmen fungerar genom att slumpmässigt välja ett antal små tal, kallade ”vittnen” och testa dem mot det givna talet för att se om de uppfyller vissa kriterier som är karakteristiska för primtal. Om det givna talet klarar av testet för ett tillräckligt stort antal slumpmässigt valda vittnen, betraktas det som ett primtal med hög sannolikhet!

Det som gör Miller-Rabin-testet användbart är att det är snabbt och effektivt även för mycket stora tal, vilket är viktigt inom områden som kryptografi där man ofta behöver hantera stora primtal. Även om algoritmen inte ger ett absolut bevis för primtalitet, ger den en stark indikation på om ett tal är ett primtal eller inte.

Primtalsfaktorisering, å andra sidan, handlar om att bryta ner ett tal i dess primfaktorer. Detta kan vara användbart för att lösa problem såsom att hitta den största gemensamma faktorn eller för att lösa ekvationer.

---

Räkneexempel och förklaringar av primtal

De allra flesta tal är delbara med fler tal än bara 1 och sig självt, till skillnad från primtal. Ett tal som inte räknas som ett primtal kallar vi istället för ett sammansatt tal. Till exempel vet vi att 10 är delbart med 1, 2, 5 och 10, vilket gör 10 till ett sammansatt tal.

Vi ser att 10 är ett sammansatt tal eftersom 10 kan skrivas som 10={5}\cdot{2}={10}\cdot{1}. Vi säger att 1, 2, 5 och 10 är delare till 10.

En delare är ett tal som kan dela ett annat tal så att det går jämnt ut. En delare till ett tal måste vara ett heltal som är större än 1. Tal som 3, 4 och 14 kan alltså vara delare. Tal som -3, \frac{1}{2} och 2,5 kan däremot inte vara delare. 

Det är även viktigt att vi får ett heltal när vi delar talet med dess delare. Vi menar alltså att talet ska vara jämnt delbart när vi påstår att det är delbart. Vi ser till exempel att 2 är en delare till 10 eftersom \frac{10}{2}=5. 

Exempel 1: Är 4 en delare till 10?

Svar: Nej.

Lösning: Talet 4 är dock inte en delare till 10 eftersom \frac{10}{4}=2,5. Vi får alltså inte ett heltal när vi delar 10 med 4.

Om vi vill undersöka vare sig ett tal är ett primtal eller inte testar vi om talet har några delare förutom 1 och talet självt. 

Att testa om varenda tal är en delare blir jobbigt. Dock kan vi använda oss av ett par olika uteslutningsmetoder för att göra det enkelt för oss själva. 

Jämna tal, med undantag för 2, är alltid sammansatta tal. Vi vet alltså att dessa inte är primtal. Att 2 är det enda jämna primtalet beror på att alla jämna tal är delbara med 2. Likaså är 5 det enda primtalet som slutar på 5 eftersom att alla tal vars sista siffra är 5 även är delbara med 5.

När vi vill ta reda på om ett tal är ett primtal eller inte räcker det med att testa alla udda tal upp till talet delat på 2. Vi behöver inte testa 1. Om inga av talen vi undersökte är delare så vet vi att talet är ett primtal.

Exempel 2: Är 17 ett primtal? 

Svar: Ja.

Lösning: När vi vill undersöka ett tal, som till exempel 17, börjar vi alltså med att dela talet på 2. 

\frac{17}{2}=8,5

Vi behöver endast testa de udda talen mellan 1 och 8,5, alltså 3, 5 och 7. Vi testar och upptäcker att varken 3, 5 eller 7 är delare till 17. Därmed är 17 ett primtal.

---

Primtalsfaktorisera

Alla heltal kan primtalsfaktoriseras. Att primtalsfaktorisera ett tal innebär att vi skriver om talet till en multiplikation av primtal. Vi inkluderar inte 1 i faktoriseringen. För talet 18 ser primtalsfaktoriseringen ut så här: 

18= {2}\cdot{9}= {2}\cdot{3}\cdot{3}

När ingen av faktorerna (talen i multiplikationen) kan delas upp ytterligare vet vi att faktoriseringen är klar. Alla tal som vi då lämnas med är primtal!

---

Minsta gemensamma multipel

Faktorisering är användbart i flera sammanhang i matematiken, bland annat när vi räknar ut en minsta gemensamma multipel (förkortas MGM). 

En multipel av ett tal är ett tal som finns i det andra talets multiplikationstabell. Till exempel är 6 en multipel av 2 eftersom 6 finns i tvåans tabell ({2}\cdot{3}=6).

En minsta gemensamma multipel är det minsta talet där två tals tabeller möts. Tvåans och treans tabell möts först vid 6 ({2}\cdot{3}=6 och {3}\cdot{2}=6), vilket betyder att 6 är den minsta gemensamma multipeln för 2 och 3.

När vi vill hitta den minsta gemensamma multipeln av två tal börjar vi med att primtalsfaktorisera talen. Vi skriver alltså om talen till en multiplikation av primtal. 

Sedan multiplicerar vi talens gemensamma faktorer med talens icke gemensamma faktorer. Talet vi får är vår minsta gemensamma multipel.

Exempel 3: Vilken är den minsta gemensamma multipeln för 18 och 30?

Svar: 90

Lösning: Vi börjar med att dela upp talen 18 och 30 i primtal.

18= {2}\cdot{9}= {2}\cdot{3}\cdot{3}

30= {2}\cdot{15}= {2}\cdot{3}\cdot{5}

Vi ser att talens gemensamma faktorer är 2 och 3. 18 har även en extra faktor 3, medan 30 har en faktor 5. Nu multiplicerar vi talens gemensamma faktorer (2 och 3) med talens icke gemensamma faktorer (3 och 5). 

{2}\cdot{3}\cdot{3}\cdot{5}=90

Vi får alltså att 90 är den minsta gemensamma multipeln för 18 och 30.

---