A bizonyításhoz az euklidészi algoritmus általánosított változatát fogjuk felhasználni. Legyen a és b az R integritástartomány két tetszőleges eleme, és jelöljük 0_R-rel a nullelemet, 0-val pedig a „nulla” természetes számot. Ha a vagy b közül bármelyik 0_R, akkor létezik kitüntetett közös osztójuk. Ha mindkettő 0_R, akkor a 17.5. Tétel 1. pontja miatt. Ha pedig csak az egyikük, akkor viszont – mivel minden euklidészi gyűrű a 17.16. Definíció alapján egységelemes – ugyanezen tétel 4. pontja miatt.

Feltételezhetjük tehát, hogy a\neq 0_R és b\neq 0_R. Mivel R euklidészi gyűrű, ezért értelmezhető rajta valamilyen f euklidészi norma. Ekkor a és b között elvégezhető a maradékos osztás az f norma szerint. Azaz létezik k_1 hányados és r_1 maradék R-ben úgy, hogy egyrészt fennálljon az f(r_1)<f(b) szigorú egyenlőtlenség, másrészt teljesüljön az alábbi egyenlet:

a=k_1b+r_1

Ha f(r_1)=0, akkor az euklidészi norma 17.16. Definíciója miatt r_1=0_R, és így a 17.13. Tétel, valamint a 17.5. Tétel 4. pontja alapján b lesz a kitüntetett közös osztó, hiszen (a,b)=(b,r_1)=(b,0_R)=b. Ha f(r_1)\neq 0, akkor r_1\neq 0_R, és így b és r_1 között ismét el tudjuk végezni az f norma szerinti maradékos osztást.

Ezt az eljárást mindaddig folytatjuk, amíg meg nem kapjuk a nullelemet maradékként valamelyik lépésben. Ekkor – szintén a 17.13. Tétel, valamint a 17.5. Tétel 4. pontja miatt – az utolsó olyan maradék lesz a kitüntetett közös osztó, amely nem a nullelem.

Az eljárás garantáltan véget fog érni véges számú lépés után, máskülönben a maradékos osztások során előállna az alábbi, természetes számokból álló végtelen sorozat:

f(b)\gt f(r_1)\gt f(r_2)\gt f(r_3)\gt \ldots

Ez a 17.15. Tétel miatt \N-nek egy olyan részhalmaza lenne, amelynek nincs minimuma. Ez viszont a 17.14. Tétel miatt lehetetlen, így az euklidészi algoritmus garantáltan leáll véges számú lépés után, és előállítja az a és b kitüntetett közös osztóját, amely az utolsó nemnulla maradék lesz.