Wikipedia

Twierdzenie o dzieleniu z resztą

twierdzenie matematyczne

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[1] edytuj

Jeżeli   i   są liczbami całkowitymi oraz  , to istnieje dokładnie jedna taka para liczb całkowitych   i  , że

  oraz  

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 edytuj

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

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

Istnienie edytuj

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ść edytuj

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 edytuj

Zobacz też: modulo.

Jeśli   oraz   są 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ż edytuj

Przypisy edytuj

  1. ↑ Adam Neugebauer, Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2020 (Matematyka olimpijska), s. 20, ISBN 978-83-7267-710-5 (pol.).

Linki zewnętrzne edytuj

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

Źródło: „https://pl.wikipedia.org/w/index.php?title=Twierdzenie_o_dzieleniu_z_resztą&oldid=72744333”