Twierdzenie o dzieleniu z resztą

Z podziału dziesięciu jabłek (dzielna) na trzy grupy (iloraz) po trzy jabłka (dzielnik) pozostaje jedno jabłko (reszta), nie tworzące pełnej (trójelementowej) grupy jabłek.

Twierdzenie o dzieleniu z resztą – twierdzenie matematyczne mówiące o możliwości przedstawienia danej liczby całkowitej, dzielnej, w postaci sumy iloczynu ilorazu przez (niezerowy) dzielnik oraz reszty. Innymi słowy twierdzenie mówi, ile razy (iloraz) dana liczba (dzielnik) mieści się w całości w innej (dzielna) oraz jaka część (reszta) tej liczby nie została wydzielona. Stosuje się także skróconą wersję nazwy: twierdzenie o dzieleniu.

Twierdzenie to znajduje zastosowanie m.in. w znajdowaniu największego wspólnego dzielnika dwóch liczb całkowitych, a przy tym uogólnia się wprost na dziedziny ideałów głównych.

Twierdzenie

Dalej, o ile nie zostało zaznaczone inaczej, słowo „liczba” będzie oznaczać liczbę całkowitą. Dla danych liczb $a$ oraz $d \ne 0$ istnieją jednoznacznie wyznaczone liczby $q$ oraz $r,$ dla których zachodzi

$a = qd + r,$

przy czym $0 \leqslant r < |d|,$ gdzie $|d|$ oznacza wartość bezwzględną $d.$ Powyższe liczby mają swoje nazwy

• $q$ nazywa się ilorazem,
• $r$ nazywa się resztą,
• $d$ nazywa się dzielnikiem,
• $a$ nazywa się dzielną.

Przykłady

• Jeśli $a = 7$ oraz $d = 3,$ to $q = 2$ oraz $r = 1,$ gdyż $7 = 2 \cdot 3 + 1.$
• Jeśli $a = 7$ oraz $d = -3,$ to $q = -2$ oraz $r = 1,$ gdyż $7 = (-2) \cdot (-3) + 1.$
• Jeśli $a = -7$ oraz $d = 3,$ to $q = -3$ oraz $r = 2,$ gdyż $-7 = (-3) \cdot 3 + 2.$
• Jeśli $a = -7$ oraz $d = -3,$ to $q = 3$ oraz $r = 2,$ gdyż $-7 = 3 \cdot (-3) + 2.$

Dowód

Dowód składa się z dwóch części: pierwsza mówi o istnieniu $q$ oraz $r,$ druga – o ich jednoznaczności.

Istnienie

Niech dany będzie zbiór $S$ liczb postaci $a - nd,$ gdzie $n$ jest dowolną liczbą, tzn.

$S = \{a - nd\colon n \in \mathbb Z\}.$

Zbiór ten zawiera przynajmniej jedną nieujemną liczbę całkowitą; są dwa przypadki:

• jeśli $a \geqslant 0,$ to można przyjąć $n = 0;$
• jeśli $a < 0,$ to wystarczy wziąć $n = ad.$

W obu przypadkach $a - nd$ jest liczbą nieujemną, zatem $S$ zawiera przynajmniej jedną liczbę nieujemną. W ten sposób, z zasady dobrego uporządkowania, zbiór $S$ musi zawierać najmniejszą nieujemną liczbę $r,$ przy czym z definicji $r = a - nd$ dla pewnego $n.$ Wspomniane $n$ będzie oznaczane dalej literą $q.$ W związku z tym, porządkując równanie, uzyskuje się $a = qd + r.$

Pozostaje wykazać, że $0 \leqslant r < |d|.$ Pierwsza nierówność wynika z wyboru $r$ jako liczby nieujemnej. Aby pokazać drugą (ostrą) nierówność, przypuśćmy, że $r \geqslant |d|.$ Ponieważ wówczas $d \ne 0$ oraz $r > 0,$ to należy rozpatrzeć są dwa przypadki ze względu na znak $d\colon$

• Jeżeli $d > 0,$ to $r \geqslant d$ pociąga, iż $a - qd \geqslant d,$ co oznacza, że $a - qd \geqslant 0$ i w dalszej kolejności $a - (q + 1)d \geqslant 0,$ co oznacza, że $a - (q + 1)d$ należy do $S,$ a ponieważ $a - (q + 1)d = r - d,$ przy czym $d > 0,$ to $a - (q + 1)d < r,$ co przeczy założeniu, że $r$ było najmniejszą liczbą nieujemną należącą do $S.$
• Jeżeli $d < 0,$ to $r \geqslant -d$ oznacza, że $a - qd \geqslant -d,$ co daje $a - qd + d \geqslant 0$ i dalej $a - (q - 1)d \geqslant 0,$ więc $a - (q - 1)d$ należy do $S,$ a ponieważ $a - (q - 1)d = r + d,$ gdzie $d < 0,$ to $a - (q - 1)d < r,$ co stanowi sprzeczność z założeniem, że $r$ był najmniejszym nieujemnym elementem $S.$

