Ö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}

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.