Bizonyítás
Legyen R valamilyen euklidészi gyűrű. A 17.18. Tétel alapján R-ben bármely két elemnek létezik kitüntetett közös osztója. Így a 17.12. Tétel miatt minden felbonthatatlan elem prím. Ebből viszont a 16.18. Tétel szerint következik a számelmélet alaptételének egyértelműségi állítása. Ha tehát valamely elemnek egyáltalán létezik felbontása, akkor az sorrendtől és asszociáltságtól eltekintve egyértelmű.
Így már csak azt kell megmutatni, hogy bármely nemnulla és nem egység elemnek ténylegesen létezik felbontása. Tegyük fel, hogy g egy olyan euklidészi függvény, amely eleget tesz a 17.21. Tételben szereplő monotonitási tulajdonságnak is. Ilyen euklidészi függvény ugyanezen tétel miatt garantáltan létezik. A bizonyításhoz a g norma értékkészletén, azaz a természetes számok \N halmazán fogunk teljes indukciót alkalmazni.
Ennek során minden n természetes számra megmutatjuk, hogy R összes olyan nemnulla és nem egység elemének létezik prímtényezős felbontása, amelynek a g euklidészi függvény szerinti értéke legfeljebb n. A 17.5. ábrán az R elemeinek azon A_0, A_1, A_2, ... részhalmazai láthatók, amelyek az első néhány természetes számhoz tartoznak ebben az értelemben. Az elemeket pontokkal jelöltük, valamint ábrázoltuk a g által hozzájuk rendelt értékeket is.
Először is indukciós feltételként feltesszük, hogy valamilyen n-re már igaz az állítás, azaz bármely n-nél nemnagyobb g-értékű nemnulla és nem egység elemnek létezik prímtényezős felbontása. Ezt az elemhalmazt a fenti ábrán A_n-nel jelöltük. Azt kell megmutatnunk, hogy ekkor az A_{n+1} halmaz elemeire is teljesülni fog az állítás. Tegyük fel, hogy a egy tetszőleges A_{n+1}-beli elem. Feltételezhetjük, hogy nincs benne A_n-ben, hiszen máskülönben az indukciós feltétel miatt róla már amúgyis tudnánk, hogy létezik prímtényezős felbontása. Így tehát:
Ha a felbonthatatlan, akkor az ő prímtényezős felbontása alatt a 16.16. Definíció alapján önmagát, mint "egytényezős szorzatot" értjük, így az nyilván létezik. Feltételezhetjük tehát, hogy a nem felbonthatatlan, azaz felírható a=bc alakban úgy, hogy b és c közül egyik sem egység.
Ekkor azonban a g euklidészi függvényre a 17.22. Tétel miatt fennállnak az alábbi szigorú egyenlőtlenségek, hiszen a nem egységszerese sem b-nek, sem pedig c-nek:
Ez viszont g(a)=n+1 miatt azt jelenti, hogy
Az indukciós feltétel alapján azonban emiatt b-nek és c-nek létezik prímtényezős felbontása, hiszen mindketten benne vannak az A_n halmazban. Így ha az a=bc szorzatba b és c helyére beírjuk e két felbontást, akkor épp a-nak a felbontását kapjuk.
Eddig tehát azt bizonyítottuk, hogy ha valamilyen n-re az A_n halmaz minden elemének létezik felbontása, akkor ez igaz lesz az őt tartalmazó A_{n+1} halmaz elemeire is. Már csak el kell indítani az indukciós "dominósor" ledöntését, azaz meg kell mutatni, hogy n=0-ra valóban teljesül a tétel állítása.
Az n=0 esethez az A_0 halmaz tartozik, amely tehát azokat a nemnulla és nem egység elemeket tartalmazza, amelyeknek a g-értéke legfeljebb 0. Tegyük fel indirekt, hogy ezek között mégis létezik egy olyan x elem, amelynek nem létezik prímtényezős felbontása. Minthogy az A_0 halmaz definíciója miatt g(x)\leq 0, ugyanakkor g(x) csak nemnegatív szám lehet, mivel a g függvény \N-be képez, ezért ez azt jelenti, hogy valójában
Jelöljük 1_R-rel az R egységelemét, és végezzük el a g euklidészi függvény szerinti maradékos osztást 1_R és x között. Ez megtehető, hiszen R euklidészi gyűrű. Létezik tehát olyan k hányados és r maradék, hogy teljesül az alábbi egyenlet:
Továbbá az alábbiak közül legalább az egyik teljesül:
Az egyenlőtlenség nem teljesülhet, hiszen – mint már említettük – a g függvény \N-be képez, és emiatt semmilyen g-érték nem lehet 0-nál kisebb. Ezért tehát szükségképpen r=0_R, azaz
Tehát valójában azt kaptuk, hogy x osztója az egységelemnek, azaz a 16.5. Tétel alapján egység. Ez viszont ellentmondás, mivel azt mondtuk, hogy az A_0 halmazban csak nemnulla és nem egység elemek vannak.
Azt kaptuk tehát, hogy az A_0 halmazra igaz lesz a tétel állítása. Ekkor azonban a már bizonyított indukciós lépés miatt igaz lesz A_1-re is, majd emiatt A_2-re is, és így tovább, egészen a végtelenségig. Minthogy a g euklidészi függvény összes lehetséges értékét lefedtük, ezért biztosan nem hagytunk ki egyetlen nemnulla és nem egység elemet sem a buliból. Mindegyikre igaz tehát a prímtényezős felbontás létezése, és így a számelmélet alaptétele.
∎