Hvad er primtal? Definition, egenskaber og berømte problemer
Lær hvad primtal er, deres egenskaber, historiske beviser og berømte problemer som Goldbach og Mersenne — klar guide til teori og anvendelser.
Et primtal er et helt, positivt tal større end 1, som kun har to positive divisorer: 1 og sig selv. Hvis et naturligt tal kan skrives som produktet af to mindre positive heltal (begge større end 1), kaldes det et sammensat tal. Tallet 1 er hverken et primtal eller et sammensat tal. Det mindste primtal er 2 (det eneste lige primtal); derpå følger 3, 5, 7, 11, 13 osv. Primtal er altså de tal større end 1, som ikke er lig med 
for nogle heltal m,n > 1. Der findes ikke noget største primtal. Mængden af primtal skrives undertiden som 
.
Den grundlæggende sætning i aritmetik siger, at ethvert positivt heltal større end 1 kan skrives som et produkt af primtal på en måde, som er unik op til rækkefølgen af faktorerne. Denne entydige primfaktorisering er grundlaget for meget af talteorien og er også praktisk vigtig i f.eks. kryptografi.
Egenskaber og eksempler
- 2 er det eneste lige primtal; alle andre primtal er ulige.
- To primtal, der adskiller sig med 2 (f.eks. 11 og 13), kaldes et tvillingeprimpar. Om der findes uendeligt mange tvillingeprimtal er en åben formodning.
- Der findes arbitrært store mellemrum mellem to på hinanden følgende primtal (prime gaps), men fordelingen af primtal følger bestemte asymptotiske regler.
- Dirichlets sætning siger, at i enhver aritmetisk progression a, a+d, a+2d, ... med a og d indbyrdes primiske findes der uendeligt mange primtal.
Fordeling og store spørgsmål
Det er vanskeligt at beskrive præcist, hvordan primtallene fordeler sig. Primtalteoremet giver en asymptotisk beskrivelse: antallet af primtal ≤ x er cirka x / log(x) når x bliver stort. På trods af dette er mange konkrete spørgsmål åbne, f.eks. Goldbachs formodning (at hvert lige heltal > 2 er sum af to primtal) og tvillingeprimformodningen.
Historie og store resultater
Den græske matematiker Euklid gav et klassisk bevis for, at der findes uendeligt mange primtal. Siden da har talteoriens udvikling bragt mange dybe resultater om primtal, men også nye åbne problemer. Mange af de største kendte primtal er Mersenne-primtal (tal på formen 2^p − 1, hvor p også er et primtal), og mange af dem er fundet gennem den globale indsats i Great Internet Mersenne Prime Search (GIMPS).
Hvordan finder og tester man primtal?
For små tal bruges simple metoder som trialdivision (prøv at dividere med alle primtal op til kvadratroden af tallet) eller Erathostenes' sive for at liste primtal op til en grænse. For meget store tal anvendes hurtige algoritmer og probabilistiske tests:
- Sieve of Eratosthenes og optimerede varianter (f.eks. segmenteret sive) til fremstilling af lister af primtal.
- Fermats lille sætning og Miller–Rabin: probabilistiske tests, som med høj sandsynlighed afgør, om et tal er sammensat eller sandsynligvis primt.
- AKS-primalitetstest: et deterministisk polynomieltidsalgoritme, som kan bevise primalitet uden tilfældighed.
- Primalitetscertifikater: beviser (f.eks. Pratt-certifikater eller elliptiske kurver-baserede beviser) som kan bekræfte, at et givet stort tal er primt.
Anvendelser
Primtal spiller en central rolle i moderne kryptografi (f.eks. RSA), hvor sværigheden ved at faktorisere et stort sammensat tal i dets primfaktorer udnyttes til sikker nøgleudveksling og kryptering. Primtal bruges også i algoritmer, hashing, pseudo-tilfældig talgenerering og i forskellige teoretiske problemer i matematik og datalogi.
Videre læsning
Hvis du vil dykke dybere, kan du læse om konkrete primalitetstests, faktoriseringsteknikker (f.eks. kvadratsøgev og kvadratiske siges), Mersenne-primtal og nyere fremskridt i forståelsen af primtalsfordelingen. Mange af disse emner fører fra elementær aritmetik til avanceret analytisk talteori og computationel matematik.
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.
Søge