youproof.orgDeep Math. Human Access.

Bizonyítás

Legyen ff egy tetszőleges euklidészi függvény RR-hez. Ilyen ugye létezik, mivel RR euklidészi gyűrű. A bizonyítás konstruktív lesz, azaz ff felhasználásával definiálni fogunk egy olyan gg 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 kk elemre szeretnénk kiszámítani a g(k)g(k) függvényértéket. Ehhez először képezzük a kk elem összes nemnulla többszörösének az ff függvény szerinti értékét, azaz minden RR-beli x≠0x\neq 0 elemre kiszámítjuk az f(kx)f(kx) természetes számokat. Ezután válasszuk g(k)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)g(k) függvényérték legyen az eredeti ff függvénynek a kk elem nemnulla többszörösein felvett minimuma.

A gg függvény iménti definíciója alapján tehát a tételben szereplő aa és b≠0Rb\neq 0_R elemek esetén létezik olyan c≠0Rc\neq 0_R elem, amelyre g(ab)=f(abc)g(ab)=f(abc) teljesül. Nevezetesen épp az a cc elem, amelyre az f(abc)f(abc) felveszi a minimumát.

Mivel ugyanakkor az abcabc szorzat az abab elemen kívül az aa elemnek is egy nemnulla többszöröse, ezért ismét a gg függvény fenti definíciója miatt:

g(a)≤f(abc)g(a)\leq f(abc)

De mivel azt mondtuk, hogy g(ab)=f(abc)g(ab)=f(abc), ezért valóban fennáll a tételben szereplő egyenlőtlenség:

g(a)≤g(ab)⏟=f(abc)g(a)\leq \underbrace{g(ab)}_{=f(abc)}

Már csak annyit kell igazolni, hogy maga gg is euklidészi függvény RR-hez. Legyen b≠0Rb\neq 0_R egy tetszőleges nemnulla RR-beli elem, valamint válasszuk ki bb-nek egy olyan nemnulla többszörösét, amelyre az eredeti ff 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≠0Rc\neq 0_R elemet, amelyre

g(b)=f(bc)g(b)=f(bc)

Minthogy b≠0Rb\neq 0_R és c≠0Rc\neq 0_R ezért a nullosztómentesség miatt bc≠0Rbc\neq 0_R. Azaz tetszőleges aa elem maradékosan elosztható a bcbc elemmel az eredeti ff euklidészi függvény szerint. Ez azt jelenti, hogy létezik olyan kk hányados és rr maradék, amelyekre teljesül az alábbi egyenlet:

a=k⋅(bc)+ra=k\cdot (bc) + r

Továbbá az alábbiak közül legalább az egyik teljesül:

r=0Rf(r)<f(bc)\begin{aligned} r&=0_R \\ f(r)&\lt f(bc) \end{aligned}

Az általánosság megsértése nélkül feltehetjük, hogy r≠0Rr\neq 0_R, és így az ff-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 gg-ről.

Egyrészt a gg függvény definíciója miatt g(r)≤f(r)g(r)\leq f(r), hiszen rr a 16.2. Tétel 1. pontja alapján önmagának is többszöröse. Másrészt viszont a cc elemet épp úgy választottuk ki, hogy f(bc)=g(b)f(bc)=g(b) teljesüljön. Létezik tehát olyan hányados – nevezetesen kckc – és maradék – nevezetesen rr –, amelyre teljesülnek az alábbiak:

a=(kc)⋅b+rg(r)⏟≤f(r)<g(b)⏟=f(bc)\begin{aligned} a&=(kc)\cdot b + r \\ \underbrace{g(r)}_{\leq f(r)}&\lt \underbrace{g(b)}_{=f(bc)} \end{aligned}

Azaz tetszőleges aa elem tetszőleges b≠0Rb\neq 0_R elemmel maradékosan elosztható a gg függvény szerint is, így gg valóban egy euklidészi függvény.

∎