Bizonyítás
Legyen f egy tetszőleges euklidészi függvény R-hez. Ilyen ugye létezik, mivel R euklidészi gyűrű. A bizonyítás konstruktív lesz, azaz f felhasználásával definiálni fogunk egy olyan g függvényt, amely maga is euklidészi függvény, de ezen felül teljesíti a tételben szereplő monotonitási tulajdonságot is.
Tegyük fel, hogy valamilyen tetszőleges k elemre szeretnénk kiszámítani a g(k) függvényértéket. Ehhez először képezzük a k elem összes nemnulla többszörösének az f függvény szerinti értékét, azaz minden R-beli x\neq 0 elemre kiszámítjuk az f(kx) természetes számokat. Ezután válasszuk g(k) értékének ezek közül a legkisebbet, amely ugye a 17.15. Tétel miatt biztosan létezik. Más szavakkal a g(k) függvényérték legyen az eredeti f függvénynek a k elem nemnulla többszörösein felvett minimuma.
A g függvény iménti definíciója alapján tehát a tételben szereplő a és b\neq 0_R elemek esetén létezik olyan c\neq 0_R elem, amelyre g(ab)=f(abc) teljesül. Nevezetesen épp az a c elem, amelyre az f(abc) felveszi a minimumát.
Mivel ugyanakkor az abc szorzat az ab elemen kívül az a elemnek is egy nemnulla többszöröse, ezért ismét a g függvény fenti definíciója miatt:
De mivel azt mondtuk, hogy g(ab)=f(abc), ezért valóban fennáll a tételben szereplő egyenlőtlenség:
Már csak annyit kell igazolni, hogy maga g is euklidészi függvény R-hez. Legyen b\neq 0_R egy tetszőleges nemnulla R-beli elem, valamint válasszuk ki b-nek egy olyan nemnulla többszörösét, amelyre az eredeti f euklidészi függvény épp a minimumát veszi fel. Ez ugye biztosan létezik, mint azt már láttuk fentebb. Azaz válasszunk ki egy olyan c\neq 0_R elemet, amelyre
Minthogy b\neq 0_R és c\neq 0_R ezért a nullosztómentesség miatt bc\neq 0_R. Azaz tetszőleges a elem maradékosan elosztható a bc elemmel az eredeti f euklidészi függvény szerint. Ez azt jelenti, hogy létezik olyan k hányados és r maradék, amelyekre teljesül az alábbi egyenlet:
Továbbá az alábbiak közül legalább az egyik teljesül:
Az általánosság megsértése nélkül feltehetjük, hogy r\neq 0_R, és így az f-re vonatkozó egyenlőtlenség áll fenn, máskülönben a további lépésekben amúgysem nyernénk semmilyen további információt g-ről.
Egyrészt a g függvény definíciója miatt g(r)\leq f(r), hiszen r a 16.2. Tétel 1. pontja alapján önmagának is többszöröse. Másrészt viszont a c elemet épp úgy választottuk ki, hogy f(bc)=g(b) teljesüljön. Létezik tehát olyan hányados – nevezetesen kc – és maradék – nevezetesen r –, amelyre teljesülnek az alábbiak:
Azaz tetszőleges a elem tetszőleges b\neq 0_R elemmel maradékosan elosztható a g függvény szerint is, így g valóban egy euklidészi függvény.
∎