Twierdzenie o dzieleniu z resztą

[tranto]

Twierdzenie brzmi następująco: jeśli \(\displaystyle{ n, d \in \mathbb{N}_{0}}\) oraz \(\displaystyle{ d>0}\), to istnieje dokładnie jedna para liczb naturalnych \(\displaystyle{ q}\) i \(\displaystyle{ r}\) takich, że \(\displaystyle{ n=qd+r}\) , przy czym \(\displaystyle{ r<d}\).

Dowód:
1) Istnienie.
Niech \(\displaystyle{ T=\{t \in \mathbb{N}_{0}: td \le n \} \subseteq \mathbb{N}_{0}}\). Zbiór \(\displaystyle{ T}\) jest niepusty, ponieważ \(\displaystyle{ 0 \in T}\). Również dla \(\displaystyle{ t \in T: t \le td \le n}\), zatem \(\displaystyle{ t \le n}\). Więc zbiór \(\displaystyle{ T}\) jest ograniczony z góry przez \(\displaystyle{ n}\), a zatem ma maksymalny element \(\displaystyle{ q}\).

Niech \(\displaystyle{ r = n-qd}\). Pozostaje wykazać, że \(\displaystyle{ r<d}\). Ale wiemy, że \(\displaystyle{ q}\) jest największym elementem \(\displaystyle{ T}\) i wobec tego \(\displaystyle{ q+1 \not\in T}\), czyli \(\displaystyle{ d(q+1)>n}\). Zatem \(\displaystyle{ r = n - qd <d(q+1) - qd = d}\), c.n.d.

