Fölérendelt lap:17.20. TételAz abszolútérték euklidészi függvény

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.

∎

Iratkozz fel a hírlevelünkre