Primtal
Primtal er tal, der kun er delelige med en og med sig selv. Primtals egenskaber bruges ofte for eksempel i kryptografi.
Definition og eksempler
Et primtal er et naturligt tal, der uden rest kun er deleligt med en og med sig selv, og selve tallet en er ikke et primtal. Det mindste primtal er to — det er deleligt uden rest med en og med to. Det er samtidig det eneste primtal, der er lige. Alle andre primtal er ulige, fordi ethvert andet lige tal foruden at være deleligt med en og med sig selv også er deleligt med to.
Talfølgen af de første primtal: 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271…
Primtal hænger sammen med aritmetikkens fundamentalsætning, som siger, at ethvert helt tal større end 1 kan skrives som et produkt af primtal.
Test, om et tal er et primtal
Egenskaber ved primtal
- Der findes uendeligt mange primtal. Beviset findes i artiklen om modstridsbevis.
- For ethvert helt tal z>1 gælder, at der i intervallet ]z; 2z[ findes mindst ét primtal. Eksempel: for z = 2 har vi intervallet ]2; 4[. Det eneste hele tal i dette interval er tre, og det er et primtal. For z = 5 får vi intervallet ]5; 10[, altså tallene 6, 7, 8, 9. Tallet 7 er et primtal. Tilsvarende for højere z.
- Et Mersenne-primtal er et primtal, der er én mindre end en heltalspotens af to. Et Mersenne-primtal M har altså formen M = 2z − 1, hvor z er et naturligt tal. Et eksempel er primtallet 3, fordi 22 − 1 = 3. Eller 7, fordi 23 − 1 = 7.
- De største kendte primtal er typisk netop Mersenne-primtal. For eksempel blev Mersenne-primtallet M43112609, hvor det nedre indeks angiver eksponenten z, fundet den 23. august 2008. Det er altså primtallet 243112609 − 1, som har 12.978.189 cifre og dengang var det største kendte primtal.
Talfølge uden primtal
Man kan finde en vilkårligt lang endelig talfølge af på hinanden følgende naturlige tal, hvor der ikke forekommer et eneste primtal. En sådan talfølge kan have formen k!+2, k!+3, …, k!+k og indeholder k − 1 på hinanden følgende sammensatte tal (udråbstegnet er fakultet).
For eksempel får vi for k = 6 fem på hinanden følgende sammensatte tal på formen: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. Disse tal er henholdsvis delelige med to, tre, fire, fem og seks, fordi tallet 6! = 720 med sikkerhed er deleligt med alle disse tal, da det er opstået som deres produkt: 6! = 6 · 5 · 4 · 3 · 2. Hvis tallet 720 er deleligt med tre, så må tallet 720 + 3 også være deleligt med tre. Tilsvarende for de øvrige.
Fermats lille sætning
For ethvert primtal p og ethvert helt tal z gælder, at tallet zp − z er deleligt med primtallet p.
Eksempel: lad os tage primtallet p = 3 og det hele tal z = 4. Vi beregner værdien af tallet 43 − 4. Den er lig med 60. Samtidig gælder det, at 60/3 = 20, så tallet tre går op i tallet 60 uden rest, hvilket svarer til Fermats lille sætning. Et andet eksempel: p = 7, z = 10. Vi beregner delresultatet 107 − 10 = 9999990 og dividerer dette tal med syv: 9999990/7 = 1428570. Igen fik vi et resultat uden rest.
Uløste spørgsmål
Der findes mange kendte hypoteser om primtal, som det endnu (2011) ikke er lykkedes at bevise eller modbevise. To af de mest kendte er:
- Uendeligt mange primtalstvillinger: en primtalstvilling er et par af tal (z, z + 2), hvor begge tal er primtal. For eksempel (3, 5) eller (29, 31). Spørgsmålet er, om der findes uendeligt mange sådanne primtalstvillinger. Man antager, at der gør, men beviset mangler.
- Riemann-hypotesen: Alle ikke-trivielle nulpunkter for Riemanns zetafunktion har realdel lig med
