Twierdzenia o podzielności liczb całkowitych

Mówimy że liczba całkowita a jest podzielna przez liczbę całkowitą b, przy czym b ≠ 0, jeśli istnieje liczba całkowita k taka, że a = k · b.

Zapisujemy wówczas b|a i mówimy, że liczba a jest podzielna (bez reszty) przez liczbę b.

W dalszej części liczby a, b, ... należą do zbioru liczb całkowitych, chyba, że jest określone inaczej.

Twierdzenie 1 (przechodniość)
Jeśli a|b i b|c to a|c.

Dowód
Z faktu a|b i b|c wynika, że istnieją liczby całkowite k₁, k₂ takie, że b = k₁ · a i c = k₂ · b.
Zatem c = (k₁ · k₂)a, co dowodzi, że a|c.
Twierdzenie to mówi, że dzielnik dzielnika pewnej liczby jest dzielnikiem tej liczby.

Twierdzenie 2
Jeśli a|b i b|c to a|b + c i a|b - c.

Dowód
Z faktu a|b i b|c wynika b = k₁ · a i c = k₂ · b, gdzie k₁ i k₂ to liczby całkowite.
Suma b + c = k₁a + k₂a = (k₁ + k₂)a jest podzielna przez a, ponieważ liczba k₁ + k₂ jest liczbą całkowitą.
Analogicznie różnica b - c = k₁a - k₂a = (k₁ - k₂)a jest podzielna przez a, ponieważ liczba k₁ - k₂ jest liczbą całkowitą.

Twierdzenie 3
Jeśli a|b i c|d to ac|bd

Dowód
Ze związków a|b i c|d wynika b = k₁ · a i d = k₂ · c, gdzie k₁ i k₂ to liczby całkowite.
Mnożymy stronami b = k₁ · a i d = k₂ · c i otrzymujemy bd = (k₁k₂)ac. Ponieważ k₁k₂ jest liczbą całkowitą, to ac|bd.

Twierdzenie 4
Jeżeli jeden składnik sumy a + b jest podzielny przez c, to suma a + b jest podzielna przez c wtedy i tylko wtedy, gdy drugi składnik tej sumy jest podzielny przez c.

Dowód
Niech c|a. Jeśli c|b, to na mocy tw. 2 zachodzi c|a + b.
W drugą stronę: jeśli c|a + b i c|a, to na podstawie tw. 2 zachodzi c|(a + b) - a, skąd c|b.

Lemat 1 (tw. Archimedesa)
Dla dowolnych liczb naturalnych a i b istnieje liczba naturalna n taka, że bn > a.
Twierdzenie to można rozszerzyć na liczby całkowite, gdzie dla liczb całkowitych a, b ≠ 0 istnieje taka liczba całkowita c, że |b|c > a, gdzie |b| jest wartością bezwzględną liczby b.

Twierdzenie 5
Dla liczb całkowitych a i b ≠ 0 istnieją takie liczby całkowite c, że |b|c + a jest liczbą naturalną

Dowód
Jeśli a ≥ 0, to istnieje takie c = 0, że |b|c + a jest liczbą naturalną.
Dla a < 0, na podstawie tw. Archimedesa (lemat 1) można dobrać taką liczbę całkowitą c, że |b|c ≥ -a, skąd wynika, że |b|c + a jest liczbą naturalną.

Twierdzenie 6 (tw. o dzieleniu z resztą)
Dla liczb całkowitych a i b ≠ 0 istnieje jedna i tylko jedna para para liczba całkowitych k i r taka, że a = k · b + r, gdzie 0 ≤ r < |b|

Dowód
Na mocy tw. 5 i zgodnie z zasadą minimum można dobrać liczbę całkowitą d taką, że liczba naturalna |b|d + a jest najmniejszą liczbą w zbiorze liczb naturalnych zbioru |b|c + a z tw. 5.
Niech |b|d + a = r, gdzie r ≥ 0.
Liczba r musi spełniać warunek r < |b|, bowiem gdyby liczba r ≥ |b|, to r > r - |b| ≥ 0.
Ale r - |b| = |b|d + a - |b| = a + |b|(d - 1) ≥ 0, skąd wynika, że istniałaby liczba a + |b|(d - 1) mniejsza od r, wbrew założeniu, że r jest liczbą najmniejszą zbioru.
Ponadto liczba r jest liczbą naturalną, więc ostatecznie spełnia warunek 0 ≤ r < |b|
Z równości |b|d + a = r wyznaczając a = -|b|d + r i podstawiając w miejsce d -k, gdy b > 0 i d = k oraz uwzględniając 0 ≤ r < |b| otrzymujemy a = k · b + r, przy czym 0 ≤ r < |b|

Ponieważ zbiór liczb całkowitych k takich, że zachodzi warunek kb ≤ a jest ograniczony od góry, więc istnieje jedna i tylko jedna liczba k taka, że kb ≤ a i (k + 1)b > a, liczba r = a - kb.

Zatem dla liczb całkowitych a i b istnieje rozkład liczby a na dwa składniki całkowite kb i r, przy czym r jest liczbą nieujemną mniejszą od bezwzględnej wartości liczby b.
Wyszukiwanie dla pary liczb a i b pary liczb k i r, gdzie 0 ≤ r < |b| nazywamy dzieleniem liczby a przez liczbę b (różną od zera). Liczbę k nazywamy ilorazem, r - resztą tego dzielenia.