Primtall
Primtall er tall som bare er delelige med 1 og seg selv. Egenskapene til primtallene brukes ofte for eksempel i kryptografi.
Definisjon og eksempler
Et primtall er et naturlig tall som bare er delelig uten rest med 1 og seg selv, og tallet 1 er selv ikke et primtall. Det minste primtallet er 2 — det er delelig uten rest med 1 og 2. Det er også det eneste primtallet som er et partall. Alle andre primtall er oddetall, fordi ethvert annet partall er delelig både med 1, med seg selv og dessuten med 2.
Her er de første primtallene: 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…
Primtallene har en nær forbindelse til aritmetikkens fundamentalteorem, som sier at ethvert heltall større enn 1 kan skrives som et produkt av primtall.
Test om et tall er et primtall
Egenskaper ved primtall
- Det finnes uendelig mange primtall. Beviset står i artikkelen om motsigelsesbevis.
- For hvert heltall z>1 finnes det minst ett primtall i intervallet ⟨z, 2z⟩. Eksempel: for z = 2 får vi intervallet ⟨2, 4⟩. Det eneste heltallet i dette intervallet er 3, og det er et primtall. For z = 5 får vi intervallet ⟨5, 10⟩, altså tallene 6, 7, 8, 9. Tallet 7 er et primtall. På tilsvarende måte for høyere z.
- Et Mersenne-primtall er et primtall som er én mindre enn en heltallig potens av 2. Et Mersenne-primtall M har altså formen M = 2z − 1, der z er et naturlig tall. Et eksempel er primtallet 3, siden 22 − 1 = 3. Eller 7, siden 23 − 1 = 7.
- De største kjente primtallene er som regel nettopp Mersenne-primtall. For eksempel ble Mersenne-primtallet M43112609 funnet 23. august 2008, der den nedre indeksen angir eksponenten z. Det er altså primtallet 243112609 − 1, som har 12 978 189 siffer og som den gangen var det største kjente primtallet.
En følge uten primtall
Man kan finne en vilkårlig lang endelig følge av etterfølgende naturlige tall der ikke ett eneste er et primtall. En slik følge kan ha formen k!+2, k!+3, …, k!+k og inneholder k − 1 etterfølgende sammensatte tall (utropstegnet betyr fakultet).
For eksempel får vi for k = 6 fem etterfølgende sammensatte tall på formen 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. Disse tallene er etter tur delelige med 2, 3, 4, 5 og 6, siden tallet 6! = 720 helt sikkert er delelig med alle disse tallene, for det er produktet av dem: 6! = 6 · 5 · 4 · 3 · 2. Hvis tallet 720 er delelig med 3, må også tallet 720 + 3 være delelig med 3. Tilsvarende for de andre.
Fermats lille teorem
For hvert primtall p og hvert heltall z er tallet zp − z delelig med primtallet p.
Eksempel: la oss ta primtallet p = 3 og heltallet z = 4. Vi regner ut verdien av 43 − 4. Den er lik 60. Samtidig er 60/3 = 20, så 3 går opp i 60 uten rest, i samsvar med Fermats teorem. Et annet eksempel: p = 7, z = 10. Vi regner ut delresultatet 107 − 10 = 9999990 og deler det på 7: 9999990/7 = 1428570. Igjen fikk vi et svar uten rest.
Uløste spørsmål
Det finnes mange kjente hypoteser om primtall som ennå (2011) ikke er blitt bevist eller motbevist. To av de mest kjente er:
- Uendelig mange primtallstvillinger: primtallstvillinger er et par av tall (z, z + 2) der begge tallene er primtall. For eksempel (3, 5) eller (29, 31). Spørsmålet er om det finnes uendelig mange slike par. Man antar at det gjør det, men beviset mangler.
- Riemann-hypotesen: alle ikke-trivielle nullpunkter til Riemanns zetafunksjon har realdel lik
