|
|
 |
Условие
Доказать, что 4m − 4n делится на 3k+1 тогда и только тогда, когда m − n делится на 3k.
Решение
Пусть для определённости m > n. Число 4m − 4n = 4n(4m–n − 1) делится на 3k+1 тогда и только тогда, когда 4m–n − 1 делится на 3k+1. Докажем индукцией по k, что наименьшее натуральное число a, для которого 4a − 1 делится на 3k+1, равно 3k; при этом 4a − 1 не делится на 3k+2.
База (k = 1) проверяется непосредственно.
Шаг индукции. Предположим, что 4b − 1 делится на 3k+2. Тогда, в частности, 4b − 1 делится на 3k+1. Представим число b в виде b = 3kc + r, где
0 ≤ r < 3k. Тогда 4b ≡ 4r (mod 3k+1), поэтому r = 0. Таким образом, 4b − 1 = 43kc − 1 = (43k − 1)(43k(c–1) + 43k(c–2) + ... + 1).
По предположению индукции число 43k – 1 делится на 3k+1 и не делится на 3k+2. Поэтому 43k + 1 не делится на 3. Ясно, что 43k·2 + 43k + 1 делится на 3 и не делится на 9 (при делении на 9 это число даёт остаток 3), поэтому минимальное c = 3.
