Признаки делимости и равноостаточности

Признаки равноостаточности по модулям 9 и 3

Формулировка: Число и его сумма цифр дают одинаковые остатки при делении на 3/на 9. В частности, число делится на 3/на 9 тогда и только тогда, когда сумма цифр числа делится на 3/на 9.

1. Дано число 237581. Найдите его остаток при делении на 3.

Ответ. 2

Решение. Можно начать делить это число в столбик, но это не очень удобно. Вместо этого можно посчитать сумму цифр этого числа и найти ее остаток при делении на 3:

Почему это работает? Рассмотрим число 7581 и рассмотрим его десятичную запись:

Теперь «оденем очки по модулю 3» и смотрим только на числа 1000, 100 и 10. Тогда

Тогда мы увидим

Значит, само число и его сумма цифр дают одинаковые остатки при делении на 3. Для 9 тоже справедливо данное рассуждение, так как 9, 99 и 999 делятся на 9. Даже если число будет состоять из большего количества цифр, то числа 10000, 100000 и далее дают остаток 1 и при делении на 3, и при делении на 9.

Доказательство

Представим число в виде его десятичной записи Хотим доказать, что

Распишем

Несложно понять, что для любого целого неотрицательного верно, что и Это следует, например, из свойства сравнений про возведение в степень. Тогда

Признаки равноостаточности по модулям 8 и 4

Формулировка: Любое натуральное число сравнимо с числом, образованным его последними тремя цифрами, по модулю 8.

Доказательство

Представим число в виде его десятичной записи Хотим доказать, что

Это равносильно следующему

Последнее сравнение верно, так как любое число с тремя нулями на конце делится на 1000, а значит, и на 8.

Формулировка: Любое натуральное число сравнимо с числом, образованным его последними двумя цифрами, по модулю 4.

Доказательство этого признака аналогично предыдущему.

Признак делимости на 11

Формулировка: Число и его знакопеременная сумма цифр, посчитанная справа налево, дают одинаковые остатки при делении на 11.

Пусть дано число Тогда знакопеременная сумма справа налево равна

Почему работает признак? Рассмотрим десятичную запись числа 7851:

Теперь поймем, что в «очках по модулю 3» мы можем видеть не только остатки по модулю 3. Например, если мы захотим, то вместо 7 мы можем видеть 4, так как 7 и 4 дают одинаковые остатки при делении на 3. Таким образом, вместо числа 7 мы можем увидеть любое число, дающее такой же остаток при делении на 3, что и 7. Поймем, что такие числа располагаются на расстоянии, кратном 3, друг от друга. Тогда если к числу 7 мы прибавим или вычтем что-то, что делится на 3, мы получим число с таким же остатком.

Теперь посмотрим на число 10 в «очках по модулю 11». Если мы захотим видеть остатки, то увидим 10, но это неудобно. Поэтому мы вычтем 11 из 10, тогда мы увидим число которое дает такой же остаток при делении на 11, что и 10.

Посмотрим на число 100. Так как то 100 дает остаток 1 при делении на 11.

Посмотрим на число 1000. Заметим, что значит, 1000 дает остаток 10 при делении на 11, следовательно, вместо него мы может увидеть Тогда

Таким образом, если нас просят найти остаток от числа при делении на 11, мы можем искать остаток знакопеременной суммы цифр, записанной справа налево, то есть, например, для числа 7851 нужно вычислить сумму

Если же у нас спрашивают, делится ли число на 11, то можно просто посчитать разность суммы цифр на четных местах и суммы цифр на нечетных, то есть, например, для числа 27851 можно посчитать либо разность либо разность

Рассмотрим следующую задачу:

Назовем натуральное число хорошим, если в нем можно переставить цифры так, чтобы получившееся число делилось на 11.
а) Является ли число 1234 хорошим?
б) Является ли число 12345 хорошим?
в) Найти наибольшее хорошее число, состоящее из различных нечетных цифр.

Ответ. а) Да

б) Нет

в) 9753

Решение. Число делится на 11, если разность суммы цифр в нечетных разрядах и суммы цифр в четных делится на 11.

а) Чтобы число являлось хорошим, нам нужно переставить в нем цифры так, чтобы оно делилось на 11, то есть чтобы разность его суммы цифр в нечетных разрядах и суммы цифр в четных была кратна 11.

Попробуем сделать так, чтобы такая разность была равна 0. Заметим, что

Тогда можем составить число 1243, которое по признаку делимости будет кратно 11. Проверим:

б) Проверим изначальное число 12345:

Рассмотрим, какое значение может принимать разность суммы цифр в нечетных разрядах и суммы цифр в четных, если мы можем переставлять только цифры 1, 2, 3, 4 и 5. Пусть и — цифры 1, 2, 3, 4 и 5 в каком-то порядке. Тогда число делится на 11, если

Оценим значение этого выражения. Оно максимально, если на нечетных местах стоят три наибольшие цифры, а на четных — две наименьшие, то есть

Аналогично оценим минимальное значение. Если на нечетных местах стоят три наименьшие цифры, а на четных — две наибольшие, то разность минимальна, то есть

Значит, если из цифр 1, 2, 3, 4 и 5 можно составить число, которое делится на 11, то разность суммы цифр в нечетных разрядах и суммы цифр в четных должна быть равна 0.

Заметим, что среди цифр 1, 2, 3, 4 и 5 три нечетные цифры (1, 3 и 5) и две четные (2 и 4), значит, как бы мы ни складывали или как бы мы ни вычитали нечетные и четные цифры, главное то, что в нашем наборе нечетное количество нечетных цифр. Следовательно, в итоге

Значит, 12345 не является хорошим числом.

в) Докажем, что число, составленное из всех пяти нечетных цифр, не будет делиться на 11. Предположим обратное, пусть такое число можно составить. Тогда оно состоит из пяти различных нечетных цифр, то есть это число является некоторой перестановкой цифр 1, 3, 5, 7 и 9.

Пусть это число Тогда воспользуемся идеей из предыдущего пункта и оценим значение этого выражения:

Таким образом, если число делится на 11, то разность суммы его цифр на нечетных местах и суммы цифр на четных равна либо 0, либо 11.

Так как в этой разности участвуют только 5 нечетных цифр, то она всегда будет нечетной. Значит, если число делится на 11, то разность суммы его цифр на нечетных местах и суммы цифр на четных местах должна быть равна 11.

Пусть а Тогда а Значит, можем составить систему:

Заметим, что никогда не может быть равно 7, так как должно быть четным как сумма двух нечетных цифр. Тогда не существует числа, состоящего из всех пяти нечетных цифр, которое делится на 11.

Рассмотрим наибольшее четырехзначное число, состоящее из различных нечетных цифр. Это число 9753. Заметим, что

Значит, число 9753 является хорошим, так как число 9537 кратно 11.