Aritmetiikan peruslause

Aritmetiikan peruslause kertoo, että jokainen ykköstä suurempi positiivinen kokonaisluku voidaan jakaa yksikäsitteisesti alkulukujen tuloksi. Esimerkiksi luku 15 voidaan kirjoittaa kahden alkuluvun tulona 3 · 5, luku 30 kolmen alkuluvun tulona 2 · 3 · 5 ja vaikkapa luku 16 neljän alkuluvun tulona 2 · 2 · 2 · 2. Tällaista tuloa kutsutaan alkutekijähajotelmaksi. Sanomme siis, että luvun 10 alkutekijähajotelma on 2 · 5.

Yksinkertaisin alkutekijähajotelma on alkuluvuilla itsellään, koska niitä ei tarvitse jakaa enempää. Luvun 7 alkutekijähajotelma on yksinkertaisesti 7.

Laske alkutekijähajotelma

Mitä aritmetiikan peruslause kertoo

Aritmetiikan peruslause, jota kutsutaan joskus myös aritmetiikan fundamentaalilauseeksi, kertoo meille kaksi asiaa:

• jokaiselle ykköstä suuremmalle positiiviselle kokonaisluvulle pystymme löytämään alkutekijähajotelman,
• jokaisella luvulla on täsmälleen yksi yksikäsitteinen alkutekijähajotelma.

Todistetaan, että asia todella on näin.

Olemassaolon todistus

Todistetaan ensin, että jokaiselle ykköstä suuremmalle positiiviselle kokonaisluvulle todella on olemassa ainakin yksi alkutekijähajotelma. Käytämme todistuksessa matemaattista induktiota. Induktion ensimmäinen askel on huomata, että pienin ykköstä suurempi positiivinen kokonaisluku eli luku 2 on alkuluku.

Näytetään nyt, että jos meillä on lukujen 2, …, n jono, jonka jokaiselle luvulle voidaan löytää alkutekijähajotelma, niin kun lisäämme jonoon luvun n + 1, myös tälle uudelle luvulle on olemassa alkutekijähajotelma. Katsotaan sitä ensin esimerkin avulla.

Aluksi jonomme 2, …, n on hieman vajaa, koska siinä on vain yksi luku, luku 2. Väitämme, että kun tähän jonoon lisätään luku n + 1 eli luku 3, tälle luvulle on olemassa alkutekijähajotelma. Koska luku 3 on alkuluku, sillä on tietysti alkutekijähajotelma – se on luku 3.

Jonossamme 2, …, n on nyt kaksi jäsentä: 2, 3. Lisätään jonoon luku 4. Luku 4 ei ole alkuluku, joten se täytyy voida jakaa kahden sellaisen positiivisen kokonaisluvun tuloksi, jotka ovat suurempia kuin 1 mutta pienempiä kuin 4. Kaikki tällaiset luvut kuuluvat kuitenkin jonoomme! Ja jonossa on vain lukuja, joilla on alkutekijähajotelma! Siis myös luvulla 4 täytyy olla alkutekijähajotelma: 2 · 2.

Palataan yleiseen todistukseen. Luku 2 on alkuluku, joten sillä on alkutekijähajotelma. Oletetaan nyt, että jokainen jonon 2, …, n luku voidaan jakaa alkutekijöihin – tämä on induktio-oletuksemme. Tällöin luku n + 1 on joko alkuluku, jolloin se on triviaalisti jaettu alkulukuihin, tai yhdistetty luku. Silloin on olemassa luvut a, b, joille

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

ja näiden positiivisten kokonaislukujen täytyy tietysti olla pienempiä kuin n + 1 ja suurempia kuin 1:

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

Luvut a, b kuuluvat siis jonoon 2, …, n. Jokaiselle tämän jonon luvulle on kuitenkin olemassa alkutekijähajotelma (tämä on induktio-oletuksemme), eli voimme kirjoittaa

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

Tässä kaikki p_i ja q_j ovat alkulukuja, ja p₁ · p₂ · … · p_i ja q₁ · q₂ · … · q_j ovat siis lukujen alkutekijähajotelmat. Koska totesimme, että n + 1 voidaan kirjoittaa tulona n + 1 = a · b, pätee samalla

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

