youproof.orgDeep Math. Human Access.

Bizonyítás

A 17.17. Definíció 1. pontja alapján egyrészt azt kell megmutatni, hogy tetszőleges a és b\neq 0 egész számokhoz léteznek k és r egész számok úgy, hogy teljesül az alábbi egyenlet:

a=kb+r

Másrészt pedig a 17.17. Definíció 2. pontja alapján azt is meg kell mutatni, hogy emellett legalább az egyik teljesül az alábbiak közül:

\begin{aligned} r&=0 \\ |r|&<|b| \end{aligned}

Mivel a \Z gyűrűben vagyunk, és a 17.19. Definíció alapján r=0 ekvivalens |r|=0-val, ezért ez utóbbi feltétel az alábbi rövidebb alakban is leírható:

0\leq |r|<|b|

A bizonyítás további részében ezt az alakot fogjuk használni.

A bizonyítás konstruktív lesz, azaz k és r létezését azáltal igazoljuk, hogy egy eljárást mutatunk a kiszámításukra. Ez az eljárás a gyakorlatban nem lenne túl hatékony, ám nekünk a bizonyításhoz épp elegendő lesz. Továbbá ki fogjuk használni, hogy a 15.18. Tételben definiált \leq reláció teljesíti a 15.11. Definícióban megfogalmazott rendezési axiómákat.

Először szorítkozzunk arra az esetre, amikor egyik bemeneti számunk sem negatív, azaz teljesülnek az alábbiak:

\begin{aligned} 0&\leq a \\ 0&\lt b \end{aligned}

Az eljárás lényege, hogy a hányadost és a maradékot próbálgatással keressük meg az alábbi lépéseket végrehajtva:

\begin{aligned} a&=0b+\underbrace{a}_{=r_0} \\ a&=1b+\underbrace{(a-b)}_{=r_1} \\ a&=2b+\underbrace{(a-2b)}_{=r_2} \\ &\vdots \\ a&=k_ib+\underbrace{(a-k_ib)}_{=r_i} \\ a&=k_{i+1}b+\underbrace{(a-k_{i+1}b)}_{=r_{i+1}} \\ &\vdots \end{aligned}

Itt az i-edik lépésben kipróbált hányados-jelöltet k_i-vel, míg az ugyanebben a lépésben kipróbált maradék-jelöltet r_i-vel jelöltük.

Nyilván mindegyik egyenlet teljesül, hiszen minden lépésben tulajdonképpen annyi történik, hogy a jobboldalhoz hozzá is adunk, és ki is vonunk b-t. Csak épp a hozzáadást a hányados-jelölt 1-gyel történő megnövelésével, míg a kivonást a maradék-jelölt b-vel történő csökkentésével érjük el. Emiatt az i-edik lépésből az i+1-edik lépésbe így jutunk:

\begin{aligned} k_{i+1}&=k_i+1 \\ r_{i+1}&=r_i-b \end{aligned}

Az eljárás megkezdésekor a kiinduló állapot: k_0=0 és r_0=a.

Az eljárást mindaddig nem fejezzük be, ameddig az aktuális r_i maradék-jelöltre már igaz nem lesz, hogy r_i<b. A befejezés előtti lépésekben tehát még b\leq r_i, és ezekben az esetekben, mivel a 15.11. Definíció szerinti 1. rendezési axióma alapján a \leq reláció kompatibilis az összeadással, ezért teljesül az alábbi:

0\leq \underbrace{r_i-b}_{=r_{i+1}}

Azaz egyrészt minden újabb lépésben folyamatosan nemnegatív maradék-jelölteket kapunk, azok tehát mindannyian természetes számok.

Másrészt, mivel r_{i+1}=r_i-b, ezért r_{i+1}+b=r_i, de ugye a bizonyítás elején egyelőre kikötöttük, hogy 0<b, emiatt:

r_{i+1}<r_i

Azaz minden újabb lépésben szigorúan kisebb maradék-jelölteket kapunk, mint az azt megelőző lépésben.

Az eljárás emiatt nyilván véges számú lépés után garantáltan befejeződik, máskülönben egy végtelen leszálló természetes számokból álló sorozatot kapnánk, ami a 17.15. Tétel miatt ellentmondás. Az utolsó lépésben tehát az előbbiek alapján kaptunk egy olyan k hányadost és r maradékot, amelyekre teljesül, hogy

\begin{aligned} a&=kb+r \\ 0&\leq r\lt b \end{aligned}

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor 0<b – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0\leq \underbrace{|r|}_{=r}<\underbrace{|b|}_{=b}

