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 oraz istnieją jednoznacznie wyznaczone liczby oraz dla których zachodzi

przy czym gdzie oznacza wartość bezwzględną Powyższe liczby mają swoje nazwy

  • nazywa się ilorazem,
  • nazywa się resztą,
  • nazywa się dzielnikiem,
  • nazywa się dzielną.

Przykłady

  • Jeśli oraz to oraz gdyż
  • Jeśli oraz to oraz gdyż
  • Jeśli oraz to oraz gdyż
  • Jeśli oraz to oraz gdyż

Dowód

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

Istnienie

Niech dany będzie zbiór liczb postaci gdzie jest dowolną liczbą, tzn.

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

  • jeśli to można przyjąć
  • jeśli to wystarczy wziąć

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

Pozostaje wykazać, że Pierwsza nierówność wynika z wyboru jako liczby nieujemnej. Aby pokazać drugą (ostrą) nierówność, przypuśćmy, że Ponieważ wówczas oraz to należy rozpatrzyć są dwa przypadki ze względu na znak

  • Jeżeli to pociąga, iż co oznacza, że i w dalszej kolejności co oznacza, że należy do a ponieważ przy czym to co przeczy założeniu, że było najmniejszą liczbą nieujemną należącą do
  • Jeżeli to oznacza, że co daje i dalej więc należy do a ponieważ gdzie to co stanowi sprzeczność z założeniem, że był najmniejszym nieujemnym elementem

W ten sposób dowiedziono, że nie była w istocie najmniejszą nieujemną liczbą ze zbioru sprzeczność ta oznacza, że musi być co kończy dowód istnienia oraz

Jednoznaczność

Załóżmy istnienie takich liczb gdzie że oraz Bez straty ogólności można założyć, że (jeśli jest odwrotnie, to liczby te można zamienić rolami).

Odejmując oba równania stronami otrzymuje się

Jeżeli to oraz a stąd Podobnie dla jest oraz co daje Łącząc obie te nierówności w jedną uzyskuje się

Wyjściowe równanie zapewnia, że jest dzielnikiem stąd lub Ponieważ dowiedziono już, że to z trychotomii można wnioskować, że pierwsza możliwość nie może zachodzić, dlatego

Podstawiając ten wynik do dwóch pierwszych równań daje a ponieważ to musi być co dowodzi jednoznaczności.

Uogólnienia

Jeśli oraz liczbami rzeczywistymi, to wykonalne jest dzielenie przez 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 oraz jednoznacznie wyznaczona reszta rzeczywista które spełniają gdzie wówczas

gdzie 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ę wyznaczoną w powyższy sposób oznacza się czasami przy czym przypadek szczególny odpowiada mantysie

Definicja reszty (w przypadku całkowitym, jak i rzeczywistym), oprócz równości zawiera również nierówność zapewniającą jej jednoznaczność. Czasem spotyka się również nierówność 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 czy też gdzie jest stałą, gwarantuje jednoznaczność reszty. Zbiór reszt 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ż

Media użyte na tej stronie

Divide10by3.svg
division: 10/3=3+1/3.