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

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

$a=qd+r$ oraz $0⩽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:n\in \mathbb{Z}\}.$

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

• jeśli $a⩾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⩽r<|d|.$ Pierwsza nierówność wynika z wyboru $r$ jako liczby nieujemnej. Aby pokazać drugą (ostrą) nierówność, przypuśćmy, że $r⩾|d|.$ Ponieważ wówczas $d\ne 0$ oraz $r>0,$ to należy rozpatrzyć są dwa przypadki ze względu na znak $d:$

• Jeżeli $d>0,$ to $r⩾d$ pociąga, iż $a-qd⩾d,$ co oznacza, że $a-qd⩾0$ i w dalszej kolejności $a-(q+1)d⩾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⩾-d$ oznacza, że $a-qd⩾-d,$ co daje $a-qd+d⩾0$ i dalej $a-(q-1)d⩾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^{\prime },r,r^{\prime },$ gdzie $0⩽r,r^{\prime }<|d|,$ że $a=dq+r$ oraz $a=d{q}^{\prime }+r^{\prime }.$ Bez straty ogólności można założyć, że $q⩽q^{\prime }$ (jeśli jest odwrotnie, to liczby te można zamienić rolami).

Odejmując oba równania stronami otrzymuje się

$d(q-q^{\prime })=(r-r^{\prime }).$

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

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

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

Uogólnienia

Szablon:Zobacz też 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⩽r<|d|;$ wówczas

$r=a-d\lfloor \frac{a}{d}\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 $amodd,$ przy czym przypadek szczególny $amod1=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⩽r<|d|$ zapewniającą jej jednoznaczność. Czasem spotyka się również nierówność $-|d|<r⩽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⩽x+|d|,$ czy też $x⩽r<x+|d|,$ gdzie $x$ jest stałą, gwarantuje jednoznaczność reszty. Zbiór reszt $\{0,1,\dots ,|d|-1\}$ 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

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

Szablon:Otwarty dostęp 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.