Деление с остатком

Определение 6. Число a делится на число b с остатком r, если его можно представить в виде:

a = q ∙ b + r,

где q и r – целые числа, причем 0 ≤ |r| < b. Равенство r = 0 в таком представлении равносильно тому, что число a делится на b.

Замечание. Если же мы рассматриваем деление с остатком лишь на множестве натуральных чисел, как было условлено ранее, то можем снять модуль в неравенстве для остатка: 0 ≤ r < b.

С учетом введенного определения и замечания, необходимо заметить следующий важный факт:

Ключевой факт. Число a при делении на число b может давать ровно b возможных вариантов остатков. То есть r = 0, 1, 2, …, b – 1.

Имеют место два важнейших утверждения.

Утверждение 1. Сумма любых двух натуральных чисел и сумма их остатков имеют одинаковые остатки при делении на некоторое число.

Утверждение 2. Произведение любых двух натуральных чисел и произведение их остатков имеют одинаковые остатки при делении на некоторое число.

Доказательство. Пусть рассматриваются два натуральных числа n₁ и n₂, которые мы делим на число m. Тогда, согласно с определением 6,

n₁ = q₁ ∙ m + r₁

n₂ = q₂ ∙ m + r₂,

где q₁, q₂ – целые числа, а r₁, r₂ – соответствующие остатки.

Перемножив числа n₁ и n₂, получим

n₁n₂ = (q₁∙ m + r₁)(q₂ ∙ m + r₂) =

= q₁q₂ ∙ m² + q₁r₂ ∙ m + q₂r₁ ∙ m + r₁r₂ =

= m ∙ (q₁q₂m + q₁r₂ + q₂r₁) + r₁r₂.

Число m ∙ (q₁q₂m + q₁r₂ + q₂r₁), очевидно, делится на m. Следовательно, остаток при делении числа n₁n₂ на m, совпадает с остатком при делении числа r₁r₂ на m.

Упражнение. Докажите утверждение 1.

Определение 7. Два числа a и b сравнимы по модулю натурального числа m (или равноостаточны при делении на m), если при делении на m они дают одинаковые остатки. Число m в таком случае называется модулем сравнения.

Обозначение. Если числа a и b сравнимы по модулю натурального числа m, то пишут, что a ≡ b (mod m).

Пример. Числа 32 и 18 сравнимы по модулю 7, поскольку 32 = 7 ∙ 4 + 4 и 18 = 7 ∙ 2 + 4. То есть 18 ≡ 32 (mod 7).

Целью двух наших следующих лекции наконец-то будет преимущественно решение задач. Лишь теперь, когда мы четко ввели необходимые определения, мы можем приступить непосредственно к решению типичных задач на делимость.

Задача 1. Произведение двух натуральных чисел, каждое из которых не делится нацело на 10, равно 1000. Найдите их сумму.

В первую очередь, давайте с Вами вспомним, что означает, что одно число делится на другое. Затем, если помните, совсем недавно мы акцентировали внимание на том, что свойства делимости числа практически полностью определяются его разложением на простые сомножители. Вот эти соображения мы с Вами наконец-то и применим!

Решение задачи 1. Поскольку произведение двух натуральных чисел равно 1000 = 2³ ∙ 5³, то каждое из чисел в своем разложении может содержать лишь двойки и пятерки. Заметим, что оба этих множителя не могут присутствовать в разложении одного числа, иначе оно будет делиться на 10. Следовательно, одно из чисел равно 5³, а другое – 2³. Тогда их сумма равна 5³ + 2³ = 125 + 8 = 133.

Заметьте, что именно благодаря составленному нами разложению на простые сомножители числа 1000, предложенная задача в один момент оказалась решенной.

Теперь давайте вспомним о том, что такое наибольший общий делитель (НОД) и наименьшее общее кратное (НОК). Имеет место следующее важнейшее утверждение.

Утверждение. Для любых натуральных чисел a и b выполняется равенство:

НОД (a, b) ∙ НОК (a, b) = ab.

Доказательство. Пусть НОД (a, b) = m. Тогда, согласно с введенным нами в предыдущей лекции определением наибольшего общего делителя, имеют место равенства:

a = a₁m,

b = b₁m,

где числа a₁ и b₁ взаимно просты – НОД (a₁, b₁) = 1.

Тогда из определения наименьшего общего кратного следует, что НОК (a, b) = a₁b₁m.

Следовательно, НОД (a, b) ∙ НОК (a, b) = m ∙ a₁b₁m = a₁m ∙ b₁m = ab.

Ключевой момент. При решении задач на НОД и НОК бывает полезно обозначить НОД двух чисел некоторой неизвестной, а затем выразить эти числа и их НОК через эту неизвестную.

В доказательстве утверждения мы обозначили НОД чисел a и b некоторой неизвестной m, а затем выразили a, b и их НОК через эту неизвестную m.

Не бойтесь вводить неизвестные! Впоследствии от них всегда можно избавиться, если окажется, что они каким-либо образом выражаются через другие введенные ранее неизвестные либо же (что тоже бывает) косвенным образом известны из условия задачи.

Рассмотрим еще один пример применения подобных рассуждений.

Задача 2 (окружной этап Всероссийской математической олимпиады): Натуральные числа a и b таковы, что НОД (a, b) + НОК (a, b) = a + b.

Докажите, что одно из чисел a или b делится на другое.

Решение. Пусть НОД (a, b) = m. Тогда a = a₁m, b = b₁m, где НОД (a₁, b₁) = 1. Тогда НОК (a, b) = a₁b₁m. По условию НОД (a, b) + НОК (a, b) = a + b. Преобразуем данное уравнение в соответствии с введенными нами обозначениями.

m + a₁b₁m = a₁m + b₁m;

m(1 + a₁b₁) = m(a₁ + b₁).

Поскольку m – число, не меньшее единицы, то можем сократить на него обе части уравнения.

1 + a₁b₁ = a₁ + b₁;

1 + a₁b₁ – a₁ – b₁ = 0;

(1 – a₁) – b₁(1 – a₁) = 0;

(1 – a₁)(1 – b₁) = 0.

Следовательно, хотя бы одно из чисел a₁ и b₁ равно единице. В случае, если a₁ = 1, a = m и тогда b, очевидно, делится на a (из определения). В случае, если b₁ = 1, получаем b = m и, следовательно, a делится на b.