Episode I

Alice és Bob

. rész: Az abszolútérték-függvény euklidészi norma – bizonyítás

Az abszolútérték-függvény képhalmaza a 17.18. Definíció alapján valóban a természetes számok \N halmaza, hiszen az abszolútérték biztosan nemnegatív. A \Z gyűrű nullelemének képe szintén a definíció alapján a 0 természetes szám. Visszafelé: ha |a|=0, akkor az alábbi két eset lehetséges:

\begin{aligned}a&=0\\-a&=0\end{aligned}

Az \Z gyűrűben tehát pontosan a nullelemnek lesz 0 az abszolútértéke, azaz teljesül az euklidészi normákra vonatkozó 1. követelmény (lásd a 17.16. Definíciót). Így már csak azt kell megmutatni, hogy tetszőleges a és b\neq 0 egész számok között elvégezhető a maradékos osztás az abszolútérték-függvény, mint norma szerint. Azaz léteznek k és r egész számok úgy, hogy teljesülnek az alábbiak:

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

Ehhez ki fogjuk használni, hogy a 15.18. Definíció szerinti \leq reláció teljesíti a 15.11. Definícióban megfogalmazott rendezési axiómákat. 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.

Először szorítkozzunk arra az esetre, amikor egyik bemeneti számunk sem negatív, azaz a\geq 0 és b\gt 0. Tegyük fel továbbá, hogy k_1=0 és r_1=a. Ekkor nyilván teljesül az alábbi:

a=\underbrace{k_1}_{=0}b+\underbrace{r_1}_{=a}

Ha r_1\lt b, akkor az eljárást befejezhetjük, és r_1 lesz a keresett maradék. Ha nem – azaz r_1\geq b –, akkor folytatnunk kell az eljárást. A jobboldalhoz hozzáadva és levonva b-t az eredmény nyilván nem változik. Így a fenti egyenlet a disztributivitási szabályokat kihasználva az alábbi alakba írható, megkapva ezáltal a k_2 és r_2 számokat:

a=k_1b+r_1-b+b=\underbrace{(k_1+1)}_{=k_2}b+\underbrace{r_1-b}_{=r_2}

Mivel ugye r_1\geq b, és a 15.11. Definíció 1. pontja alapján a rendezési reláció kompatibilis az összeadással, ezért az egyenlőtlenség mindkét oldalához -b-t adva \underbrace{r_1-b}_{=r_2}\geq 0. Igaz továbbá, hogy r_2+b=r_1, és mivel b-ről kikötöttük, hogy nem 0, ezért ez azt jelenti, hogy r_2\lt r_1. Találtunk tehát egy r_1-nél kisebb nemnegatív jelöltet a keresett maradékra.

Ha r_2\lt b, akkor az eljárást befejezhetjük, és r_2 lesz a keresett maradék. Ha nem, akkor az előbbi gondolatmenetet megismételve tudunk találni újabb és újabb nemnegatív jelölteket, melyek mindegyike kisebb, mint az előző lépésben kapott jelölt. Az eljárásnak garantáltan véget kell érnie egyszer, máskülönben az alábbi végtelen hosszú nemnegatív egészekből álló sorozatot kapnánk:

r_1\gt r_2\gt r_3\gt \ldots

Ez a természetes számoknak egy olyan részhalmaza lenne, amelynek nem létezne minimuma, ami a 17.14. Tétel alapján lehetetlen. Így megmutattuk, hogy a\geq 0 és b\gt 0 esetén az a elem felírható a=kb+r alakban úgy, hogy teljesüljön a 0\leq r\lt b egyenlőtlenség. Ez az egyenlőtlenség viszont ebben a speciális esetben épp azt jelenti, hogy |r|\lt |b|.

Most általánosítsuk ezt az eredményt először a b\lt 0 esetre. Ekkor a 15.9. Lemma 1. pontja miatt (-b)\gt 0. Így a fenti gondolatmenet alapján az a egész szám felírható a=k(-b)+r=(-k)b+r alakban úgy, hogy teljesüljön a 0\leq r\lt (-b) egyenlőtlenség. Minthogy 0\lt r és b\lt 0, ezért ez az egyenlőtlenség az abszolútértékekre vonatkozóan épp azt jelenti, hogy |r|\lt \underbrace{|b|}_{=|-b|}. Így lefedtük az összes olyan esetet, amikor a\geq 0 és b\neq 0.

Végül nézzük meg, mi van akkor, ha a\leq 0. Ekkor szintén a 15.9. Lemma miatt (-a)\geq 0, és így a fentiek alapján ő felírható (-a)=kb+r alakban úgy, hogy |r|\lt |b|. De ekkor mindkét oldal ellentettjét véve azt kapjuk, hogy a=(-k)b+(-r), miközben teljesül, hogy \underbrace{|-r|}_{=|r|}\lt |b|.

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 norma a \Z gyűrűn.

Kapcsolódó oldal:
Érintő - Elektronikus Matematikai Lapok