Celem tego rodziału będzie zaznajomienie czytelnika z podstawowymi wynikami teorii liczb, które są interesujące nie tylko same w sobie, ale znajdą również zastosowanie w dalszych rozdziałach i niejednokrotnie będą motywacją do wprowadzenia nowych pojęć (i badania ich własności).
Uwaga 2.1.2 ( własności podzielności w \(\Z \)). Niech \(a, b, c, m, n\in \Z \). Wtedy:
(a) \(1|a\), \(a|0\),
(b) jeśli \(0|a\), to \(a=0\),
(c) relacja podzielności na \(\Z ^\star \) jest zwrotna i przechodnia,
(d) \((b|a \ i \ a|b)\) wtedy i tylko wtedy, gdy \(|a|=|b|\),
(e) jeśli \(c|a\), \(c|b\), to \(c|(am+nb)\),
(f) jeśli \(a|b\) i \(b\ne 0\), to \(1\leqslant |a|\leqslant |b|\).
Przedstawimy poniżej dwie wersje twierdzenia o algorytmie dzielenia z resztą w zbiorze liczb całkowitych. Pierwsza z tych wersji (wersja A) stanowi przygotowanie do przyszłego uogólnienia omawianej własności do bardziej abstrakcyjnej sytuacji pierścienia euklidesowego (por. odnośnik). Druga wersja (wersja B) jest znana szerzej i szczególnie wygodna w zastosowaniach.
Potraktujemy to twierdzenie jako konsekwencję wspomnianego wyżej, ogólniejszego rezultatu.
Twierdzenie 2.1.4 ( algorytm dzielenia z resztą - wersja B). Niech \(a, b\in \Z \) i załóżmy, że \(b\ne 0\). Wtedy:
(\(\bullet \)) istnieje dokładnie jedna taka para \((q,r)\in \Z \times \Z \), że:
(1) \(a=bq+r\), (2) \(0\leqslant r<|b|\).
(\(\bullet \)) jeśli dodatkowo \(b\nmid a\), to istnieją dokładnie dwie pary \((q,r)\) takie, że
(1) \(a=bq+r\), (2) \(|r|<|b|\).
Dowód. Udowodnimy pierwszą część twierdzenia 2.1.4 (wynika z niej natychmiast tw. 2.1.3).
Istnienie reszty. Niech \(S:=\{a-kb, \ k\in \Z , \ a-kb\geqslant 0\}\) - jest to niepusty podzbiór \(\N _0\), wobec tego ma on element najmniejszy, który oznaczymy jako \(r\). Element ten jest postaci \(r=a-qb\) dla pewnego \(q\) całkowitego i z jego określenia widzimy, że spełniona jest nierówność \(0\leqslant r\) oraz \(a=qb+r\).
Pozostaje jedynie pytanie, czy \(r<|b|\)? Udowodnimy tę część niewprost. Gdyby \(r\geqslant |b|\), to \(r-|b|\geqslant 0\) oraz \(r-|b|=a-qb-|b|=a-(q+sgn(b))b\), więc \(r-|b|\in S\) oraz \(r-|b|<r\), (skoro \(b\ne 0\), to \(|b|\geq 1\)). Dostajemy sprzeczność z wyborem \(r\).
Jednoznaczność reszty nieujemnej. Dla dowodu niewprost załóżmy, że \(a=bq_1+r_1=bq_2+r_2\), \(0\leqslant r_1<|b|\), \(0\leqslant r_2<|b|\). Jeśli \(r_1<r_2\), to oczywiście \(q_1-q_2\ne 0\). Otrzymujemy zatem, że \(b(q_1-q_2)=r_2-r_1\) i w konsekwencji \(|b|\leqslant |b||q_1-q_2|=|r_2-r_1|=(r_2-r_1)<|b|\), co prowadzi do sprzeczności. W analogiczny sposób rozumujemy w przypadku, gdy \(r_{2}<r_{1}\). □
Zachęcamy do udowodnienia we własnym zakresie drugiej części twierdzenia 2.1.4.