Fölérendelt lap:18.2. TételEgész számok maradékos osztása egyértelmű

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.

∎

Iratkozz fel a hírlevelünkre