Aritmetikens fundamentalsats

Aritmetikens fundamentalsats säger att varje positivt heltal större än 1 entydigt kan skrivas som en produkt av primtal. Till exempel kan talet 15 skrivas som en produkt av två primtal 3 · 5, talet 30 som en produkt av tre primtal 2 · 3 · 5 och talet 16 som en produkt av fyra primtal 2 · 2 · 2 · 2. En sådan produkt kallar vi primtalsfaktorisering. Vi säger alltså att primtalsfaktoriseringen av talet 10 är 2 · 5.

De enklaste primtalsfaktoriseringarna har primtalen själva, eftersom de inte behöver delas upp vidare. Primtalsfaktoriseringen av talet 7 är helt enkelt 7.

Beräkna primtalsfaktoriseringen

Vad aritmetikens fundamentalsats säger

Aritmetikens fundamentalsats, ibland också kallad den fundamentala satsen i aritmetiken, säger alltså två saker:

• för varje positivt heltal större än 1 kan vi hitta en primtalsfaktorisering,
• varje tal har exakt en primtalsfaktorisering.

Låt oss bevisa att det verkligen är så.

Bevis för existens

Först bevisar vi att det för varje positivt heltal större än 1 verkligen finns minst en primtalsfaktorisering. Det gör vi med matematisk induktion. Basfallet i induktionen blir att det minsta positiva heltalet som är större än 1, alltså talet 2, är ett primtal.

Nu visar vi att om vi redan har en talföljd 2, …, n där alla tal har en primtalsfaktorisering, så har också talet n + 1 en primtalsfaktorisering när vi lägger till det i följden. Först visar vi det på ett exempel.

I början är vår talföljd 2, …, n lite urartad, eftersom den bara innehåller ett tal, talet 2. Vi säger att om vi lägger till talet n + 1, alltså talet 3, så finns det en primtalsfaktorisering för det talet. Eftersom talet 3 är ett primtal finns naturligtvis en primtalsfaktorisering för det – den är talet 3.

Vår talföljd 2, …, n har nu två termer: 2, 3. Vi lägger till talet 4. Talet 4 är inte ett primtal, så det måste gå att skriva som en produkt av två andra positiva heltal som är större än 1 men mindre än 4. Alla sådana tal ingår ju i vår talföljd! Och i den talföljden finns bara tal som har en primtalsfaktorisering! Alltså måste också talet 4 ha en primtalsfaktorisering: 2 · 2.

När vi återvänder till det allmänna beviset kan vi skriva att talet 2 är ett primtal och alltså har en primtalsfaktorisering. Anta nu att varje tal i talföljden 2, …, n kan primtalsfaktoriseras – det är vårt induktionsantagande. Då gäller att talet n + 1 antingen är ett primtal och därmed trivialt kan skrivas som en produkt av primtal, eller ett sammansatt tal. För det talet måste det alltså finnas tal a, b sådana att

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

Samtidigt måste det gälla att dessa positiva heltal naturligtvis är mindre än n + 1 och större än 1:

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

Talen a, b måste alltså ingå i talföljden 2, …, n. Men för varje tal i den följden finns en primtalsfaktorisering (det är vårt induktionsantagande), dvs. vi kan skriva

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

Där alla p_i och q_j är primtal, och p₁ · p₂ · … · p_i och q₁ · q₂ · … · q_j är alltså deras primtalsfaktoriseringar. Men eftersom vi sade att n + 1 kan skrivas som produkten n + 1 = a · b gäller samtidigt

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

Talet n + 1 kan alltså skrivas som en produkt av primtalen p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, så också det nytillagda talet n + 1 har en primtalsfaktorisering. Av det följer att varje positivt heltal större än 1 har minst en primtalsfaktorisering.

Bevis för entydighet

Låt oss nu visa att det för varje positivt heltal större än 1 inte finns fler än en primtalsfaktorisering. Satsen bevisar vi med ett motsägelsebevis. Vi antar att satsen inte är sann, och alltså antar vi att det finns ett positivt heltal n större än 1 som har två olika primtalsfaktoriseringar:

$$\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 samtidigt att n är det minsta av alla tal som har flera primtalsfaktoriseringar. Det betyder att det inte finns något mindre positivt heltal som har fler än en primtalsfaktorisering. Eftersom q₁ är ett av primtalen som delar talet n måste naturligtvis också q₁ dela talet p₁ · p₂ · … · p_i.

Vidare måste vi använda Euklides lemma. Det säger att om ett primtal p delar produkten av två heltal a · b, så delar p också minst ett av talen a eller b. Som exempel: primtalet 3 delar talet 84. Talet 84 kan vi skriva som produkten 12 · 7. Euklides lemma säger att primtalet 3 delar minst ett av talen 12 eller 7 – i det här fallet delar det talet 12.

Med hjälp av lemmat kan vi säga att när q₁ delar p₁ · p₂ · … · p_i, så måste det också dela minst ett av talen p₁, p₂, …, p_i. Vi kan utan inskränkning anta att q₁ delar talet p₁. Men p₁ är också ett primtal. När kan ett primtal dela ett annat primtal? Till exempel, vilket primtal är delbart med primtalet 7? Återigen bara primtalet 7. Det kan inte dela ett annat primtal, för då vore det inte ett primtal. Det måste alltså gälla att p₁ = q₁.

Det betyder att det i båda primtalsfaktoriseringarna finns ett primtal som är detsamma: primtalet p₁ respektive q₁. Låt oss dela båda likheterna med p₁ respektive 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}$$

Eftersom p₁ = q₁ får vi samma tal i vänsterledet, låt oss kalla det m. Det gäller alltså att

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

I högerledet förkortar vi bara bråken:

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

Talet m är med säkerhet ett positivt heltal som är mindre än talet n, eftersom m bildades genom att vi delade n med en av dess primfaktorer. Men i högerleden i båda likheterna har vi en primtalsfaktorisering av talet m. Vi har alltså lyckats konstruera ett annat tal m som är mindre än talet n och som också har två olika primtalsfaktoriseringar. Det strider dock mot vårt antagande att n är det minsta talet som har fler än en primtalsfaktorisering.

Den enda förklaringen är alltså att det inte finns något ”minsta tal med fler än en primtalsfaktorisering”. Och att det inte finns något ”minsta tal med fler än en primtalsfaktorisering” betyder att det inte finns ett enda tal med flera primtalsfaktoriseringar – varje heltal större än 1 har alltså exakt en primtalsfaktorisering.