Hoppa till innehållet
Hem

Primtal: definition, egenskaper och betydelse

Primtal är heltal större än 1 som endast är delbara med 1 och sig själva. Artikeln går igenom definition, grundläggande satser, historik, användningar och några öppna problem.

Författare: Skapad: Uppdaterad:

Översikt

Ett primtal är ett heltal större än 1 som inte kan skrivas som produkten av två mindre positiva heltal. Med andra ord har ett primtal precis två positiva delare: 1 och talet självt. De första primtalen är 2, 3, 5, 7, 11 och 13; observera att 2 är det enda jämna primtalet. För en introduktion till mängden av naturliga tal se naturliga tal, och för kontrasten mot tal som kan faktoriseras, se sammansatta tal. 1 räknas inte som ett primtal.

{\displaystyle m\times n}

Bildgalleri

9 Bilder
File:Prime_rectangles.png
simple.wikipedia.org · Public domain

Egenskaper och grundläggande resultat

En av de viktigaste satsarna i talteori är aritmetikens grundläggande sats, som säger att varje positivt heltal kan skrivas på ett unikt sätt (upp till ordning) som en produkt av primtal. Detta gör primtalen till de "byggstenar" som alla heltal består av. För större tal blir det dock svårare att avgöra om de är primtal — både teoretiskt och praktiskt — och för detta finns effektiva tester och heuristiska resultat.

  • Primtalssatsen beskriver den asymptotiska fördelningen av primtal och är en viktig del av analytisk talteori: se primtalssatsen.
  • Det finns oändligt många primtal; det klassiska beviset gavs av Euklid redan i antiken.

Metoder för att känna igen och hitta primtal

Metoderna varierar beroende på talens storlek. För små tal räcker prövningsdivision; för mycket stora tal används probabilistiska eller deterministiska algoritmer, till exempel Miller–Rabin (probabilistisk) och AKS (deterministisk). I praktiska tillämpningar kombineras ofta flera tester för att nå både snabbhet och säkerhet.

  1. Prövningsdivision: testa delbarhet upp till kvadratroten.
  2. Probabilistiska tester: snabbare, med liten risk för fel.
  3. Deterministiska polynom-tidstester: teoretiskt viktiga för stora tal.
{\displaystyle \mathbb {P} }

Historia och utveckling

Studiet av primtal sträcker sig tillbaka till antiken, där grekiska matematiker utvecklade grundläggande begrepp. Under 1700– och 1800-talen formaliserades många satser inom talteori. På 1900‑talet och framåt har analytiska metoder, datorer och algoritmer ökat förmågan att hitta mycket stora primtal, till exempel Mersenne-primtal, och att studera fördelningen via primtalssatsen.

Tillämpningar, särskilda typer och öppna problem

Primtal är centrala i modern kryptografi, inte minst i system som RSA där säkerheten bygger på svårigheten att faktorisera stora tal. Det finns även många särskilda klasser av primtal som intresserar matematikersamhället: Mersenne-primtal, Fermat-primtal, primtal i aritmetiska progressioner och tvillingprimtal. Bland kända olösta problem finns Goldbachs gissning och tvillingprimtalsförmodan. För information om positiva heltal som bas för faktorisering, se positivt heltal.

Fördjupning och ytterligare läsning kan du hitta via introduktioner och vetenskapliga översikter; övergripande resurser om primtal och relaterade satser finns också på pedagogiska webbplatser och i populärvetenskapliga sammanställningar — se till exempel resurser markerade här: grundläggande talbegrepp, sammansatta tal, faktoruppdelning, heltal, fördelning av primtal, kända gissningar och historiska bidrag som Euklids arbete.

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.  
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:

  1. 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.
  2. Börja med b lika med 2. Gå till nästa steg.
  3. Cirkla runt b i listan. Gå till nästa steg.
  4. 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.)
  5. Öka b med 1. Gå till nästa steg.
  6. 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.
  7. (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.

Relaterade artiklar

Författare

AlegsaOnline.com Primtal: definition, egenskaper och betydelse

URL: https://sv.alegsaonline.com/art/79128

Dela

Källor