Aritmetikkens fundamentalsætning

Aritmetikkens fundamentalsætning siger, at ethvert naturligt tal større end 1 på præcis én måde kan opløses i et produkt af primtal. Tallet 15 kan for eksempel opløses i et produkt af to primtal 3 · 5, tallet 30 i et produkt af tre primtal 2 · 3 · 5, og tallet 16 i et produkt af fire primtal 2 · 2 · 2 · 2. Et sådant produkt kalder vi primfaktoropløsningen. Vi siger altså, at primfaktoropløsningen af tallet 10 er 2 · 5.

Den enkleste primfaktoropløsning har primtallene selv, for dem behøver vi ikke opløse videre. Primfaktoropløsningen af tallet 7 er simpelthen 7.

Beregn primfaktoropløsningen selv

Hvad aritmetikkens fundamentalsætning siger

Aritmetikkens fundamentalsætning siger altså to ting:

• for ethvert naturligt tal større end 1 kan vi finde en primfaktoropløsning,
• ethvert tal har præcis én entydig primfaktoropløsning.

Lad os bevise, at det virkelig forholder sig sådan.

Bevis for eksistens

Først beviser vi, at der for ethvert naturligt tal større end 1 virkelig findes mindst én primfaktoropløsning. Til det bruger vi matematisk induktion. Det første trin i induktionen er, at det mindste naturlige tal, der er større end 1, altså tallet 2, er et primtal.

Nu viser vi, at hvis vi allerede har en talfølge 2, …, n, hvor alle tal har en primfaktoropløsning, og vi føjer tallet n + 1 til denne talfølge, så findes der også en primfaktoropløsning for det nye tal. Først viser vi det på et eksempel.

I begyndelsen er vores talfølge 2, …, n lidt udartet, for den indeholder kun ét tal, nemlig tallet 2. Vi siger, at når vi føjer tallet n + 1, altså tallet 3, til denne talfølge, så vil der findes en primfaktoropløsning for dette tal. Da tallet 3 er et primtal, findes der naturligvis en primfaktoropløsning for det — det er tallet 3.

Vores talfølge 2, …, n har nu to led: 2, 3. Vi føjer tallet 4 til talfølgen. Tallet 4 er ikke et primtal, så det må kunne opløses i et produkt af to andre naturlige tal, som er større end 1, men mindre end 4. Alle sådanne tal er imidlertid en del af vores talfølge! Og i denne talfølge er der kun tal, som har en primfaktoropløsning! Så også tallet 4 må have en primfaktoropløsning: 2 · 2.

Når vi vender tilbage til det generelle bevis, kan vi skrive, at tallet 2 er et primtal og derfor har en primfaktoropløsning. Antag nu, at ethvert tal i talfølgen 2, …, n kan opløses i primfaktorer — det er vores induktionsantagelse. Så gælder det, at tallet n + 1 enten er et primtal og dermed trivielt kan opløses i primfaktorer, eller også er det et sammensat tal. For dette tal må der så findes tal a, b, således at

$$n+1=a\cdot b$$

Samtidig må det gælde, at disse naturlige tal naturligvis er mindre end n + 1 og større end 1:

$$\begin{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

Tallene a, b må derfor være en del af talfølgen 2, …, n. Men for ethvert tal i denne talfølge findes der en primfaktoropløsning (det er vores induktionsantagelse), dvs. vi kan skrive

$$\begin{array}{rcl}a& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ b& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

hvor alle p_i og q_j er primtal, og p₁ · p₂ · … · p_i og q₁ · q₂ · … · q_j er dermed deres primfaktoropløsninger. Da vi har sagt, at n + 1 kan opløses i produktet n + 1 = a · b, gælder samtidig

$$\begin{array}{rcl}n+1& =& a\cdot b\\ & =& p_1\cdot p_2\cdot \dots \cdot p_i\cdot q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Tallet n + 1 kan altså opløses i produktet af primtallene p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, så også det nyligt tilføjede tal n + 1 har en primfaktoropløsning. Heraf følger, at ethvert naturligt tal større end 1 har mindst én primfaktoropløsning.

Bevis for entydighed

Lad os nu vise, at der for ethvert naturligt tal større end 1 ikke findes flere primfaktoropløsninger. Denne sætning beviser vi ved hjælp af et modstridsbevis. Vi antager, at sætningen ikke er sand, og at der altså findes et naturligt tal n større end 1, som har to forskellige primfaktoropløsninger:

$$\begin{array}{rcl}n& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ n& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Vi antager samtidig, at n er det mindste af alle de tal, der har flere primfaktoropløsninger. Dvs. at der ikke findes noget mindre naturligt tal, som har mere end én primfaktoropløsning. Da q₁ er et af de primtal, der går op i tallet n, må det naturligvis også gælde, at q₁ går op i tallet p₁ · p₂ · … · p_i.

Videre skal vi bruge Euklids lemma. Det siger, at hvis et primtal p går op i et produkt af to hele tal a · b, så går p også op i mindst et af tallene a eller b. Et eksempel: primtallet 3 går op i tallet 84. Tallet 84 kan vi opløse i produktet 12 · 7. Euklids lemma siger, at primtallet 3 går op i mindst et af tallene 12 eller 7 — i dette tilfælde går det op i tallet 12.

Ved hjælp af dette lemma kan vi sige, at når q₁ går op i p₁ · p₂ · … · p_i, så må det også gå op i mindst et af tallene p₁, p₂, …, p_i. Vi kan antage — uden tab af generalitet — at q₁ går op i tallet p₁. Men p₁ er også et primtal. Hvornår kan et primtal gå op i et andet primtal? Hvilket primtal er for eksempel deleligt med primtallet 7? Igen kun primtallet 7. Det kan ikke gå op i et andet primtal, for så ville det ikke være et primtal. Der må altså gælde, at p₁ = q₁.

Det betyder, at der i begge primfaktoropløsninger findes et primtal, som er det samme: primtallet p₁, henholdsvis q₁. Lad os dividere begge ligninger med p₁, henholdsvis q₁:

$$\begin{array}{rcl}\frac{n}{p_1}& =& \frac{p_1\cdot p_2\cdot \dots \cdot p_i}{p_1}\\ \frac{n}{q_1}& =& \frac{q_1\cdot q_2\cdot \dots \cdot q_j}{q_1}\end{array}$$

Da p₁ = q₁, får vi det samme tal på venstre side. Lad os kalde det for eksempel m. Der gælder altså, at

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

På højre side forkorter vi blot brøkerne:

$$\begin{array}{rcl}m& =& p_2\cdot p_3\cdot \dots \cdot p_i\\ m& =& q_2\cdot q_3\cdot \dots \cdot q_j\end{array}$$

Tallet m er helt sikkert et naturligt tal, som er mindre end tallet n, for m er opstået ved, at vi har divideret n med en af dets primfaktorer. På højre side af ligningerne har vi imidlertid i begge tilfælde en primfaktoropløsning af tallet m. Vi har altså kunnet konstruere et andet tal m, som er mindre end tallet n, og som også har to forskellige primfaktoropløsninger. Det er dog i modstrid med vores antagelse om, at n er det mindste tal, der har mere end én entydig primfaktoropløsning.

Den eneste forklaring er derfor, at der ikke findes noget »mindste tal med mere end én primfaktoropløsning«. Og at der ikke findes noget »mindste tal med mere end én primfaktoropløsning«, betyder, at der slet ikke findes noget tal med flere primfaktoropløsninger — ethvert helt tal større end en har altså præcis én entydig primfaktoropløsning.