Aritmetikkens fundamentalteorem

Aritmetikkens fundamentalteorem sier at ethvert naturlig tall større enn 1 på en entydig måte kan skrives som et produkt av primtall. For eksempel kan tallet 15 skrives som produktet av to primtall, 3 · 5, tallet 30 som produktet av tre primtall, 2 · 3 · 5, og tallet 16 som produktet av fire primtall, 2 · 2 · 2 · 2. Et slikt produkt kaller vi primfaktorisering. Vi sier altså at primfaktoriseringen av tallet 10 er 2 · 5.

Den enkleste primfaktoriseringen har primtallene selv, for dem trenger vi ikke dele opp videre. Primfaktoriseringen av tallet 7 er rett og slett 7.

Regn ut primfaktoriseringen

Hva aritmetikkens fundamentalteorem sier

Aritmetikkens fundamentalteorem sier oss altså to ting:

• for hvert naturlig tall større enn 1 kan vi finne en primfaktorisering,
• hvert tall har nøyaktig én entydig primfaktorisering.

La oss bevise at det virkelig er slik.

Bevis for eksistens

Først skal vi bevise at det for hvert naturlig tall større enn 1 virkelig finnes minst én primfaktorisering. Til det bruker vi matematisk induksjon. Induksjonsstarten er at det minste naturlige tallet som er større enn 1, altså tallet 2, er et primtall.

Nå skal vi vise at hvis vi allerede har en følge av tall 2, …, n som alle har en primfaktorisering, og vi føyer tallet n + 1 til følgen, så finnes det en primfaktorisering også for dette nye tallet. Først viser vi det på et eksempel.

I begynnelsen er følgen 2, …, n litt spesiell, for den inneholder bare ett tall, nemlig 2. Vi sier at når vi føyer tallet n + 1, altså 3, til denne følgen, så finnes det en primfaktorisering for dette tallet. Siden 3 er et primtall, finnes det selvsagt en primfaktorisering for det — den er 3.

Følgen 2, …, n har nå to ledd: 2, 3. Vi føyer tallet 4 til følgen. Tallet 4 er ikke et primtall, så det må kunne skrives som et produkt av to andre naturlige tall som er større enn 1, men mindre enn 4. Alle slike tall er imidlertid med i følgen vår! Og i følgen er det bare tall som har en primfaktorisering! Altså må også tallet 4 ha en primfaktorisering: 2 · 2.

Tilbake til det generelle beviset: Tallet 2 er et primtall og har derfor en primfaktorisering. Anta nå at hvert tall i følgen 2, …, n kan primfaktoriseres — det er induksjonsantakelsen vår. Da er tallet n + 1 enten et primtall og kan dermed trivielt skrives som et produkt av primtall, eller det er et sammensatt tall. For dette tallet må det da finnes tall a, b slik at

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

og disse naturlige tallene må selvsagt være mindre enn n + 1 og større enn 1:

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

Tallene a, b må derfor være med i følgen 2, …, n. Men for hvert tall i denne følgen finnes det en primfaktorisering (det er induksjonsantakelsen vår), altså kan vi 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}$$

Her er alle p_i og q_j primtall, og p₁ · p₂ · … · p_i og q₁ · q₂ · … · q_j er dermed primfaktoriseringene deres. Siden vi har sagt at n + 1 kan skrives som produktet n + 1 = a · b, gjelder 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å skrives som produktet av primtallene p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, så også det nye tallet n + 1 har en primfaktorisering. Dermed har hvert naturlig tall større enn 1 minst én primfaktorisering.

Bevis for entydighet

La oss nå vise at hvert naturlig tall større enn 1 ikke har flere enn én primfaktorisering. Dette beviser vi med motsigelsesbevis. Vi antar at påstanden ikke er sann, altså at det finnes et naturlig tall n større enn 1 som har to forskjellige primfaktoriseringer:

$$\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}$$

Anta samtidig at av alle tallene som har flere primfaktoriseringer, er n det minste. Det vil si at det ikke finnes noe mindre naturlig tall som har mer enn én primfaktorisering. Siden q₁ er et av primtallene som deler tallet n, må det selvsagt også gjelde at q₁ deler tallet p₁ · p₂ · … · p_i.

Videre må vi bruke Euklids lemma. Det sier at hvis et primtall p deler produktet av to heltall a · b, så deler p også minst ett av tallene a eller b. Et eksempel: primtallet 3 deler tallet 84. Tallet 84 kan vi skrive som produktet 12 · 7. Euklids lemma sier at primtallet 3 deler minst ett av tallene 12 eller 7 — i dette tilfellet deler det tallet 12.

Med dette lemmaet kan vi si at når q₁ deler p₁ · p₂ · … · p_i, så må den også dele minst ett av tallene p₁, p₂, …, p_i. Vi kan anta — uten tap av generalitet — at q₁ deler tallet p₁. Men p₁ er også et primtall. Når kan et primtall dele et annet primtall? For eksempel, hvilket primtall er delelig med primtallet 7? Igjen bare primtallet 7. Det kan ikke dele et annet primtall, for da ville det ikke vært et primtall. Altså må p₁ = q₁.

Det betyr at det i begge primfaktoriseringene finnes et primtall som er det samme: primtallet p₁, henholdsvis q₁. La oss dele begge likningene på 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}$$

Siden p₁ = q₁, får vi det samme tallet på venstre side. La oss kalle det m. Da gjelder

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

På høyre side forkorter vi bare brøkene:

$$\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 sikkert et naturlig tall som er mindre enn tallet n, siden m er blitt til ved at vi delte n på en av primfaktorene. På høyre side av likningene har vi imidlertid i begge tilfeller en primfaktorisering av tallet m. Altså har vi konstruert et annet tall m som er mindre enn n og som også har to forskjellige primfaktoriseringer. Det er i motstrid med antakelsen vår om at n er det minste tallet som har mer enn én entydig primfaktorisering.

Den eneste forklaringen er at det ikke finnes noe «minste tall med mer enn én primfaktorisering». Og at det ikke finnes noe «minste tall med mer enn én primfaktorisering», betyr at det ikke finnes ett eneste tall med flere primfaktoriseringer — hvert heltall større enn 1 har altså nøyaktig én entydig primfaktorisering.