Задачи на делимость решают двумя инструментами: признаками делимости, которые позволяют судить о делимости по цифрам числа, и арифметикой остатков, где вместо самих чисел следят только за их остатками при делении на выбранное число.
По сути это один инструмент: признак делимости на 9 — наблюдение, что число и сумма его цифр дают одинаковый остаток при делении на 9. Ниже — как устроены признаки, как считать с остатками и пять задач из Математического праздника, Московской олимпиады и заключительного этапа Всероссийской олимпиады, от седьмого класса до доказательства делимости на 27.
Признаки делимости и почему они работают
Запишем число через его цифры. Например, . Все признаки получаются из того, какой остаток дают степени десятки при делении на нужное число.
На 2, 5 и 10. Число 10 делится на 2 и на 5, значит, всё, кроме последней цифры, на них делится. Остаётся проверить последнюю цифру: чётная — делится на 2, 0 или 5 — делится на 5, ноль — на 10.
На 4 и 25, на 8 и 125. , поэтому сотни, тысячи и все старшие разряды делятся на 4 и на 25 — смотрят на число из двух последних цифр. У числа 1 000 316 это 16, оно кратно 4, значит, и всё число кратно 4. Для 8 и 125 так же работают три последние цифры, потому что .
На 3 и 9. Здесь важно, что , а , и так далее. Каждая степень десятки при делении на 9 даёт остаток 1. Поэтому
Первые три слагаемых делятся на 9, значит, у числа 2754 и у суммы его цифр один и тот же остаток при делении на 9. Это сильнее обычной формулировки признака: по сумме цифр можно найти не только «делится или нет», но и сам остаток. Число 12 345 678 с суммой цифр 36 делится на 9, а число из 300 единиц даёт остаток 3 — это понадобится в задаче 2.
На 11. , поэтому при делении на 11 десятка даёт остаток (то есть 10), сотня — остаток , тысяча — снова . Отсюда признак: сложите цифры через одну со знаками «плюс» и «минус», начиная с последней. У числа 2728 получается , значит, делится на 11 (это ).
На составные числа. Если число раскладывается на взаимно простые множители, проверяют каждый. На 6 — делимость на 2 и на 3, на 12 — на 3 и на 4, на 45 — на 5 и на 9. Пары 2 и 6 для числа 12 недостаточно: 6 делится и на 2, и на 6, но не на 12.
Арифметика остатков простыми словами
Говорят, что сравнимо с по модулю , и пишут , если и дают одинаковые остатки при делении на . Это то же самое, что «разность делится на ». Например, и .
Главное свойство: в сумме, разности и произведении любое число можно заменить на его остаток, и остаток результата не изменится. Если и по модулю , то , и .
Так считается остаток огромных степеней. Найдём остаток при делении на 3. Поскольку , получаем . Остаток равен 1, и выписывать 31-значное число не пришлось.
Делить сравнения нельзя без оговорок: , но не сравнимо с по модулю 6. Сократить на число можно, только если оно взаимно просто с модулем.
Второе применение — короткие таблицы остатков. Квадрат целого числа при делении на 3 даёт только остатки 0 и 1, при делении на 9 — только 0, 1, 4 и 7. Если по условию получается квадрат с остатком 2 по модулю 3, задача решена. Тот же приём для уравнений, где ищут целые решения, подробно разобран в статье об уравнениях в целых числах.
- Найдите модульпо виду задачи: цифры числа подсказывают 9 или 11, квадраты — 3, 4, 8 или 9, конкретное число в условии — его простые делители
- Перейдите к остаткамзамените каждое число и выражение остатком и упростите
- Переберите случаиостатков конечное число, обычно не больше девяти
- Сделайте выводразные остатки у двух частей — равенство невозможно; одинаковые во всех случаях — делимость доказана
Задача 1: простое число и сумма цифр
Ваня задумал простое трёхзначное число, все цифры которого различны. На какую цифру оно может оканчиваться, если его последняя цифра равна сумме первых двух?
Показать решение ↓Скрыть решение ↑
Решение
Обозначим цифры , , , где . Первая цифра не меньше 1, поэтому . Если , то и , число равно 101 — у него повторяется цифра 1, это запрещено.
Трёхзначное простое число не может оканчиваться чётной цифрой — иначе оно делилось бы на 2 и было бы больше 2. Не может оно оканчиваться и цифрой 5 — делилось бы на 5. Остались варианты , и .
Сумма всех цифр равна . При она равна 6, при — 18. В обоих случаях сумма цифр делится на 3, значит, и число делится на 3 и не может быть простым.
Цифра 7 действительно встречается: число 167 простое, его цифры различны и . Подходят также 257, 347 и 617.
Источник задачи: XV Математический праздник, 15 февраля 2004 года, 7 класс, задача 1 — условие — официальный архив Математического праздника; решение — problems.ru, задача 103898
Математический праздник проводят для 6 и 7 классов, и задачи на признаки делимости там встречаются среди первых, самых доступных. Что это за олимпиада и как в ней участвовать, рассказано на странице о Математическом празднике.
Задача 2: число из единиц и нулей
Доказать, что число, состоящее из 300 единиц и некоторого количества нулей, не является точным квадратом.
Показать решение ↓Скрыть решение ↑
Решение
Сумма цифр такого числа равна 300, сколько бы нулей в нём ни было и где бы они ни стояли. Сумма 300 делится на 3, значит, по признаку делимости и само число делится на 3. А , поэтому при делении на 9 число даёт остаток 3 и на 9 не делится.
Предположим, что это число равно . Тогда делится на 3. Число 3 простое, поэтому если делит , то 3 делит . Но тогда и делится на 9 — противоречие.
То же видно из таблицы: квадраты по модулю 9 дают остатки 0, 1, 4 и 7, остатка 3 среди них нет.
Источник задачи: XXIII Московская математическая олимпиада, 1960 год, 8 класс, первый тур, задача 1 — условие и решение — problems.ru, архив задач МЦНМО
Задача 3: семь жетонов
Имеются семь жетонов с цифрами 1, 2, 3, 4, 5, 6, 7. Докажите, что ни одно семизначное число, составленное посредством этих жетонов, не делится на другое.
Показать решение ↓Скрыть решение ↑
Решение
Во всех таких числах одни и те же цифры, только в разном порядке. Сумма цифр у каждого равна , а . Значит, по признаку делимости каждое такое число даёт остаток 1 при делении на 9.
Пусть , где и — два разных числа из жетонов, — натуральное. Так как , то . Оценим сверху: самое большое число из жетонов — 7 654 321, самое маленькое — 1 234 567, а . Значит, .
Теперь перейдём к остаткам по модулю 9. Из и получаем , то есть делится на 9. При число лежит от 1 до 5 и на 9 не делится. Противоречие.
Источник задачи: XV Московская математическая олимпиада, 1952 год, второй тур, 8 класс и 9 класс, задача 3 — условие и решение — problems.ru, архив задач МЦНМО
Решение держится на двух шагах: остаток не зависит от порядка цифр, а оценка оставляет мало вариантов для . Без оценки рассуждение не закончено — при остаток по модулю 9 тоже был бы равен 1.
Задача 4: делимость на 2019
Найдите наименьшее натуральное число , для которого делится на .
Показать решение ↓Скрыть решение ↑
Решение
Разложим выражение и модуль на множители:
где 3 и 673 — простые числа.
Произведение делится на простое число 3, только если на 3 делится хотя бы один множитель. Множители и отличаются на 18, а 18 кратно 3, поэтому они дают одинаковый остаток при делении на 3. Значит, если на 3 делится один из них, то делятся оба.
Произведение делится и на простое число 673, поэтому один из множителей кратен 673. Этот множитель делится и на 3, и на 673, а значит, на .
Остаётся найти наименьшее натуральное , при котором или кратно 2019. Для это , для — . Меньшее из них — 2000.
Проверка: .
Источник задачи: LXXXII Московская математическая олимпиада, 17 марта 2019 года, 8 класс, задача 2 (автор Д. Шноль) — условие — официальный сайт ММО; решение — problems.ru, задача 66530
Если следить только за делимостью на 673, легко получить неверный ответ . Тогда , но не делится на 3, и тоже не делится. Проверка делимости на каждый простой множитель модуля обязательна.
Задача 5: делимость на 27
Целые числа , и таковы, что . Докажите, что число делится на 27.
Показать решение ↓Скрыть решение ↑
Решение
Посмотрим на остатки , , при делении на 3.
Все остатки разные. Тогда это остатки 0, 1 и 2 в каком-то порядке, и — правая часть делится на 3. А в левой части ни одна разность не делится на 3, так как в каждой паре остатки различны. Произведение трёх чисел, не делящихся на простое 3, на 3 не делится. Противоречие, этот случай невозможен.
Хотя бы два остатка совпадают. Тогда разность этих двух чисел делится на 3, и всё произведение делится на 3. Значит, тоже делится на 3. Пусть, например, , а . Тогда , откуда . Третий остаток совпадает с двумя первыми.
Итог. Все три остатка одинаковые, поэтому каждая из трёх разностей , , делится на 3, и их произведение делится на . Оно равно , что и требовалось.
Такие числа существуют: при , , левая часть равна , а правая .
Источник задачи: Всероссийская олимпиада по математике 1992/93 учебного года, заключительный этап, 9 класс, задача 5 (также 10 класс, задача 5), автор Н. Агаханов — условие и решение — problems.ru, архив задач МЦНМО
Где теряют баллы в задачах на делимость
Чаще всего — на потерянном случае. В задаче 1 легко забыть, что последняя цифра могла быть равна 1, а в задаче 5 — что остатки могут быть все разные. Перебор остатков ценен тем, что он полный: по модулю 3 случаев всего три, и каждый нужно закрыть.
Полезно подкрепить ответ примером: число 167 показывает, что последняя цифра 7 действительно возможна. В официальном разборе задачи 1 примеры не требовались, но в учебном решении они помогают проверить достижимость ответа.
Похожий перебор остатков работает и в задачах на чётность — это частный случай модуля 2. Разбор таких задач — в статье о чётности и инварианте.
Курс по теме
Тематические курсы в записи
Тематические курсы в записи разбирают отдельные олимпиадные методы, в том числе делимость и остатки, на задачах от простых до уровня ММО и ВсОШ.
Частые вопросы
С какого класса решают задачи на делимость?
Признаки делимости на 2, 3, 5, 9 и 10 проходят в школе в 5–6 классе, в зависимости от учебника. На олимпиадах они встречаются уже в 6–7 классе — задача 1 из этой статьи была на Математическом празднике для 7 класса. Сравнения по модулю удобно вводить в 7–8 классе, когда ученик уже уверенно делит с остатком.
Обязательно ли писать на олимпиаде значок сравнения?
Нет. Запись $a \equiv b \pmod m$ — сокращение для фразы «$a$ и $b$ дают одинаковые остатки при делении на $m$». Рассуждение можно записать словами. Важнее, чтобы был обоснован каждый переход и разобраны все остатки.
Есть ли признак делимости на 7?
Есть несколько. Один из них: отбросьте последнюю цифру и вычтите её удвоенное значение из оставшегося числа; исходное число делится на 7 тогда и только тогда, когда делится результат. Для 364: $36 - 2 \cdot 4 = 28$, а 28 делится на 7, значит, и 364 делится. Работает это потому, что $10a + b$ и $a - 2b$ одновременно делятся или не делятся на 7: умножение на $-2$ переводит первое во второе по модулю 7, а так как $-2$ и 7 взаимно просты, делимость сохраняется в обе стороны.
Как понять, по какому модулю смотреть остатки?
Подсказку даёт условие. Если речь о цифрах числа или их перестановке — пробуйте 9 и 11. Если есть квадраты — 3, 4, 8 или 9. Если в условии конкретное число вроде 2019 или 27 — разложите его на простые множители и проверяйте каждый.
Источники
- problems.ru — рубрика «Признаки делимости» — архив задач МЦНМО
- problems.ru — рубрика «Деление с остатком. Арифметика остатков» — архив задач МЦНМО
- Математический праздник 2004, условия и решения для 7 класса — официальный архив олимпиады
- problems.ru — Математический праздник 2004, 7 класс, задача 1 — условие и решение
- problems.ru — ММО 1960, 8 класс, задача 1 — условие и решение
- МЦНМО — ММО 1952, 8 класс, второй тур, задача 3 — условие и решение
- mmo.mccme.ru — LXXXII Московская математическая олимпиада, 2019 — официальный сборник ММО, условия и решения
- problems.ru — ММО 2019, 8 класс, задача 2 — условие и два решения
- problems.ru — Всероссийская олимпиада 1992/93, заключительный этап — задачи этапа
- problems.ru — ВсОШ 1993, 9 класс, задача 5 — условие и решение