Azaz ebben az esetben teljesülnek a euklidészi függvényre vonatkozó követelmények.

Eddig tehát azt az esetet fedtük le, amikoris 0\leq a és 0\lt b. Ennek az eredménynek az általánosítása a többi előjel-kombinációra már egyszerű. Az alábbiakban ennek technikai részleteit ismertetjük.

0\leq a ~~\text{és}~~ b\lt 0

Ekkor a 15.9. Lemma 1. pontja miatt 0\lt (-b), tehát a fenti eljárás szóról szóra megismételhető, csak ekkor b helyét (-b) veszi át. Az utolsó lépésben így kapunk egy olyan k hányadost és r maradékot, amelyekre teljesülnek az alábbiak:

\begin{aligned} a&=k(-b)+r \\ 0&\leq r\lt (-b) \end{aligned}

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor 0<(-b) – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0\leq \underbrace{|r|}_{=r}<\underbrace{|-b|}_{=(-b)}

Nekünk azonban a-nak (-b) helyett a b-vel történő maradékos osztására, és ezért a |-b| helyett a |b| abszolút értékre van szükségünk. De semmi gond, mivel a 15.1. Tétel 3. pontja, valamint az abszolútérték-függvény 17.19. Definíciója miatt a fenti egyenlet és az abszolút értékekre vonatkozó egyenlőtlenség átírható:

\begin{aligned} a&=(-k)b+r \\ 0&\leq |r|\lt \underbrace{|b|}_{=|-b|} \end{aligned}

Azaz ebben az esetben is teljesülnek a euklidészi függvényre vonatkozó követelmények.

a\leq 0 ~~\text{és}~~ 0\lt b

Ekkor a 15.9. Lemma 1. pontja miatt 0\leq (-a), tehát a fenti eljárás szóról szóra megismételhető, csak ekkor a helyét (-a) veszi át. Az utolsó lépésben így kapunk egy olyan k hányadost és r maradékot, amelyekre teljesülnek az alábbiak:

\begin{aligned} (-a)&=kb+r \\ 0&\leq r\lt b \end{aligned}

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor 0<b – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0\leq \underbrace{|r|}_{=r}<\underbrace{|b|}_{=b}

Nekünk azonban (-a) helyett a-nak a b-vel történő maradékos osztására van szükségünk. De semmi gond, mivel a 15.1. Tétel 2., 5. és 3. pontjai, valamint az abszolútérték-függvény 17.19. Definíciója miatt a fenti egyenlet és az abszolút értékekre vonatkozó egyenlőtlenség átírható:

\begin{aligned} a&=(-k)b+(-r) \\ 0&\leq \underbrace{|-r|}_{=|r|}\lt |b| \end{aligned}

Azaz ebben az esetben is teljesülnek a euklidészi függvényre vonatkozó követelmények.

a\leq 0 ~~\text{és}~~ b\lt 0

Ekkor a 15.9. Lemma 1. pontja miatt 0\lt (-b) és 0\leq (-a), tehát a fenti eljárás szóról szóra megismételhető, csak ekkor a helyét (-a) és b helyét (-b) veszi át. Az utolsó lépésben így kapunk egy olyan k hányadost és r maradékot, amelyekre teljesülnek az alábbiak:

\begin{aligned} (-a)&=k(-b)+r \\ 0&\leq r\lt (-b) \end{aligned}

A lenti egyenlőtlenség viszont ebben a speciális esetben – tehát amikor 0<(-b) – a 17.19. Definíció alapján az abszolút értékekre vonatkozóan épp azt jelenti, hogy

0\leq \underbrace{|r|}_{=r}<\underbrace{|-b|}_{=(-b)}

Nekünk azonban (-a) helyett a-nak a (-b) helyett b-vel történő maradékos osztására, és ezért a |-b| helyett a |b| abszolút értékre van szükségünk. De semmi gond, mivel a 15.1. Tétel 2., 5., 3. és 4. pontjai, valamint az abszolútérték-függvény 17.19. Definíciója miatt a fenti egyenlet és az abszolút értékekre vonatkozó egyenlőtlenség átírható:

\begin{aligned} a&=kb+(-r) \\ 0&\leq \underbrace{|-r|}_{=|r|}\lt \underbrace{|b|}_{=|-b|} \end{aligned}

Azaz ebben az esetben is teljesülnek a euklidészi függvényre vonatkozó követelmények.

Ezzel már minden esetet lefedtünk, azaz tetszőleges a és b\neq 0 elemek között elvégezhető az abszolútérték-függvény szerinti maradékos osztás. Ez a függvény tehát valóban egy euklidészi függvény a \Z gyűrűn.

∎