Aritmetiikan peruslause

Alkutekijähajotelman olemassaolo voidaan todistaa melko suoraviivaisesti induktiolla. Todetaan aluksi, että luvulla 2 on olemassa alkutekijähajotelma 2. Olkoon sitten ${\displaystyle n\geq 3}$ ja oletetaan, että kaikille kokonaisluvuille ${\displaystyle 2,\ldots ,n-1}$ on olemassa alkutekijähajotelma. Jos ${\displaystyle n}$ on alkuluku, niin se on oma alkutekijähajotelmansa. Jos taas ${\displaystyle n}$ on yhdistetty luku, niin se voidaan hajottaa tuloksi ${\displaystyle n=ab}$, missä ${\displaystyle a}$ ja ${\displaystyle b}$ ovat kokonaislukuja ja ${\displaystyle 1<a,\;b<n}$. Induktio-oletuksen nojalla ${\displaystyle a}$ ja ${\displaystyle b}$ voidaan kumpikin esittää alkulukujen tuloina; kertomalla nämä tulot keskenään saadaan ${\displaystyle n}$ alkulukujen tulona.[3]

Hajotelman yksikäsitteisyys voidaan todistaa eri tavoin, riippuen siitä mitä tuloksia oletetaan tunnetuiksi.

Eukleideen lemma sanoo, että jos jokin alkuluku ${\displaystyle p}$ jakaa kahden luvun tulon ${\displaystyle ab}$, niin se jakaa ainakin toisen sen tekijöistä. Induktiolla tästä seuraa, että jos alkuluku ${\displaystyle p}$ jakaa jonkin tulon ${\displaystyle abc\ldots }$, niin ${\displaystyle p}$ jakaa jonkin tekijöistä ${\displaystyle a,b,c,\ldots }$

Aritmetiikan peruslause seuraa Eukleideen lemmasta melko yksinkertaisesti. Olkoon luvulla ${\displaystyle n}$ kaksi alkutekijähajotelmaa

${\displaystyle n=pqr\ldots =p'q'r'\ldots }$

Koska ${\displaystyle p}$ jakaa tulon ${\displaystyle p'q'r'\ldots }$, niin ${\displaystyle p}$ jakaa jonkin tekijöistä ${\displaystyle p',q',r',\ldots }$, ja koska ne ovat alkulukuja, niin ${\displaystyle p}$ on eräs niistä. Molemmat alkutekijähajotelmat voidaan nyt supistaa ${\displaystyle p}$:llä. Jatkamalla samaan tapaan nähdään, että alkutekijähajotelmat ovatkin samat.[5]

Vaihtoehtoisesti aritmetiikan peruslause voidaan todistaa myös suoraan jaollisuuden perusominaisuuksista, käyttämättä Eukleideen lemmaa, Eukleideen algoritmia tai vastaavia aputuloksia. Ernst Zermelo kehitti tällaisen suoraviivaisen todistuksen vuonna 1912.[6]