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, 1R1_R-rel pedig az egységelemet – amely ugye létezik, hiszen a 17.17. Definíció alapján minden euklidészi gyűrű integritástartomány, tehát egységelemes.

Ha aa és bb közül mindkettő 0R0_R, akkor a 17.6. Tétel 5. pontja miatt a kitüntetett közös osztójuk 0R0_R, amely nyilvánvalóan kifejezhető a kívánt alakban, méghozzá tetszőleges uu és vv elemekkel:

0R⏟=a⋅u+0R⏟=b⋅v=0R⏟=(a,b)\underbrace{0_R}_{=a}\cdot u+\underbrace{0_R}_{=b}\cdot v=\underbrace{0_R}_{=(a,b)}

Ha aa és bb közül csak az egyikük 0R0_R, akkor viszont ugyanezen tétel 4. pontja miatt a kitüntetett közös osztójuk a másik elem lesz. Ha például a≠0Ra\neq 0_R és b=0Rb=0_R, akkor (a,b)=(a,0R)∼a(a,b)=(a,0_R)\sim a. Ez nyilván kifejezhető a kívánt alakban u=1Ru=1_R és tetszőleges vv elemekkel:

a⋅1R⏟=u+0R⏟=b⋅v=(a,b)⏟∼aa\cdot \underbrace{1_R}_{=u}+\underbrace{0_R}_{=b}\cdot v=\underbrace{(a,b)}_{\sim a}

Értelemszerűen ha a=0Ra=0_R és b≠0Rb\neq 0_R, akkor pedig v=1Rv=1_R és uu tetszőleges.

Az általánosság megsértése nélkül feltételezhetjük tehát, hogy a≠0Ra\neq 0_R és b≠0Rb\neq 0_R. Ekkor lefuttathatjuk erre a két elemre, mint bemenetre a 17.18. Tétel bizonyításában ismertetett euklidészi algoritmust, amely az ott ismertetett gondolatmenet alapján garantáltan befejeződik véges számú lépés után.

Tegyük fel, hogy az algoritmus futtatásakor az nn-edik maradékos osztás során kapjuk meg az utolsó nemnulla maradékot, amely ugye az (a,b)(a,b) kitüntetett közös osztó lesz. Ez tehát az alábbi nn darab maradékos osztást jelenti:

a=k1b+r1b=k2r1+r2r1=k3r2+r3r2=k4r3+r4⋮rn−2=knrn−1+rn⏟=(a,b)\begin{aligned} a&=k_1b+r_1 \\ b&=k_2r_1+r_2 \\ r_1&=k_3r_2+r_3 \\ r_2&=k_4r_3+r_4 \\ &\vdots \\ r_{n-2}&=k_nr_{n-1}+\underbrace{r_n}_{=(a,b)} \end{aligned}

Az utolsó maradékos osztást itt nem tüntettük fel, amelynek során végül a 0R0_R maradékot megkapjuk és amely terminálja az algoritmust.

Célunk tehát, hogy az nn-edik lépésben megkapott rnr_n maradékot kifejezzük rn=au+bvr_n=au+bv alakban valamilyen uu és vv elemek segítségével. Vegyük észre, hogy az első maradékos osztást leíró egyenlet mindkét oldalából k1bk_1b-t kivonva kapunk egy ehhez hasonló kifejezést az r1r_1 maradékra. Jelöljük az így kapott együtthatókat u1u_1-gyel és v1v_1-gyel:

r1=a−k1b=a⋅1⏟=u1+b⋅(−k1)⏟=v1r_1=a-k_1b=a\cdot \underbrace{1}_{=u_1}+b\cdot \underbrace{(-k_1)}_{=v_1}

Az első lépésben kapott r1r_1 maradékot tehát ilymódon kifejeztük az aa és bb lineáris kombinációjaként az u1=1u_1=1 és a v1=−k1v_1=-k_1 együtthatók segítségével. Most tegyük meg ugyanezt a második lépésben kapott r2r_2 maradékkal is. Ehhez semmi mást nem kell tennünk, mint a második maradékos osztást leíró egyenlet mindkét oldalából levonnunk k2r1k_2r_1-et, majd r1r_1 helyére behelyettesíteni az előző lépésben kapott kifejezést. Jelöljük az így kapott együtthatókat u2u_2-vel és v2v_2-vel:

