Теорема о делении с остатком. Алгоритм Евклида

Основную роль во всей арифметике целых чисел играет теорема о делении с остатком.

Теорема 4.1. Для любого целого а и целого существуют и единственные целые q и r, такие что .

Замечание 4.3. Если то q называется неполным частным, а r – остатком от деления a на b.

Замечание 4.2. В частности, если , то и делится на .

Из теоремы 4.1 следует, что при фиксированном целом m > 0 любое целое число а можно представить в одном из следующих видов:

При этом если то будем иметь , если и

, если .

Примеры.

1.
Любое целое число можно представить в виде или .

2.
Любое целое число можно представить в виде или или .

Важным следствием из теоремы о делении с остатком является еще одно свойство делимости.

Теорема 4.4. Разность целых чисел а и b делится на натуральное число m в том и только в том случае, когда числа а и b при делении на m дают одинаковые остатки.

Замечание. Такие числа называют еще равноостаточными, или сравнимыми по модулю m.

На следующей теореме основан ещё один способ нахождения наибольшего общего делителя целых чисел.

Теорема 4.5. Пусть a и b – два целых числа, 0и , тогда .

Этот способ называется алгоритмом Евклида. Задача нахождения НОД чисел a и b сводится к более простой задаченахождения НОД b и r, . Если r = 0, то . Если же , то рассуждения повторяем, отправляясь от b и r. В результате получаем цепочку равенств: