Et naturligt tal, der kun kan deles med tallet 1 og tallet selv, kaldes for et primtal.
Det mindste primtal er tallet 2. Tallet 1 er ikke et primtal.
De naturlige tal er mængden \(\{1, 2, 3, 4, …\}\).
Eksempler
Tallet 2 er et primtal, da det kun er deleligt med tallet 1 og tallet 2.
Tallet 3 er et primtal, da det kun er deleligt med tallet 1 og tallet 3.
Tallet 4 er ikke et primtal; det kan nemlig deles med tallene 1, 2 og 4.
Tallet 5 er et primtal, da det kun er deleligt med tallet 1 og tallet 5.
Tallet 6 er ikke et primtal; det kan nemlig deles med tallene 1, 2, 3 og 6.
Tallet 7 er et primtal, da det kun er deleligt med tallet 1 og tallet 7.
Tallet 8 er ikke et primtal; det kan nemlig deles med tallene 1, 2, 4 og 8.
Eksempel fra den virkelige verden
Antag at vi skal sætte nogle ens brædder i forlængelse af hinanden, således at den samlede længde bliver 17 meter.
I byggemarkeder har de brædder med længderne 1m, 2m, 3 m, 4 m, …, 17 m.
Hvordan kan vi sætte ens bræddert i forlængelse af hianden, således at den samlede længde bliver 17 m?
Der er faktisk kun to muligheder; enten skal vi tage 17 brædder med en længde på 1 m, eller også skal vi tage ét langt bræt med en længde på 17 m.
Forklaringen er, at 17 er et primtal, så ingen af tallene 2, 3, 4, …, 16 går op i tallet 17.
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, 113, 127, 131, 137, 149, 151, …
Er et tal et primtal?
Det er let at afgøre om et lille tal er et primtal; det er bare at prøve efter.
Skal vi f.eks. undersøge om 251 er et primtal, så kan vi bare dividere 251 med 2, så med 3, så med 4, så med 5 o.s.v. for at se om nogle af disse tal går op i 251.
Det er klart at lige tal ikke kan gå op i 251, og man kan også let udelukke en del andre tal på vejen som man ikke behøver at dividere op i 251. Hvis f.eks. 3 ikke går op i 251, så går 9 heller ikke op i 251. Hvis 9 nemlig går op i 251, så vil 3 gå to gange op i 251.
Desuden behøver man ikke dividere med alle tal, helt op til 251, for at undersøge om 251 er et primtal. Det er nok at prøve med tallene op til 15.
Det skyldes, at \(\sqrt{251}=15.84\). Dermed er \(251 = 15.84 \cdot 15.84\). Hvis 251 kan skrives som \( a \cdot b\), hvor a og b er heltal, med f.eks. a større end 15,84, så må b være mindre end 15,84.
Har vi derfor prøvet at dividere 251 med alle hele tal op til 15, uden at andre end tallet 1 går op, så kan ingen andre tal gå op i 251. Hvis et tal over 15 gik op i 251, så ville der jo også være et tal under 15 som går op i 251.
Hvis man vil undersøge om meget store tal er primtal, så kan man ikke bare afprøve alle muligheder. Det kan jo ikke nytte noget at det tager 1 mio år, på den hurtigste computer, at undersøge om et tal er et primtal. Der er flere andre, og smarte metoder, som på kort tid kan afgøre om et tal er et primtal.
RSA-kryptering bygger på, at tager man to meget store primtal \(p\) og \(q\), og ganger dem med hinanden; \(n = p \cdot q\), så kan man ikke på nogen let måde bestemme \(p\) eller \(q\) alene ud fra tallet \(n\). Det er altså let at gå den ene vej; det med at gange de to primtal, men det er meget vanskeligt at gå den anden vej; det med, ud fra kendskab til n, at finde p eller q.
Bemærk at det er ret let at afgøre om tallet n er et primtal; det er det naturligvis ikke da både p og q går op i det. Men det hjælper ikke på opgaven med at bestemme p eller q.
Aritmetikkens fundamentalsætning
Primtal spille en stor rolle i talteorien. En vigtig sætning er aritmetikkens fundamentalsætning. Den fortæller, list løst, at alle hele tal er bygget op af primtal.
Det vises lettest med nogle eksempler:
\(2 = 2\) \(3 = 3\) \(4 = 2 \cdot 2 = 2^2\) \(5 = 5\) \(6 = 2 \cdot 3\) \(7 = 7\) \(8 = 2 \cdot 2 \cdot 2 = 2^3\) \(9 = 3 \cdot 3 = 3^2\) \(10 = 2 \cdot 5\) \(11 = 11\) \(12 = 2 \cdot 2 \cdot 3 = 2^2 \cdot 2\) \(13 = 13\) \(14 = 2 \cdot 7\) \(15 = 3 \cdot 5\)
På venstre side har jeg tallene 2, 3, 4, … og på højre side står der, hvordan disse tal er opbygget af primtal.
Aritmetikkens fundamentalsætning siger, at alle tal kan skrives som et produkt af primtal, dvs. som primtal ganget med hinanden. Sætningen siger også at det kun kan gøres på én måde. Her er det underforstået, at det at bytte om på to tal, ikke tæller som anden måde; \(6 = 2 \cdot 3\) og \(6 = 3 \cdot 2\) er altså ikke to forskellige måder.
Når man har skrevet et helt tal som et produkt af primtal, så siger man, at man har lavet en primfaktoropløsning af tallet.
Vi kan vælge lidt større eksempler:
\(100 = 2^2 \cdot 5^2\) \(12345 = 3 \cdot 5 \cdot 823\) \(987654321 = 3^2 \cdot 17^2 \cdot 379721\) \(998877665544332211 = 3^2 \cdot 11 \cdot 229 \cdot 547 \cdot 883 \cdot 9277 \cdot 9833\)
Alle de tal der står på højre side af lighedstegnet er primtal. De resultater har jeg naturligvis ikke regnet ud ved håndkraft. Jeg har brugt Maple, og funktionen ifactor( ).