Ogólne twierdzenia dotyczące podzielności.

Podamy najpierw podstawowe fakty dotyczące teorii podzielności. Łatwe dowody tych twierdzeń znajdzie Czytelnik w książce W. Sierpińskiego Arytmetyka Teoretyczna, PWN, Warszawa 1966.

Niech będą liczbami całkowitymi. Jeśli istnieje taka liczba całkowita że to mówimy, że liczba jest wielokrotnością liczby albo że dzieli się przez (w terminologii szkolnej mówimy - dzieli się bez reszty), albo że liczba jest dzielnikiem liczby

 

Fakt ten zapisujemy symbolem

Fakt, że nie jest dzielnikiem będziemy zapisywać symbolem

Twierdzenie A.

Liczbę nazywamy wtedy resztą z dzielenia liczby przez

Zauważmy, że każdy niepusty zbiór liczb całkowitych, różny od posiada tylko skończoną ilość dzielników wspólnych, największy z takich dzielników nazywać będziemy największym wspólnym dzielnikiem liczb tego zbioru.

Największy wspólny dzielnik liczb całkowitych oznaczać będziemy symbolem

Znajdź

bo wspólnymi dzielnikami liczb są liczby

 

Najmniejszą liczbę naturalną, większą od zera, która jest wspólną wielokrotnością liczb całkowitych nazywamy najmniejszą wspólną wielokrotnością tych liczb i oznaczamy symbolem

Znajdźmy

bo   czyli 

Twierdzenie B.

Zauważ, że wspólną wielokrotnością liczb jest liczba A liczba Twierdzenie powyższe mówi, że każda wspólna wielokrotność podanych liczb jest w tym przypadku podzielna przez

Wniosek B 1.
Największy wspólny dzielnik liczb dowolnego niepustego zbioru liczb całkowitych różnych od zera jest podzielny przez każdy dzielnik wspólny liczb tego zbioru.

Uzasadnimy ten wniosek

Rzeczywiście, niech będzie dowolną liczbą rozważanego zbioru i niech będzie największym wspólnym dzielnikiem liczb tego zbioru, zaś - dowolnym wspólnym dzielnikiem liczb tego zbioru.

Zatem jest wspólną wielokrotnością a więc, zgodnie z Twierdzeniem B,

Czyli, wobec faktu, że jest dowolnie wybraną liczbą naszego zbioru, jest wspólnym dzielnikiem liczb rozważanego zbioru, zachodzi zatem nierówność]

Ale jako wspólna wielokrotność spełnia nierówność a więc zachodzi równość

Stąd i z definicji wspólnej wielokrotności mamy c.n.d.