youproof.orgDeep Math. Human Access.

Bizonyítás

Előszöris azt igazoljuk, hogy a maradékos osztás ezekkel a szigorúbb feltételekkel is elvégezhető, azaz mindenképpen létezik nemnegatív maradék is.

A 17.20. Tétel alapján tudjuk, hogy az abszolútérték-függvény egy euklidészi függvény a \Z gyűrűn. Ez a 17.17. Definíció szerint azt jelenti, hogy tetszőleges a és b\neq 0 egész számokhoz létezik olyan k_0 hányados és r_0 maradék, amelyekre teljesülnek az alábbiak:

\begin{aligned} a&=k_0\cdot b + r_0 \\ 0&\leq|r_0|\lt |b| \end{aligned}

Feladatunk megmutatni, hogy ezekből előállítható olyan k hányados és r maradék is, amelyek a tételben szereplő szigorúbb feltételeknek is eleget tesznek. Amennyiben 0\leq r_0, akkor az abszolútérték-függvény 17.19. Definíciója miatt |r_0|=r_0, és ezért az r=r_0 és a k=k_0 választás épp megfelel a feltételeknek.

Így elegendő csak azzal az esettel foglalkozni, amikor r_0\lt 0. Ekkor az abszolútérték-függvény definíciója miatt |r_0|=-r_0. Mivel r_0\lt 0, ezért a 15.9. Lemma 1. pontja miatt -r_0\gt 0. Ekkor az euklidészi függvényre vonatkozó |r_0|\lt|b| feltétel az alábbi két eset valamelyikével ekvivalens attól függően, hogy b pozitív vagy negatív:

\begin{aligned} \text{b pozitív} &\implies 0\lt -r_0\lt b \\ \text{b negatív} &\implies 0\lt -r_0\lt -b \end{aligned}

A jobboldali egyenlőtlenségekhez r_0-t, a baloldali egyenlőtlenségekhez pedig negatív b esetén (r_0+b)-t, pozitív b esetén pedig (r_0-b)-t adva az alábbiakat kapjuk:

\begin{aligned} \text{b pozitív} &\implies 0\lt r_0+b\lt b \\ \text{b negatív} &\implies 0\lt r_0-b\lt -b \end{aligned}

Azaz ha meg tudnánk oldani, hogy az eredeti a=k_0b+r_0 egyenletből kiindulva olyan maradékos osztást végezzünk, amelynek eredményeképp az első esetben (r_0+b), a második esetben pedig (r_0-b) legyen a maradék, akkor ezek eleget tennének a tételben szereplő feltételeknek. Ezt viszont a 14.12. Definíció 5. pontja szerinti disztributivitási szabályok kihasználásával és egy piszkos kis trükkel minden gond nélkül meg tudjuk tenni.

Egyrészt pozitív b esetén:

a=k_0b+r_0+\underbrace{b-b}_{=0}=(\underbrace{k_0-1}_{=k})b + \underbrace{r_0+b}_{=r}\\

Másrészt negatív b esetén:

a=k_0b+r_0+\underbrace{b-b}_{=0}=(\underbrace{k_0+1}_{k})b + \underbrace{r_0-b}_{r}

Így tehát az első esetben a k=k_0-1 és r=r_0+b választással, második esetben pedig a k=k_0+1 és r=r_0-b választással az r maradék garantáltan pozitív lesz. Ezzel minden esetet lefedtünk, az egész számok körében tehát valóban mindig elvégezhető a maradékos osztás úgy, hogy a kapott maradék nemnegatív.

Azt kell még igazolni, hogy ilyen feltételekkel viszont már csak egyféleképpen végezhető el. Tegyük fel indirekt, hogy kétféleképpen is elvégezhető a nemnegatív maradékos osztás. Ez azt jelenti, hogy léteznek olyan k_1 és k_2 hányadosok, valamint nemnegatív r_1 és r_2 maradékok, amelyekre teljesülnek az alábbiak:

\begin{aligned} &a=k_1\cdot b + r_1 \\ &a=k_2\cdot b + r_2 \\ &0\leq r_1 \lt |b| \\ &0\leq r_2\lt |b| \end{aligned}

A két egyenletet egymásból kivonva a következőt kapjuk:

0=(k_1-k_2)\cdot b + r_1 - r_2

Mindkét oldalból (k_1-k_2)\cdot b-t kivonva az alábbi lesz a szituáció:

\underbrace{(k_2-k_1)}_{=-(k_1-k_2)}\cdot b = r_1-r_2

Ez viszont a 16.1. Definíció alapján épp azt jelenti, hogy teljesül az alábbi oszthatóság:

b|r_1-r_2

Ekkor viszont r_1-re és r_2-re alkalmazható a 18.1. Lemma, amiből

r_1=r_2

következik, azaz a maradékok valóban megegyeznek.

Emiatt viszont a korábban kapott (k_2-k_1)\cdot b = r_1-r_2 egyenlet az alábbi alakra egyszerűsödik:

(k_2-k_1)\cdot b = \underbrace{0}_{=r_1-r_2}

Mivel a tétel szövegében kikötöttük, hogy b\neq 0, ezért a nullosztómentesség miatt ez csak akkor teljesülhet, ha k_2-k_1=0, amiből

k_1=k_2

következik, és így a hányadosok is megegyeznek.

∎