Den matematiska definitionen på ett primtal är ett naturligt tal1 som är större än 1 och endast delbart med sig självt och 1. Det kan tyckas självklart att det finns sådana tal och man fäster kanske inte så mycket uppmärksamhet vid dem. Historiskt sett har primtalen spelat en viss roll och tilldragit sig en hel del intresse. I dag är de aktuella inom den gren av matematiken som heter talteori. De används i tillämpningar som rör kryptering, t ex RSA-kryptot är baserat på stora primtal. Även inom datorvetenskapen visas intresse för primtalen, bland annat gör man tester av beräkningskapacitet i form av program som letar upp stora primtal.
1De naturliga talen är de positiva heltalen inklusive noll.
Man kan konstatera att det finns oändligt många primtal. Det är lätt att anta att det är så, men inte lika lätt att visa. Euklides bevisade dock detta redan på 300-talet före Kristus. Förenklat bygger beviset på följande resonemang:
Anta att det finns ändligt många primtal, dvs vi skulle kunna räkna upp dem bara vi tog tillräckligt lång tid på oss. Vi antar att de är n stycken. Då kan vi kalla våra primtal för p1,p2, .. pn. Vi bildar talet P som produkten av alla våra primtal, dvs P=p1p2..pn+1. Då får vi resten 1 vid division med varje tal pk. P delas alltså inte av något i listan. Då måste det vara så att P antingen är ett primtal eller så är p en produkt av primtal som inte finns i listan. Detta bygger på den så kallade aritmetikens fundamentalsats.
Exempel: Vi har talet 8379. Det kan delas upp i faktorer som är primtal. 8379 = 3x3x7x7x19.
Alla heltal kan skrivas som en produkt av primtal och detta kan göras på endast ett sätt (bortsett från talens ordning). Detta samband brukar kallas för aritmetikens fundamentalsats.
Att finna primtalen görs enklast med någon metod som väljer ut de tal som uppfyller villkoren för primtal. Den äldsta metoden är Eratosthenes såll där man helt enkelt provar delbarheten för varje tal.