Primtal | naturligt tal av ett visst slag

Ett primtal är ett naturligt tal av ett visst slag. Varje naturligt tal är lika med 1 gånger sig självt. Om talet är lika med alla andra naturliga tal multiplicerat kallas talet för ett sammansatt tal. Det minsta sammansatta talet är 4, eftersom 2 x 2 = 4. 1 är inte ett sammansatt tal. Varje annat tal är ett primtal. Primtalen är de andra tal än 1 som inte är lika med m × n {\displaystyle m\times n} $m\times n$ (utom 1 gånger sig själv). Det minsta primtalet är 2. De följande primtalen är 3, 5, 7, 11 och 13. Det finns inget största primtal. Mängden primtal skrivs ibland som P {\displaystyle \mathbb {P} } $\mathbb {P}$ .

Enligt aritmetikens grundläggande sats kan varje positivt heltal skrivas som en produkt av primtal på ett unikt sätt, även om det är ett svårt problem för matematiker att avgöra hur primtalen uppstår. När ett tal är större är det svårare att veta om det är ett primtal. Ett av svaren är primtalssatsen. Ett av de olösta problemen är Goldbachs gissning.

En av de mest kända matematikerna från den klassiska eran, Euklid, lade fram ett bevis för att det inte finns något största primtal. Många vetenskapsmän och matematiker söker dock fortfarande efter det som en del av den stora Internet Mersenne Prime Search.

Här är ett annat sätt att tänka på primtal. Talet 12 är inte primtal, eftersom det går att göra en rektangel med sidorna 4 och 3. Denna rektangel har en area på 12, eftersom alla 12 klossar används. Detta kan inte göras med 11. Oavsett hur rektangeln arrangeras kommer det alltid att finnas block kvar, utom i rektangeln med sidorna med längderna 11 och 1. 11 måste därför vara ett primtal.

Hur man hittar små primtal

Det finns en enkel metod för att hitta en lista över primtal. Eratosthenes skapade den. Den kallas Eratosthenes sil. Den fångar upp tal som inte är primtal (som en sil) och låter primtalen passera igenom.

Metoden arbetar med en lista med nummer och ett särskilt nummer, b, som ändras under metoden. När man går igenom metoden cirklar man runt vissa nummer i listan och stryker andra. Varje inringat tal är ett primtal och varje överstruket tal är ett sammansatt tal. I början är alla tal vanliga: de är inte inringda och inte överstrukna.

Metoden är alltid densamma:

Skriv alla hela tal från 2 upp till det tal som ska testas på ett papper. Skriv inte ner siffran 1. Gå till nästa steg.
Börja med b lika med 2. Gå till nästa steg.
Cirkla runt b i listan. Gå till nästa steg.
Börja med b och räkna upp ytterligare b i listan och stryk det numret. Upprepa att räkna upp ytterligare b nummer och stryka ut nummer tills listan är slut. Gå till nästa steg.

(Till exempel: När b är 2, ska du sätta en cirkel runt 2 och stryka över 4, 6, 8 och så vidare. När b är 3, ska du ringa in 3 och stryka 6, 9, 12 och så vidare. 6 och 12 har redan strukits ut. Stryk dem igen.)

Öka b med 1. Gå till nästa steg.
Om b har strukits över, gå tillbaka till föregående steg. Om b är ett nummer i listan som inte har strukits över, gå till det tredje steget. Om b inte finns i listan, gå till det sista steget.
(Detta är det sista steget.) Du är klar. Alla primtal är inringade och alla sammansatta tal är överstrukna.

Man kan t.ex. använda denna metod på en lista med tal från 2 till 10. Till slut kommer siffrorna 2, 3, 5 och 7 att vara inringade. Dessa är primtal. Numren 4, 6, 8, 9 och 10 kommer att strykas över. Dessa är sammansatta tal.

Denna metod eller algoritm tar för lång tid att hitta mycket stora primtal. Den är dock mindre komplicerad än de metoder som används för mycket stora primtal, t.ex. Fermats primtalstest (ett test för att se om ett tal är primtal eller inte) och Miller-Rabins primtalstest.

Vad används primtalen till?

Primtal är mycket viktiga inom matematik och datavetenskap. Mycket långa tal är svåra att lösa. Det är svårt att hitta deras primfaktorer, så oftast används tal som troligen är primtal för kryptering och hemliga koder. Till exempel:

De flesta människor har ett bankkort, med vilket de kan hämta pengar från sitt konto i en bankomat. Kortet är skyddat av en hemlig kod. Eftersom koden måste hållas hemlig kan den inte lagras i klartext på kortet. Kryptering används för att lagra koden på ett hemligt sätt. Denna kryptering använder multiplikationer, divisioner och att hitta rester av stora primtal. En algoritm som kallas RSA används ofta i praktiken. Den använder sig av det kinesiska restsatsen.

Om någon har en digital signatur för sitt e-postmeddelande används kryptering. Detta säkerställer att ingen kan förfalska ett e-postmeddelande från dem. Innan signeringen skapas ett hashvärde av meddelandet. Detta kombineras sedan med en digital signatur för att skapa ett signerat meddelande. Metoderna som används är mer eller mindre desamma som i det första fallet ovan.

Att hitta det största kända primtalet har under årens lopp blivit en sport. Att testa om ett tal är primtal kan vara svårt om talet är stort. De största primtalen som är kända vid någon tidpunkt är vanligtvis Mersenne-rimtal, eftersom det snabbaste kända testet för primtal är Lucas-Lehmer-testet, som bygger på Mersenne-talens speciella form.

Relaterade sidor

Coprime
Förteckning över primtal
Palindromiskt primtal
Faktorisering av primtal
Wilson prime

Frågor och svar

Fråga: Vad är ett primtal?

S: Ett primtal är ett naturligt tal som inte kan delas av något annat naturligt tal än 1 och sig självt.

Fråga: Vad är det minsta sammansatta talet?

S: Det minsta sammansatta talet är 4, eftersom 2 x 2 = 4.

Fråga: Vilka är de närmaste primtalen efter 2?

S: De närmaste primtalen efter 2 är 3, 5, 7, 11 och 13.

Fråga: Finns det ett största primtal?

Svar: Nej, det finns inget största primtal. Mängden primtal är oändlig.

Fråga: Vad säger den grundläggande aritmetiska satsen?

Svar: Aritmetikens grundläggande sats säger att varje positivt heltal kan skrivas som en produkt av primtal på ett unikt sätt.

F: Vad är Goldbachs gissning?

S: Goldbachs gissning är ett olöst problem inom matematiken som säger att varje jämnt heltal större än två kan uttryckas som summan av två primtal.

F: Vem har bevisat att det inte finns något största primtal?

Svar: Euklid bevisade att det inte fanns något största primtal.