Primtal | naturligt tal af en bestemt slags

Et primtal er et naturligt tal af en bestemt slags. Ethvert naturligt tal er lig med 1 gange sig selv. Hvis tallet er lig med andre naturlige tal ganget med hinanden, kaldes tallet for et sammensat tal. Det mindste sammensatte tal er 4, fordi 2 x 2 = 4. 1 er ikke et sammensat tal. Alle andre tal er et primtal. Primtal er de andre tal end 1, som ikke er lig med m × n {\displaystyle m\times n} $m\times n$ (undtagen 1 gange sig selv). Det mindste primtal er 2. De næste primtal er 3, 5, 7, 11 og 13. Der findes ikke noget største primtal. Mængden af primtal skrives undertiden som P {\displaystyle \mathbb {P} } $\mathbb {P}$ .

Den grundlæggende sætning i aritmetik fastslår, at ethvert positivt heltal kan skrives som et produkt af primtal på en unik måde, selv om måden, hvorpå primtalene forekommer, er et vanskeligt problem for matematikere. Når et tal er større, er det sværere at vide, om det er et primtal. Et af svarene er primtalteoremet. Et af de uløste problemer er Goldbachs formodning.

En af de mest berømte matematikere fra den klassiske æra, Euklid, har ført bevis for, at der ikke findes noget største primtal. Mange forskere og matematikere søger dog stadig efter det som led i den store Mersenne Prime Search på internettet.

Her er en anden måde at tænke på primtal på. Tallet 12 er ikke primtal, fordi der kan laves et rektangel med siderne 4 og 3 lange. Dette rektangel har et areal på 12, fordi alle 12 klodser er brugt. Dette kan ikke lade sig gøre med 11. Uanset hvordan rektanglet er indrettet, vil der altid være klodser tilbage, bortset fra rektanglet med sider af længderne 11 og 1. 11 må derfor være et primtal.

Sådan finder du små primtal

Der findes en simpel metode til at finde en liste over primtal. Eratosthenes skabte den. Den har navnet Eratosthenes' si. Den fanger tal, der ikke er primtal (som en sigte), og lader primtalene passere igennem.

Metoden arbejder med en liste af tal og et særligt tal kaldet b, som ændres undervejs i metoden. Efterhånden som man gennemgår metoden, omkredser man nogle tal på listen og streger andre ud. Hvert indcirklet tal er et primtal, og hvert overstreget tal er et sammensat tal. I begyndelsen er alle tallene almindelige: de er ikke omkredset og ikke overstreget.

Metoden er altid den samme:

Skriv alle hele tal fra 2 og op til det tal, der skal testes, på et stykke papir. Tallet 1 må ikke skrives ned. Gå til næste trin.
Start med b lig med 2. Gå til næste trin.
Cirkel b på listen. Gå til næste trin.
Start fra b, tæl b mere opad på listen og streger dette tal ud. Gentag det med at tælle b tal mere op og strege numre ud indtil listen er slut. Gå til næste trin.

(For eksempel: Når b er 2, omkredser du 2 og streger 4, 6, 8 osv. ud. Når b er 3, skal du sætte en cirkel om 3 og krydse 6, 9, 12 osv. ud. 6 og 12 er allerede blevet overstreget. Sæt kryds igen.)

Forøg b med 1. Gå til næste trin.
Hvis b er blevet overstreget, skal du gå tilbage til det foregående trin. Hvis b er et tal på listen, som ikke er blevet overstreget, skal du gå til tredje trin. Hvis b ikke er på listen, skal du gå til det sidste trin.
(Dette er det sidste trin.) Du er færdig. Alle primtal er omkredset, og alle sammensatte tal er overstreget.

Man kan f.eks. anvende denne metode på en liste over tallene fra 2 til 10. Til sidst vil tallene 2, 3, 5 og 7 være indcirklet. Disse er primtal. Tallene 4, 6, 8, 9 og 10 vil blive overstreget. Det er sammensatte tal.

Denne metode eller algoritme tager for lang tid til at finde meget store primtal. Den er dog mindre kompliceret end de metoder, der anvendes til meget store primtal, f.eks. Fermats primtalstest (en test for at se, om et tal er primtal eller ej) og Miller-Rabin-primtalstesten.

Hvad primtal bruges til

Primtal er meget vigtige inden for matematik og datalogi. Meget lange tal er svære at løse. Det er svært at finde deres primfaktorer, så for det meste bruges tal, der sandsynligvis er primtal, til kryptering og hemmelige koder. For eksempel:

De fleste mennesker har et bankkort, hvor de kan hæve penge fra deres konto ved hjælp af en hæveautomat. Dette kort er beskyttet af en hemmelig adgangskode. Da koden skal holdes hemmelig, kan den ikke gemmes i klartekst på kortet. Kryptering bruges til at lagre koden hemmeligt. Ved denne kryptering anvendes multiplikationer, divisioner og søgning efter resten af store primtal. En algoritme kaldet RSA anvendes ofte i praksis. Den anvender den kinesiske restsætning.

Hvis en person har en digital signatur til sin e-mail, anvendes kryptering. Dette sikrer, at ingen kan forfalske en e-mail fra dem. Før signeringen oprettes en hash-værdi af meddelelsen. Denne kombineres derefter med en digital signatur for at frembringe en signeret meddelelse. De metoder, der anvendes, er mere eller mindre de samme som i det første tilfælde ovenfor.

At finde det største kendte primtal er i årenes løb blevet en slags sport. Det kan være vanskeligt at afprøve, om et tal er primtal, hvis tallet er stort. De største primtal, der er kendt til enhver tid, er normalt Mersenne-rimtal, fordi den hurtigste kendte test for primalitet er Lucas-Lehmer-testen, som er baseret på den særlige form af Mersenne-tallene.

Relaterede sider

Coprime
Liste over primtal
Palindromisk primtal
Primtalsfaktorisering
Wilson prime

Spørgsmål og svar

Spørgsmål: Hvad er et primtal?

A: Et primtal er et naturligt tal, som ikke kan deles af andre naturlige tal undtagen 1 og sig selv.

Spørgsmål: Hvad er det mindste sammensatte tal?

Svar: Det mindste sammensatte tal er 4, fordi 2 x 2 = 4.

Spørgsmål: Hvad er de næste primtal efter 2?

Svar: De næste primtal efter 2 er 3, 5, 7, 11 og 13.

Spørgsmål: Findes der et største primtal?

Svar: Nej, der findes ikke noget største primtal. Mængden af primtal er uendelig.

Spørgsmål: Hvad siger den grundlæggende sætning i aritmetik?

Svar: Den grundlæggende sætning i aritmetik siger, at ethvert positivt heltal kan skrives som et produkt af primtal på en unik måde.

Spørgsmål: Hvad er Goldbachs formodning?

Svar: Goldbachs formodning er et uløst problem i matematikken, der fastslår, at ethvert lige heltal større end to kan udtrykkes som summen af to primtal.

Spørgsmål: Hvem har ført bevis for, at der ikke findes noget største primtal?

Svar: Euklid har ført bevis for, at der ikke findes noget største primtal.