r2=b−k2r1=b−k2(a−k1b⏞=r1)==a⋅(−k2)⏟=u2+b⋅(1+k1k2)⏟=v2\begin{aligned}r_2&=b-k_2r_1=b-k_2(\overbrace{a-k_1b}^{=r_1})=\\&=a\cdot \underbrace{(-k_2)}_{=u_2} + b\cdot \underbrace{(1+k_1k_2)}_{=v_2}\end{aligned}

A második lépésben kapott r2r_2 maradékot tehát szintén kifejeztük az aa és bb lineáris kombinációjaként az u2=−k2u_2=-k_2 és a v2=1+k1k2v_2=1+k_1k_2 együtthatók segítségével.

Ezt az eljárást persze folytathatnánk egészen az nn-edik lépésig, amikor végül az rnr_n kitüntetett közös osztót is megkapnánk aa és bb lineáris kombinációjaként. Mi azonban lusták vagyunk, ezért adunk egy általános képletet, amely megadja, hogy a soron következő rir_i maradékot hogyan lehet előállítani aa és bb lineáris kombinációjaként, ha egyébként az ri−2r_{i-2} és ri−1r_{i-1} maradékokra ez az előállítás már ismert.

Tegyük fel tehát, hogy az alábbi lineáris kombinációs előállításokat már ismerjük, azaz az alábbi kifejezésekben szereplő ui−2u_{i-2} és vi−2v_{i-2} valamint ui−1u_{i-1} és vi−1v_{i-1} együtthatókat már kiszámítottuk:

ri−2=a⋅ui−2+b⋅vi−2ri−1=a⋅ui−1+b⋅vi−1\begin{aligned}r_{i-2}&=a\cdot u_{i-2} + b\cdot v_{i-2} \\ r_{i-1}&=a\cdot u_{i-1} + b\cdot v_{i-1}\end{aligned}

Feladatunk előállítani az rir_i maradékot az aa és bb elemek lineáris kombinációjaként. Ehhez először is tekintsük az euklidészi algoritmus futtatása során kapott ii-edik maradékos osztást leíró egyenletet:

ri−2=kiri−1+rir_{i-2}=k_ir_{i-1}+r_i

Mindkét oldalából vonjunk le kiri−1k_ir_{i-1}-et:

ri−2−kiri−1=rir_{i-2}-k_ir_{i-1}=r_i

Az ii-edik lépésben kapott rir_i maradékot tehát kifejeztük az ri−2r_{i-2} és ri−1r_{i-1} lineáris kombinációjaként. Ez utóbbi kettőről viszont azt mondtuk, hogy már előállítottuk őket aa és bb lineáris kombinációjaként. Helyettesítsük is be a fenti egyenletbe ezeket az előállításokat:

ri=(aui−2+bvi−2⏟=ri−2)−ki⋅(aui−1+bvi−1⏟=ri−1)r_i=(\underbrace{au_{i-2} + bv_{i-2}}_{=r_{i-2}})-k_i\cdot (\underbrace{au_{i-1} + bv_{i-1}}_{=r_{i-1}})

Ezt a 14.12. Definícióban szereplő gyűrűaxiómáknak megfelelően átrendezve megkapjuk rir_i-t is aa és bb lineáris kombinációjaként. Jelöljük az így kapott együtthatókat uiu_i-vel és viv_i-vel:

ri=a⋅(ui−2−kiui−1⏟=ui)+b⋅(vi−2−kivi−1⏟=vi)r_i=a\cdot (\underbrace{u_{i-2}-k_iu_{i-1}}_{=u_i}) + b\cdot (\underbrace{v_{i-2}-k_iv_{i-1}}_{=v_i})

Ezzel a bizonyításunk teljes, mivel az első két lépésben kapott r1r_1 és r2r_2 maradékokat előállítottuk aa és bb lineáris kombinációjaként, az imént konstruált képlet alapján pedig elő tudjuk állítani a további maradékokat is. Ezek közül ugye az nn-edik lépés során kapott rn=aun+bvnr_n=au_n+bv_n előállítás épp az (a,b)(a,b) kitüntetett közös osztó előállítása az aa és bb lineáris kombinációjaként.

∎