Twierdzenie o dzieleniu z resztą

Ten artykuł od 2010-09 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła, najlepiej w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 ${\displaystyle a}$ oraz ${\displaystyle d\neq 0}$ istnieją jednoznacznie wyznaczone liczby ${\displaystyle q}$ oraz ${\displaystyle r,}$ dla których zachodzi

${\displaystyle a=qd+r,}$

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

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

Przykłady

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

Dowód

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

Istnienie

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

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

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

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

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

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

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

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

Jednoznaczność

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

Odejmując oba równania stronami otrzymuje się

${\displaystyle d(q-q')=(r-r').}$

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

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

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

Uogólnienia

Jeśli ${\displaystyle a}$ oraz ${\displaystyle d\neq 0}$ są liczbami rzeczywistymi, to wykonalne jest dzielenie ${\displaystyle a}$ przez ${\displaystyle 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 ${\displaystyle q}$ oraz jednoznacznie wyznaczona reszta rzeczywista ${\displaystyle r,}$ które spełniają ${\displaystyle a=qd+r,}$ gdzie ${\displaystyle 0\leqslant r<|d|;}$ wówczas

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

gdzie ${\displaystyle \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ę ${\displaystyle r}$ wyznaczoną w powyższy sposób oznacza się czasami ${\displaystyle a\ {\bmod {\ }}d,}$ przy czym przypadek szczególny ${\displaystyle a\ {\bmod {\ }}1=a-\lfloor a\rfloor }$ odpowiada mantysie ${\displaystyle \{a\}.}$

Definicja reszty (w przypadku całkowitym, jak i rzeczywistym), oprócz równości ${\displaystyle a=qd+r,}$ zawiera również nierówność ${\displaystyle 0\leqslant r<|d|}$ zapewniającą jej jednoznaczność. Czasem spotyka się również nierówność ${\displaystyle -|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 ${\displaystyle x<r\leqslant x+|d|,}$ czy też ${\displaystyle x\leqslant r<x+|d|,}$ gdzie ${\displaystyle x}$ jest stałą, gwarantuje jednoznaczność reszty. Zbiór reszt ${\displaystyle {\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