Luku n + 1 voidaan siis kirjoittaa alkulukujen tulona p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, joten myös uudella luvulla n + 1 on alkutekijähajotelma. Tästä seuraa, että jokaisella ykköstä suuremmalla positiivisella kokonaisluvulla on ainakin yksi alkutekijähajotelma.

Yksikäsitteisyyden todistus

Näytetään seuraavaksi, että jokaisella ykköstä suuremmalla positiivisella kokonaisluvulla ei ole useampaa kuin yksi alkutekijähajotelma. Todistamme väitteen ristiriitatodistuksella. Oletamme, että väite ei pidä paikkaansa, eli että on olemassa ykköstä suurempi positiivinen kokonaisluku n, jolla on kaksi eri alkutekijähajotelmaa:

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

Oletetaan lisäksi, että kaikista luvuista, joilla on useampi alkutekijähajotelma, n on pienin. Toisin sanoen ei ole olemassa pienempää positiivista kokonaislukua, jolla olisi useampi kuin yksi alkutekijähajotelma. Koska q₁ on yksi alkuluvuista, jotka jakavat luvun n, täytyy tietysti päteä myös, että q₁ jakaa luvun p₁ · p₂ · … · p_i.

Seuraavaksi tarvitsemme Eukleideen lemmaa. Sen mukaan jos alkuluku p jakaa kahden kokonaisluvun tulon a · b, niin p jakaa myös ainakin toisen luvuista a tai b. Esimerkki: alkuluku 3 jakaa luvun 84. Luku 84 voidaan jakaa tuloksi 12 · 7. Eukleideen lemman mukaan alkuluku 3 jakaa ainakin toisen luvuista 12 tai 7 – tässä tapauksessa se jakaa luvun 12.

Lemman avulla voimme sanoa, että kun q₁ jakaa tulon p₁ · p₂ · … · p_i, sen täytyy jakaa myös ainakin yksi luvuista p₁, p₂, …, p_i. Voimme olettaa yleisyyttä rajoittamatta, että q₁ jakaa luvun p₁. Mutta p₁ on myös alkuluku. Milloin alkuluku voi jakaa toisen alkuluvun? Esimerkiksi mikä alkuluku on jaollinen alkuluvulla 7? Taas vain alkuluku 7. Alkuluku ei voi jakaa toista alkulukua, koska silloin tuo toinen ei olisi alkuluku. Täytyy siis päteä p₁ = q₁.

Tämä tarkoittaa, että molemmissa alkutekijähajotelmissa on yksi sama alkuluku: alkuluku p₁ eli q₁. Jaetaan kumpikin alkulukuyhtälö luvulla p₁ eli 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}$$

Koska p₁ = q₁, saamme vasemmalle puolelle saman luvun, merkitään sitä vaikkapa m. Siis

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

Oikealla puolella supistamme vain murtoluvut:

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

Luku m on varmasti positiivinen kokonaisluku, joka on pienempi kuin n, koska m syntyi jakamalla n jollakin sen alkutekijöistä. Yhtälöiden oikealla puolella on kuitenkin molemmissa tapauksissa luvun m alkutekijähajotelma. Olemme siis onnistuneet muodostamaan toisen luvun m, joka on pienempi kuin n ja jolla on myös kaksi eri alkutekijähajotelmaa. Tämä on ristiriidassa oletuksemme kanssa, että n on pienin luku, jolla on useampi kuin yksi yksikäsitteinen alkutekijähajotelma.

Ainoa selitys on, että ”pienintä lukua, jolla on useampi kuin yksi alkutekijähajotelma” ei ole olemassa. Ja se, ettei tällaista lukua ole olemassa, tarkoittaa, ettei ole olemassa yhtään lukua, jolla olisi useampi alkutekijähajotelma – jokaisella ykköstä suuremmalla kokonaisluvulla on siis täsmälleen yksi yksikäsitteinen alkutekijähajotelma.