W ten sposób dowiedziono, że $r > 0$ nie była w istocie najmniejszą nieujemną liczbą ze zbioru $S;$ sprzeczność ta oznacza, że musi być $r < |d|,$ co kończy dowód istnienia $q$ oraz $r.$

Jednoznaczność

Załóżmy istnienie takich liczb $q, q', r, r',$ gdzie $0 \leqslant r, r' < |d|,$ że $a = dq + r$ oraz $a = dq' + r'.$ Bez straty ogólności można założyć, że $q \leqslant q'$ (jeśli jest odwrotnie, to liczby te można zamienić rolami).

Odejmując oba równania stronami otrzymuje się

$d(q - q') = (r - r').$

Jeżeli $d > 0,$ to $r' \geqslant r$ oraz $r < d \leqslant d + r',$ a stąd $(r - r') < d.$ Podobnie dla $d < 0$ jest $r \leqslant r'$ oraz $r < -d \leqslant -d + r,$ co daje $-(r - r') < -d.$ Łącząc obie te nierówności w jedną uzyskuje się $|r - r'| < |d|.$

Wyjściowe równanie zapewnia, że $|d|$ jest dzielnikiem $|r - r'|,$ stąd $|d| \leqslant |r - r'|$ lub $|r - r'| = 0.$ Ponieważ dowiedziono już, że $|r - r'| < d,$ to z trychotomii można wnioskować, że pierwsza możliwość nie może zachodzić, dlatego $r = r'.$

Podstawiając ten wynik do dwóch pierwszych równań daje $dq = dq',$ a ponieważ $d \ne 0,$ to musi być $q = q',$ co dowodzi jednoznaczności.

Uogólnienia

Jeśli $a$ oraz $d \ne 0$ są liczbami rzeczywistymi, to wykonalne jest dzielenie $a$ przez $d$ bez reszty, przy czym iloraz jest inną liczbą rzeczywistą. Jeśli jednak ograniczyć iloraz tak, by był liczbą całkowitą, to pojęcie reszty nadal okazuje się niezbędne; zachodzi wtedy odpowiednik twierdzenia o dzieleniu: istnieje jednoznacznie wyznaczony iloraz całkowity $q$ oraz jednoznacznie wyznaczona reszta rzeczywista $r,$ które spełniają $a = qd + r,$ gdzie $0 \leqslant r < |d|;$ wówczas

$r = a - d \left\lfloor\tfrac{a}{d}\right\rfloor,$

gdzie $\lfloor \cdot \rfloor$ oznacza część całkowitą.

Powyższe rozszerzenie pojęcia reszty na liczby rzeczywiste nie ma wielkiego znaczenia teoretycznego w matematyce, jednak definicję tę stosuje się w wielu językach programowania oraz systemach obliczeniowych; liczbę $r$ wyznaczoną w powyższy sposób oznacza się czasami $a\ \bmod\ d,$ przy czym przypadek szczególny $a\ \bmod\ 1 = a - \lfloor a\rfloor$ odpowiada mantysie $\{a\}.$

Definicja reszty (w przypadku całkowitym, jak i rzeczywistym), oprócz równości $a = qd + r,$ zawiera również nierówność $0 \leqslant r < |d|$ zapewniającą jej jednoznaczność. Czasem spotyka się również nierówność $-|d| < r \leqslant 0,$ przy czym ten wybór sprawia, że reszta ma ten sam znak, co dzielnik (w przeciwieństwie do poprzedniego, w którym reszta ma znak dzielnej); z tego powodu należy mieć na uwadze konwencję stosowaną w danym języku programowania, np. C99 i Pascal zwracają resztę o tym samym znaku co dzielna (wcześniej w języku C zależało to od implementacji), z kolei Perl oraz Python dają resztę o tym samym znaku, co dzielnik; język Ada umożliwia wybranie znaku reszty.

Z punktu widzenia teorii wybór między powyższymi nierównościami jest jednak kwestią gustu, gdyż dowolny warunek postaci $x < r \leqslant x + |d|,$ czy też $x \leqslant r < x + |d|,$ gdzie $x$ jest stałą, gwarantuje jednoznaczność reszty. Zbiór reszt $\bigl\{0, 1, \dots, |d| - 1\bigr\}$ jest tak wybrany ze względu na jego wygodę: znak reszty jest zgodny ze znakiem dzielnika (co można zaobserwować w Przykładach); powyższe, w języku arytmetyki modularnej, oznacza, że zamiast wspomnianego zbioru można wykorzystać dowolny zbiór liczb całkowitych przystających do liczb z tego zbioru, a w języku teorii grup, iż każdy element tego zbioru powinien być reprezentantem innej warstwy (zob. grupa ilorazowa).

Zobacz też

• arytmetyka reszt
• chińskie twierdzenie o resztach
• kongruencja