youproof.orgDeep Math. Human Access.

Bizonyítás

Legyen aa és bb az RR két tetszőleges eleme, és jelöljük 0R0_R-rel a nullelemet. Az általánosság megsértése nélkül feltételezhetjük, hogy a≠0Ra\neq 0_R és b≠0Rb\neq 0_R, minden más esetben ugyanis a 17.6. Tételből azonnal megkapjuk a keresett kitüntetett közös osztót.

Mivel RR euklidészi gyűrű, ezért a 17.17. Definíció 1. pontja szerint aa és bb között elvégezhető a maradékos osztás egy valamilyen ff euklidészi függvény szerint. Azaz RR-ben létezik k1k_1 hányados és r1r_1 maradék RR-ben úgy, hogy teljesüljön az alábbi egyenlet:

a=k1b+r1a=k_1b+r_1

Ekkor a 17.17. Definíció 2. pontja szerint az alábbiak közül legalább az egyik teljesül:

r1=0Rf(r1)<f(b)\begin{aligned} r_1&=0_R \\ f(r_1)&<f(b) \end{aligned}

Ha r1=0Rr_1=0_R, akkor a 17.13. Tétel, valamint a 17.6. Tétel 4. pontja alapján bb lesz a kitüntetett közös osztó, hiszen

(a,b)∼(b,r1⏟=a−k1b)∼(b,0R⏟=r1)∼b(a,b)\sim (b,\underbrace{r_1}_{=a-k_1b})\sim (b,\underbrace{0_R}_{=r_1})\sim b

Ha viszont r1≠0Rr_1\neq 0_R, akkor egyrészt a 17.17. Definíció 2. pontja értelmében szükségképpen teljesül az alábbi szigorú egyenlőtlenség:

f(b)>f(r1)f(b)>f(r_1)

Másrészt pedig a 17.17. Definíció 1. pontja alapján ezúttal bb és r1r_1 között ismét elvégezhető az ff szerinti maradékos osztás.

Ezt az eljárást mindaddig folytatjuk, amíg meg nem kapjuk a nullelemet maradékként valamelyik lépésben. Ekkor – ismételten a 17.13. Tétel, és a 17.6. 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)>f(r1)>f(r2)>f(r3)>…f(b)\gt f(r_1)\gt f(r_2)\gt f(r_3)\gt \ldots

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

∎