2) Jednoznaczność.
Teraz wykażemy, że dane liczby \(\displaystyle{ q}\) i \(\displaystyle{ r}\) są wyznaczone jednoznacznie. Niech \(\displaystyle{ q, q'}\) oraz \(\displaystyle{ r, r'}\) będą liczbami naturalnymi takimi, że
\(\displaystyle{ \begin{cases}n = qd+r, \ r < d\\ n=q'd + r', \ r'<d.\end{cases}}\)
Wynika stąd, że \(\displaystyle{ (q-q')d=r'-r.}\)

Przypuśćmy, że \(\displaystyle{ r \neq r'}\). Bez straty ogólności możemy założyć, że \(\displaystyle{ r<r'}\). Wynika stąd, że \(\displaystyle{ r'-r < d}\), w przeciwnym razie bowiem mielibyśmy \(\displaystyle{ r' \ge d + r \ge d}\), wbrew założeniu.

Zatem \(\displaystyle{ (q-q')d=r'-r<d}\), a więc \(\displaystyle{ (q-q')d<d}\), a ponieważ \(\displaystyle{ d>0}\), to dzieląc przed \(\displaystyle{ d}\) otrzymujemy nierówność \(\displaystyle{ q-q'<1}\), czyli \(\displaystyle{ q-q'=0}\). Z nierówności \(\displaystyle{ (q-q')d=r'-r}\) wynika wobec tego, że również \(\displaystyle{ r-r'=0}\) i \(\displaystyle{ r =r'}\) - wbrew założeniu, że \(\displaystyle{ r \neq r'}\).

Wynika stąd, że \(\displaystyle{ r=r'}\), a stąd - że również \(\displaystyle{ q=q'}\), c.n.d.

Proszę o sprawdzenie poprawności zamieszczonego powyżej dowodu.

[Piotr Rutkowski]

Dowód jest całkowicie poprawny, co więcej bardzo dokładny.

[tranto]

Uogólniona postać tego twierdzenia brzmi następująco:

Niech \(\displaystyle{ n, d \in \mathbb{Z}}\) oraz \(\displaystyle{ d \neq 0}\). Wówczas istnieje dokładnie jedna para liczb całkowitych \(\displaystyle{ q, r}\) spełniających warunki:
\(\displaystyle{ \begin{cases}n = qd+r\\ 0 \le r< |d|.\end{cases}}\)
Ponieważ nie rozumiem na razie dowodu pokazanego na polskiej Wikipedii, więc postaram się oprzeć w dowodzie na twierdzeniu udowodnionym powyżej.

Dowód:
Wykazaliśmy już, że twierdzenie jest prawdziwe dla \(\displaystyle{ n \in \mathbb{N}_{0}, \ d \in \mathbb{N}_{+}.}\)

1. Istnienie:
Poszostaje wykazać, że taka para liczb istnieje również w pozostałych trzech przypadkach:
\(\displaystyle{ 1^\circ \begin{cases} -n \in \mathbb{N}_{+}\\ d \in \mathbb{N}_{+}\end{cases}}\)
Wówczas istnieją liczby \(\displaystyle{ q', r' \in \mathbb{N}_{0}}\), takie że \(\displaystyle{ -n=q'd + r'}\) i \(\displaystyle{ 0 \le r' < d.}\)
Jeśli \(\displaystyle{ r'=0}\), to \(\displaystyle{ n=(-q')d}\) i wystarczy przyjąć \(\displaystyle{ q=-q'}\) i \(\displaystyle{ r=0}\).
Jeżeli \(\displaystyle{ r' > 0}\), to \(\displaystyle{ n = -q'd-r'= -(q'+1)d+(d-r').}\)
Z założenia \(\displaystyle{ r'>0}\), więc \(\displaystyle{ -r'<0}\) i w konsekwencji \(\displaystyle{ d-r'<d=|d|}\). Ponadto z założenia \(\displaystyle{ r'<d}\), więc \(\displaystyle{ d-r'>0}\), i w konsekwencji \(\displaystyle{ d-r' \ge 0.}\)
Zatem wystarczy przyjąć \(\displaystyle{ q=-(q'+1), r=d-r'.}\)

Przypadki:
\(\displaystyle{ 2^\circ \begin{cases} -n \in \mathbb{N}_{+}\\ -d \in \mathbb{N}_{+}\end{cases}}\)
i
\(\displaystyle{ 3^\circ \begin{cases} n \in \mathbb{N}_{0}\\ -d \in \mathbb{N}_{+}\end{cases}}\)
dowodzimy analogicznie.

2. Jednoznaczność.
Przypuśćmy, że dla pewnych liczb całkowitych \(\displaystyle{ q, r}\) oraz \(\displaystyle{ q', r'}\) zachodzi:
\(\displaystyle{ \begin{cases}n = qd+r, \ 0 \le r < |d|\\ n=q'd + r', \ 0 \le r'<|d|.\end{cases}}\)
Wówczas \(\displaystyle{ qd+r=q'd+r',}\) skąd \(\displaystyle{ (q-q')d=r'-r.}\)

Przypuśćmy, że \(\displaystyle{ r \neq r'.}\) Bez straty ogólności możemy założyć, że \(\displaystyle{ r < r'.}\)

Z naszego przypuszczenia wynika, że \(\displaystyle{ |r'-r|<|d|.}\) W przeciwnym razie bowiem mielibyśmy \(\displaystyle{ r'-r=|r'-r| \ge |d|,}\) skąd \(\displaystyle{ r' \ge |d| + r \ge |d|}\), wbrew założeniu.

Zatem \(\displaystyle{ 0<r'-r<|d|}\), czyli \(\displaystyle{ 0<(q-q')d<|d|,}\) skąd wnosimy, że \(\displaystyle{ |(q-q')d|<|d|,}\) czyli \(\displaystyle{ |q-q'| \cdot |d| < |d|.}\) Ponieważ \(\displaystyle{ |d| > 0}\), to dzieląc obie strony nierówności przez tę liczbę wnioskujemy, że \(\displaystyle{ |q-q'|<1}\). Ale przecież \(\displaystyle{ |q-q'|}\) jest liczbą naturalną, co oznacza, że \(\displaystyle{ |q-q'|=0}\) i w konsekwencji \(\displaystyle{ q=q'}\).

Oczywiście \(\displaystyle{ q=q'}\) pociąga za sobą, że również \(\displaystyle{ r=r'}\), co jest wbrew przypuszczeniu.

Zatem musi być \(\displaystyle{ r=r'}\), a stąd wynika, jak łatwo zauważyć, że \(\displaystyle{ q=q'}\) - c.n.d.

Proszę o sprawdzenie również tego dowodu.

[InYourHead]

Dziękuję za dowód, czegoś takiego właśnie szukałem

[michalplat]

Jest sens rozpatrywać zarówno przypadek \(\displaystyle{ a \le 0 \wedge b>0}\), oraz \(\displaystyle{ a \ge 0 \wedge b<0}\) ? A jeśli tak to jaki ?