Twierdzenie o dzieleniu z resztą

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.

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 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

Jeżeli $a$ i $d$ są liczbami całkowitymi oraz $d\neq 0$, to istnieje dokładnie jedna taka para liczb całkowitych $q$ i $r$, że

$a=qd+r$ oraz $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\neq 0$ oraz $r>0,$ to należy rozpatrzyć 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\neq 0,$ to musi być $q=q',$ co dowodzi jednoznaczności.

Uogólnienia

Jeśli $a$ oraz $d\neq 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

Linki zewnętrzne

• Dzielenie z resztą, Zintegrowana Platforma Edukacyjna, zpe.gov.pl [dostęp 2023-11-24].

Nagrania na YouTube [dostęp 2023-11-24]:

• Wstęp do dzielenia z resztą, kanał Khan Academy, 18 września 2014;
• Dzielenie z resztą. Podzielność liczb, kanał Wydawnictwa Nowa Era, 16 maja 2023.