Et primtal er et positivt heltal, der er større end, som ikke er deleligt med andre hele positive tal end 1 samt tallet selv.
Ethvert positivt heltal kan skrives som et produkt af et primtal på entydig vis, hvis man ser bort fra rækkefølgen af primtallene. Dette kaldes for tallets primfaktoropløsning, mens de indgående primtal er kendt som tallets primfaktorer.
At ethvert positivt helt tal på entydig vis kan skrives som et produkt af primfaktorer, er kendt som aritmetikkens fundamentalsætning.
Det skal selvfølgelig nævnes, at 1 ikke er et primtal i henhold til den førnævnte definition, da det kræves, at tallet er større end 1, hvis det skal være et primtal. Derfor er 1 altså ikke et primtal i sig selv.
Man kunne principielt godt have defineret 1 som et primtal, men det havde dog medført, at den videre udvikling af teorien ville have været mere besværlig, eftersom mange sætninger kun er gældende for primtal, der er større end eller lig 2.
Ovenstående gør sig fx gældende for den tidligere oplyste entydighed af primfaktoropløsninger. Hvis 1 havde været defineret som et primtal, ville fx 60 kunne skrives som et produkt af et primtal på et uendeligt mange måder. Som følge af dette, er det ganske naturligt, at man ikke definerer 1 som et primtal.
Desuden bør det også nævnes, at primtal er noget, der bliver studeret meget indenfor talteori. Ydermere er primtal også noget, der danner basis for en lang række krypteringsalgoritmer.
Hvor mange primtal findes der?
Cirka 300 f.Kr. blev det af Euklid bevist, at der findes uendeligt mange primtal. Beviset anføres dog ofte at være et såkaldt modstridsbevis, da man i dag antager, at man nu har kendskab til alle primtal.
Hvis man ganger alle disse tal sammen og lægger en til, så får man et tal, der enten er et ikke-kendt primtal, eller som har en primfaktor, der ikke er kendt, eftersom der er ingen af dem, man har kendskab til dig, der kan gå op.
Faktisk gik Euklids bevisførelse ud på, at hvis blot man har en hvilken som helst mængde primtal, er det muligt at finde mindst ét primtal til. Fremgangsmåden for dette svarer til ovenstående. Og det er selvfølgelig muligt at gentage dette i det uendelige.
Desuden er der også flere andre matematikere, der har lavet andre beviser for, at der er et uendeligt antal primtal. Det gør sig blandt andet gældende for Euler, der har vist, at summen af primtallenes reciprokke værdier ikke konvergerer, men derimod går mod uendelig.
Primtallenes fordeling
Det er ikke svært at se, at der findes uendeligt mange primtal. Hvad der derimod ikke er helt så let, er at holde styr på, hvordan de mange primtal fordeler sig.
Hvis man kigger på en liste over primtal, ser det nemlig ganske tilfældigt og usystematisk ud. Det betyder også, at det kan virke næsten som et tilfælde, hvornår det næste primtal egentlig dukker op.
Til trods for, at det kan se ud til, at fordelingen af primtallene er uregelmæssige, når man ser på dem i lille skala, dukker der dog en form for regelmæssighed op, når man ser på antallet af primtal i store områder:
- Antal primtal under 1.000: 168 stk. (16,8 procent)
- Antal primtal under 1.000.000: 78.498 stk. (7,8 procent)
- Antal primtal under 1.000.000.000: 50.847.534 stk. (5,1 procent)
- Antal primtal under 1.000.000.000.000: 37.607.912.018 stk. (3,8 procent)
- Antal primtal under 1.000.000.000.000.000: 29.844.570.422.669 stk. (3,0 procent)
- Antal primtal under 1.000.000.000.000.000.000: 24.739.954.287.740.860 stk. (2,5 procent)
- Antal primtal under 1.000.000.000.000.000.000.000: 21.127.269.486.018.731.928 stk. (2,1 procent)
Primtalssætningen, der blev bevist i 1896, giver en specifik beskrivelse af denne regelmæssighed. Antallet af primtal mindre x kan approksimeres med x / (log x), da den relative fejl ved dette bliver forsvindende, når x går mod uendelig (her betegner log den naturlige logaritme).
Dog er det stadig ikke afklaret, hvor store udsving fra systematikken fra primtalssætningen, der forekommer. Er Riemann-hypotesen sand, er deres fordeling nemlig så ensartet, som det er teoretisk muligt.
Viser hypotesen sig derimod mod forventning at være falsk, vil det sige, at der derimod igennem hele talrække vil være forholdsvis store ‘bump’, hvor tætheden af primtallene ville afvige mere fra den ideelle, end den reelt ‘behøvede’.
Hvad er det største primtal?
Som følge af, at brugen af computere har gjort det muligt at regne med primtal på en helt ny måde, er der sket en kraftig udvikling i det største kendte primtal. Det største kendte primtal har stort set altid været i form af 2n-1, der kaldes for mersennetal. Det er dog ikke alle af disse tal, der rent faktisk er primtal.
På nuværende tidspunkt er det største kendte primtal blevet fundet den 7. december 2018 af GIMPS, som er en internetgruppe, der gør brug af overskydende computertid at finde mersenneprimtal. Dette tal består af intet mindre end 24.862.048 decimaler.
Desuden bliver alle primtal på over 1.000 cifre kaldt for et titanprimtal. Hvis en person finder et sådant tal, kan personen kalde sig selv for en ‘titan’.
Primtalstvillinger
Primtalstvillinger er to primtal, der kun har ét enkelt tal imellem sig. Der findes mange af disse primtal. Herunder kan du se en liste over en række primtalstvillinger:
- 3 og 5
- 5 og 7
- 11 og 13
- 17 og 19
- 101 og 103
- 22271 og 22273
- 57007007 og 57007009
- 1.000.000.000.061 og 1.000.000.000.063
Der er endnu ikke givet et klart svar på, hvorvidt der findes et uendeligt antal primtalstvillinger. Den mest almindelige opfattelse er dog, at der findes et uendeligt antal primtalstvillinger.
Det har den norske matematiker Viggo Brun forsøgt at bevise, hvilket han gjorde ved at bevise, at den reciprokke sum af alle primtalstvillinger var uendelig. Dog lykkedes det ham i 1919 at bevise, at summen var endelig, hvilket dog hverken kan bruges som et argument for eller imod, at antallet af primtalstvillinger er uendeligt.
Eksempelvis er den reciprokke sum af alle kvadrattal også endelig, men det ændrer dog ikke på det faktum, at der findes uendeligt mange kvadrattal.
At den reciprokke sum af primtalstvillinger er endelig, er dog et bevis på, at der findes markant færre primtalstvillinger end primtal, eftersom den reciprokke sum af alle primtal er uendelig.
Vigtigt, at vi har kendskab til egenskaber
Det største primtal har så mange cifre og er så langt, at det faktisk vil kunne strække sig over hele 9.000 sider i en bog. Til sammenligning mener forskerne ikke, at dét tal, der angiver antallet af atomer i hele det observerbare univers, har over 100 cifre. Det vidner om, hvor stort et tal, der er tale om her.
Tallet, der er blevet døbt M77232917, og kan findes ved at gange to med sig selv 77.232.917 gange og dernæst fratrække ét, er – som tidligere angivet – blev fundet ved hjælp af frivillig crowdsourcing via GIMPS-projektet, som indtil videre har brugt 14 år på at jagte nye primtal.
Det er dog ikke alle, der helt er med på, hvad der ligger til grund for, at vi egentlig skal vide noget om et tal, der har 23 millioner cifre. Det skyldes især, at de fleste mener, at de tal, der er de vigtigste, er de tal, som vi kan bruge til at kvantificere noget i vores egen verden.
Til trods for, at man skulle tro det, er det faktisk ikke sådan, det forholder sig. Derimod er det afgørende, at vi har kendskab til forskellige tals egenskaber, da vi dermed kan videreudvikle vores teknologi, men også sikre os, at den faktisk er sikker.
Primtalsfaktorisering
Primtalsfaktorisering er bestemt ikke nemt, hvilket er netop, hvad det såkaldte RSA-krypteringssystem udnytter. Det er en metode, hvor hele sikkerheden hviler på, at vi har viden om, at det er umuligt effektivt at faktorisere et helt tal i et produkt af primtal.
Det lyder sandsynligvis meget avanceret, hvorfor det er lettest at forklare det med et eksempel: Jan og Jette vil rigtig gerne kunne kommunikere fortroligt over nettet. Derfor har de brug for en form for krypteringssystem. Hvis de mødes ansigt til ansigt, er det muligt fro dem at udarbejde en metode til både kryptering og dekryptering, som kun de kender.
Hvis den første kommunikation er nødt til at ske på nettet, er de tvunget til først at kommunikere selve krypteringssystemet, hvilket kan være risikabelt.
Hvis Jan derimod udvælger to store primtal, beregner deres produkt og kommunikerer resultatet af dette, kan det vise sig at blive uhyre svært at afsløre hendes oprindelige primtal. Det skyldes naturligvis, at det kun er ham, der kender til faktorerne. Derefter kommunikerer Jan sit produkt til Jette, men holder faktorerne hemmelige.
Jette bruger dernæst produktet til at kryptere en besked til Jan. Denne besked vil kun være mulig at dekryptere ved at gøre brug af de faktorer, som kun Jan kender, da han ikke har oplyst disse faktorer til andre.
Selv i tilfælde af, at Jesper smuglytter, vil det ikke være muligt for ham at afkode Jettes besked, da det kræver, at han har et kendskab til Jans faktorer – og det har han ikke, for de er aldrig blevet delt med nogen.
Faktisk vil det ikke engang være muligt for selv den hurtigste supercomputer at hjælpe Jesper med at opløse tallet i primtalsfaktorer. Årsagen til dette er, at der ganske enkelt ikke findes en eneste algoritme, der kan gøre dette muligt.