Veta o delení so zvyškom

[Martin Sleziak]

Vo viacerých úvahách využívame fakt, ktorému sa hovorí veta o delení so zvyškom.
Najmä keď pracujeme grupou $\mathbb Z_n$ (so sčitovaním modulo $n$) alebo okruhom $\mathbb Z_n$ (so sčitovaním a násobením modulo $n$), ale aj inde (napríklad v dôkaze vety že každá podgrupa grupy $(\mathbb Z,+)$ má tvar $m\mathbb Z=\{m\cdot z; z\in\mathbb Z\}$ pre vhodné $\mathbb Z$).

Veta o delení so zvyškom: Nech $a$, $b$ sú celé čísla a navyše $b>0$. Potom existujú čísla $q,r\in\mathbb Z$ také, že platí
$$a=q\cdot b+r \qquad\text{a}\qquad 0\le r <b.$$
Navyše tieto čísla $q$ a $r$ sú uvedenými podmienkami jednoznačne určené.

V znení vety som tieto číslo označil $q$ (z anglického quotient) a $r$ (z anglického remainder). Aj ich zvykneme volať podiel a zvyšok.

Fakt, ktorý tu spomínam je pomerne jasný. (A navyše to je niečo, čo pravdepodobne poznáte zo strednej školy - aj keď možno ste to nemali sformulované v takejto podobe, tak to že deliť so zvyškom sa dá a ako sa to robí viete.) Aj tak sa môžeme skúsiť zamyslieť nad tým, či by sme to vedeli nejako poriadne dokázať.
Skúsim sem pridať aj pár odkazov, kde sa dá dôkaz nájsť. Ale napíšem dôkaz aj sem na fórum - neviem, do akej miery sa mi to podarí, ale rád by som ho napísal ako postupnosť hintov, aby ste mohli skúsiť prísť na dôkaz tejto vety aj sami. (A samozrejme môžete začať tým, že sa zamyslíte nad tým, čo by ste vedeli dokázať aj bez toho, že dostanete nejaké hinty.)
Samozrejme, toto určite nie je jediná možnosť ako dokazovať toto tvrdenie. (Môžete sa napríklad zamyslieť nad tým, či by ste vedeli napísať nejaký rozumný dôkaz, ktorý by sa robil indukciou.)

[Martin Sleziak]

Dôkaz

Zvlášť sa skúsme pozrieť na to ako dokážeme existenciu a na to ako dokážeme jednoznačnosť.

1. Existencia.

Hint 1:

Spoiler:

Ak sa pozriete na podmienky, ktoré majú spĺňať čísla $q$ a $r$, tak určite musí platiť $q\cdot b\le a$. Viete povedať niečo o množine
$$\{k\in\mathbb Z; kb\le a\}$$
čo by nám mohlo pomôcť? (Inak povedané, pozeráme sa na násobky čísla $b$, ktoré neprevýšia číslo $a$.)

Hint 2:

Spoiler:

Azda nie je ťažké skontrolovať, že množina $\{k\in\mathbb Z; kb\le a\}$ je zhora ohraničená.
Ak mám zhora ohraničenú množinu celých čísel, viem z nej vybrať nejaký špeciálny prvok?

Hint 3:

Spoiler:

Každá zhora ohraničená množina prirodzených čísel má najväčší prvok. Existuje teda maximum
$$q=\max\{k\in\mathbb Z; kb\le a\}.$$
Ak sme takto zvolili $q$, vedeli by ste dokázať, že už vieme dostať že sú splnené podmienky uvedené vo vete?

Tu už je v podstate kompletný dôkaz existencie, ktorý ide takým smerom ako je naznačený v uvedených hintoch:

Spoiler:

Dôkaz.
Máme dané celé čísla $a$, $b$ pričom $b$ je kladné.

Potom množina
$$M=\{k\in\mathbb Z; kb\le a\}$$
je zhora ohraničená. (Stačí si uvedomiť, že $kb\le a$ je ekvivalentné s $b\le\frac ak$.)

Ľubovoľná zhora ohraničená množina celých čísel má najväčší prvok. (Toto by mohlo byť jasné - súvisí to s niečím čomu sa zvykne hovoriť princíp dobrého usporiadania a budete o ňom pravdepodobne hovoriť na diskrétnej matematike, takže tu to nebudem detailne rozoberať.)
Položme
$$q=\max M = \max\{k\in\mathbb Z; kb\le a\}.$$

Potom aby platilo $a=qb+r$, tak musíme zobrať
$$r=a-qb.$$

Všimnime si, že $a \ge qb$. (Vyplýva to z toho že $q\in M$.)
Teda $$r= a-qb \ge 0.$$

Súčasne však $q+1\notin M$. (Pretože $q$ je najväčší prvok tejto množiny.)
To znamená, že $a<(q+1)b$, a teda
$$r=a-qb<b.$$

Vidíme, že čísla $q$ a $r$ zvolené takýmto spôsobom spĺňajú podmienky uvedené v tvrdení vety.

2. Jednoznačnosť.

Asi je hlavné uvedomiť si, čo vlastne znamená to, že $q$ a $r$ sú jednoznačne určené.

Spoiler:

Chceme ukázať, že ak
$$q_1b+r_1=q_2b+r_2 \qquad\text{pričom }0\le r_{1,2} < b,$$
tak $q_1=q_2$ a $r_1=r_2$.

Toto nie je veľmi ťažké overiť:

Spoiler:

Z $q_1b+r_1=q_2b+r_2$ dostaneme
\begin{gather*}
(q_1-q_2)b=r_1-r_2\\
|q_1-q_2|b=|r_1-r_2|
\end{gather*}
Pretože $r_1$ aj $r_2$ sú celé čísla z rozsahu $0,1,\dots,b-1$, tak máme $0\le |r_1-r_2|\le b-1$.
Jediný celočíselný násobok čísla $b$ v tomto rozsahu je $0\cdot b=0$, čo znamená, že
$$|q_1-q_2|b=|r_1-r_2|=0$$
čiže $q_1-q_2=r_1-r_2=0$, a teda $q_1=q_2$, $r_1=r_2$.

[Martin Sleziak]

Ak sa chcete pozrieť na to, ako je to dokázané inde, tak sa to dá nájsť na veľa miestach. Aspoň zopár, ktoré som narýchlo našiel sem napíšem.

Literatúra

• Katriňák a kol.: Algebra a teoretická aritmetika 1 - Veta 1.5.1
• Šalát a kol: Algebra a teoretická aritmetika 2 - Lema 3.1.1
• Veselý: O dělitelnosti čísel celých (ŠMM 14) - $T_{11}$ a $T_{12}$

Linky

• Wikipedia Euclidean division
• ProofWiki: Division Theorem
• Poznámky k predmetu Elementárna teória čísel (v súčasnej verzii veta 1.1.3)
• Poznámky k predmetu Teória čísel (v súčasnej verzii veta 2.1.1)