Top.Mail.Ru
К содержанию

Чем можем помочь?

Открыть popup op Открыть popup admin

Задачи на делимость

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

Редакция блога «Олмат»11 минут чтения
√

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

По сути это один инструмент: признак делимости на 9 — наблюдение, что число и сумма его цифр дают одинаковый остаток при делении на 9. Ниже — как устроены признаки, как считать с остатками и пять задач из Математического праздника, Московской олимпиады и заключительного этапа Всероссийской олимпиады, от седьмого класса до доказательства делимости на 27.

Признаки делимости и почему они работают

Запишем число через его цифры. Например, 2754=2⋅1000+7⋅100+5⋅10+42754 = 2 \cdot 1000 + 7 \cdot 100 + 5 \cdot 10 + 4. Все признаки получаются из того, какой остаток дают степени десятки при делении на нужное число.

На 2, 5 и 10. Число 10 делится на 2 и на 5, значит, всё, кроме последней цифры, на них делится. Остаётся проверить последнюю цифру: чётная — делится на 2, 0 или 5 — делится на 5, ноль — на 10.

На 4 и 25, на 8 и 125. 100=4⋅25100 = 4 \cdot 25, поэтому сотни, тысячи и все старшие разряды делятся на 4 и на 25 — смотрят на число из двух последних цифр. У числа 1 000 316 это 16, оно кратно 4, значит, и всё число кратно 4. Для 8 и 125 так же работают три последние цифры, потому что 1000=8⋅1251000 = 8 \cdot 125.

На 3 и 9. Здесь важно, что 10=9+110 = 9 + 1, а 100=99+1100 = 99 + 1, 1000=999+11000 = 999 + 1 и так далее. Каждая степень десятки при делении на 9 даёт остаток 1. Поэтому

2754=2⋅999+7⋅99+5⋅9+(2+7+5+4).2754 = 2 \cdot 999 + 7 \cdot 99 + 5 \cdot 9 + (2 + 7 + 5 + 4).

Первые три слагаемых делятся на 9, значит, у числа 2754 и у суммы его цифр 1818 один и тот же остаток при делении на 9. Это сильнее обычной формулировки признака: по сумме цифр можно найти не только «делится или нет», но и сам остаток. Число 12 345 678 с суммой цифр 36 делится на 9, а число из 300 единиц даёт остаток 3 — это понадобится в задаче 2.

На 11. 10=11−110 = 11 - 1, поэтому при делении на 11 десятка даёт остаток −1-1 (то есть 10), сотня — остаток (−1)2=1(-1)^2 = 1, тысяча — снова −1-1. Отсюда признак: сложите цифры через одну со знаками «плюс» и «минус», начиная с последней. У числа 2728 получается 8−2+7−2=118 - 2 + 7 - 2 = 11, значит, 27282728 делится на 11 (это 11⋅24811 \cdot 248).

На составные числа. Если число раскладывается на взаимно простые множители, проверяют каждый. На 6 — делимость на 2 и на 3, на 12 — на 3 и на 4, на 45 — на 5 и на 9. Пары 2 и 6 для числа 12 недостаточно: 6 делится и на 2, и на 6, но не на 12.

Арифметика остатков простыми словами

Говорят, что aa сравнимо с bb по модулю mm, и пишут a≡b(modm)a \equiv b \pmod m, если aa и bb дают одинаковые остатки при делении на mm. Это то же самое, что «разность a−ba - b делится на mm». Например, 17≡2(mod5)17 \equiv 2 \pmod 5 и −1≡4(mod5)-1 \equiv 4 \pmod 5.

Главное свойство: в сумме, разности и произведении любое число можно заменить на его остаток, и остаток результата не изменится. Если a≡ba \equiv b и c≡dc \equiv d по модулю mm, то a+c≡b+da + c \equiv b + d, ac≡bdac \equiv bd и an≡bna^n \equiv b^n.

Так считается остаток огромных степеней. Найдём остаток 21002^{100} при делении на 3. Поскольку 2≡−1(mod3)2 \equiv -1 \pmod 3, получаем 2100≡(−1)100=1(mod3)2^{100} \equiv (-1)^{100} = 1 \pmod 3. Остаток равен 1, и выписывать 31-значное число не пришлось.

Делить сравнения нельзя без оговорок: 2⋅3≡2⋅0(mod6)2 \cdot 3 \equiv 2 \cdot 0 \pmod 6, но 33 не сравнимо с 00 по модулю 6. Сократить на число можно, только если оно взаимно просто с модулем.

Второе применение — короткие таблицы остатков. Квадрат целого числа при делении на 3 даёт только остатки 0 и 1, при делении на 9 — только 0, 1, 4 и 7. Если по условию получается квадрат с остатком 2 по модулю 3, задача решена. Тот же приём для уравнений, где ищут целые решения, подробно разобран в статье об уравнениях в целых числах.

  1. Найдите модульпо виду задачи: цифры числа подсказывают 9 или 11, квадраты — 3, 4, 8 или 9, конкретное число в условии — его простые делители
  2. Перейдите к остаткамзамените каждое число и выражение остатком и упростите
  3. Переберите случаиостатков конечное число, обычно не больше девяти
  4. Сделайте выводразные остатки у двух частей — равенство невозможно; одинаковые во всех случаях — делимость доказана

Задача 1: простое число и сумма цифр

1Условие7 классМатематический праздник, 2004 год

Ваня задумал простое трёхзначное число, все цифры которого различны. На какую цифру оно может оканчиваться, если его последняя цифра равна сумме первых двух?

Показать решение ↓Скрыть решение ↑

Решение

Обозначим цифры aa, bb, cc, где c=a+bc = a + b. Первая цифра aa не меньше 1, поэтому c≥1c \ge 1. Если c=1c = 1, то a=1a = 1 и b=0b = 0, число равно 101 — у него повторяется цифра 1, это запрещено.

Трёхзначное простое число не может оканчиваться чётной цифрой — иначе оно делилось бы на 2 и было бы больше 2. Не может оно оканчиваться и цифрой 5 — делилось бы на 5. Остались варианты c=3c = 3, 77 и 99.

Сумма всех цифр равна a+b+c=2ca + b + c = 2c. При c=3c = 3 она равна 6, при c=9c = 9 — 18. В обоих случаях сумма цифр делится на 3, значит, и число делится на 3 и не может быть простым.

Цифра 7 действительно встречается: число 167 простое, его цифры различны и 1+6=71 + 6 = 7. Подходят также 257, 347 и 617.

ОтветНа цифру 7.

Источник задачи: XV Математический праздник, 15 февраля 2004 года, 7 класс, задача 1 — условие — официальный архив Математического праздника; решение — problems.ru, задача 103898

Математический праздник проводят для 6 и 7 классов, и задачи на признаки делимости там встречаются среди первых, самых доступных. Что это за олимпиада и как в ней участвовать, рассказано на странице о Математическом празднике.

Задача 2: число из единиц и нулей

2Условие8 классМосковская математическая олимпиада, 1960 год

Доказать, что число, состоящее из 300 единиц и некоторого количества нулей, не является точным квадратом.

Показать решение ↓Скрыть решение ↑

Решение

Сумма цифр такого числа равна 300, сколько бы нулей в нём ни было и где бы они ни стояли. Сумма 300 делится на 3, значит, по признаку делимости и само число делится на 3. А 300=9⋅33+3300 = 9 \cdot 33 + 3, поэтому при делении на 9 число даёт остаток 3 и на 9 не делится.

Предположим, что это число равно k2k^2. Тогда k2k^2 делится на 3. Число 3 простое, поэтому если 33 делит k⋅kk \cdot k, то 3 делит kk. Но тогда k=3tk = 3t и k2=9t2k^2 = 9t^2 делится на 9 — противоречие.

То же видно из таблицы: квадраты по модулю 9 дают остатки 0, 1, 4 и 7, остатка 3 среди них нет.

ОтветУтверждение доказано: число делится на 3, но не делится на 9, а квадрат, кратный 3, всегда кратен 9.

Источник задачи: XXIII Московская математическая олимпиада, 1960 год, 8 класс, первый тур, задача 1 — условие и решение — problems.ru, архив задач МЦНМО

Задача 3: семь жетонов

3Условие8–9 классМосковская математическая олимпиада, 1952 год

Имеются семь жетонов с цифрами 1, 2, 3, 4, 5, 6, 7. Докажите, что ни одно семизначное число, составленное посредством этих жетонов, не делится на другое.

Показать решение ↓Скрыть решение ↑

Решение

Во всех таких числах одни и те же цифры, только в разном порядке. Сумма цифр у каждого равна 1+2+…+7=281 + 2 + \ldots + 7 = 28, а 28=9⋅3+128 = 9 \cdot 3 + 1. Значит, по признаку делимости каждое такое число даёт остаток 1 при делении на 9.

Пусть a=kba = kb, где aa и bb — два разных числа из жетонов, kk — натуральное. Так как a≠ba \ne b, то k≥2k \ge 2. Оценим kk сверху: самое большое число из жетонов — 7 654 321, самое маленькое — 1 234 567, а 7⋅1 234 567=8 641 969>7 654 3217 \cdot 1\,234\,567 = 8\,641\,969 > 7\,654\,321. Значит, k≤6k \le 6.

Теперь перейдём к остаткам по модулю 9. Из a≡1a \equiv 1 и b≡1b \equiv 1 получаем 1≡k⋅1(mod9)1 \equiv k \cdot 1 \pmod 9, то есть k−1k - 1 делится на 9. При 2≤k≤62 \le k \le 6 число k−1k - 1 лежит от 1 до 5 и на 9 не делится. Противоречие.

ОтветДоказано: все такие числа дают остаток 1 при делении на 9, поэтому частное двух из них сравнимо с 1 по модулю 9, а целых частных от 2 до 6 с таким свойством нет.

Источник задачи: XV Московская математическая олимпиада, 1952 год, второй тур, 8 класс и 9 класс, задача 3 — условие и решение — problems.ru, архив задач МЦНМО

Решение держится на двух шагах: остаток не зависит от порядка цифр, а оценка оставляет мало вариантов для kk. Без оценки рассуждение не закончено — при k=10k = 10 остаток по модулю 9 тоже был бы равен 1.

Задача 4: делимость на 2019

4Условие8 классМосковская математическая олимпиада, 2019 год

Найдите наименьшее натуральное число nn, для которого n2+20n+19n^2 + 20n + 19 делится на 20192019.

Показать решение ↓Скрыть решение ↑

Решение

Разложим выражение и модуль на множители:

n2+20n+19=(n+1)(n+19),2019=3⋅673,n^2 + 20n + 19 = (n + 1)(n + 19), \qquad 2019 = 3 \cdot 673,

где 3 и 673 — простые числа.

Произведение делится на простое число 3, только если на 3 делится хотя бы один множитель. Множители n+1n + 1 и n+19n + 19 отличаются на 18, а 18 кратно 3, поэтому они дают одинаковый остаток при делении на 3. Значит, если на 3 делится один из них, то делятся оба.

Произведение делится и на простое число 673, поэтому один из множителей кратен 673. Этот множитель делится и на 3, и на 673, а значит, на 3⋅673=20193 \cdot 673 = 2019.

Остаётся найти наименьшее натуральное nn, при котором n+1n + 1 или n+19n + 19 кратно 2019. Для n+19n + 19 это n=2000n = 2000, для n+1n + 1 — n=2018n = 2018. Меньшее из них — 2000.

Проверка: 20002+20⋅2000+19=4 040 019=2019⋅20012000^2 + 20 \cdot 2000 + 19 = 4\,040\,019 = 2019 \cdot 2001.

Ответn=2000n = 2000.

Источник задачи: LXXXII Московская математическая олимпиада, 17 марта 2019 года, 8 класс, задача 2 (автор Д. Шноль) — условие — официальный сайт ММО; решение — problems.ru, задача 66530

Если следить только за делимостью на 673, легко получить неверный ответ n=654n = 654. Тогда n+19=673n + 19 = 673, но 673673 не делится на 3, и n+1=655n + 1 = 655 тоже не делится. Проверка делимости на каждый простой множитель модуля обязательна.

Задача 5: делимость на 27

5Условие9–10 классзаключительный этап Всероссийской олимпиады, 1993 год

Целые числа xx, yy и zz таковы, что (x−y)(y−z)(z−x)=x+y+z(x - y)(y - z)(z - x) = x + y + z. Докажите, что число x+y+zx + y + z делится на 27.

Показать решение ↓Скрыть решение ↑

Решение

Посмотрим на остатки xx, yy, zz при делении на 3.

Все остатки разные. Тогда это остатки 0, 1 и 2 в каком-то порядке, и x+y+z≡0+1+2=3≡0(mod3)x + y + z \equiv 0 + 1 + 2 = 3 \equiv 0 \pmod 3 — правая часть делится на 3. А в левой части ни одна разность не делится на 3, так как в каждой паре остатки различны. Произведение трёх чисел, не делящихся на простое 3, на 3 не делится. Противоречие, этот случай невозможен.

Хотя бы два остатка совпадают. Тогда разность этих двух чисел делится на 3, и всё произведение делится на 3. Значит, x+y+zx + y + z тоже делится на 3. Пусть, например, x≡y≡rx \equiv y \equiv r, а z≡s(mod3)z \equiv s \pmod 3. Тогда 2r+s≡0(mod3)2r + s \equiv 0 \pmod 3, откуда s≡−2r≡r(mod3)s \equiv -2r \equiv r \pmod 3. Третий остаток совпадает с двумя первыми.

Итог. Все три остатка одинаковые, поэтому каждая из трёх разностей x−yx - y, y−zy - z, z−xz - x делится на 3, и их произведение делится на 3⋅3⋅3=273 \cdot 3 \cdot 3 = 27. Оно равно x+y+zx + y + z, что и требовалось.

Такие числа существуют: при x=15x = 15, y=18y = 18, z=21z = 21 левая часть равна (−3)⋅(−3)⋅6=54(-3) \cdot (-3) \cdot 6 = 54, а правая 15+18+21=5415 + 18 + 21 = 54.

ОтветДоказано: из равенства следует, что xx, yy, zz дают одинаковые остатки при делении на 3, поэтому каждая разность кратна 3, а их произведение x+y+zx + y + z кратно 27.

Источник задачи: Всероссийская олимпиада по математике 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 — разложите его на простые множители и проверяйте каждый.

Источники

  1. problems.ru — рубрика «Признаки делимости» — архив задач МЦНМО
  2. problems.ru — рубрика «Деление с остатком. Арифметика остатков» — архив задач МЦНМО
  3. Математический праздник 2004, условия и решения для 7 класса — официальный архив олимпиады
  4. problems.ru — Математический праздник 2004, 7 класс, задача 1 — условие и решение
  5. problems.ru — ММО 1960, 8 класс, задача 1 — условие и решение
  6. МЦНМО — ММО 1952, 8 класс, второй тур, задача 3 — условие и решение
  7. mmo.mccme.ru — LXXXII Московская математическая олимпиада, 2019 — официальный сборник ММО, условия и решения
  8. problems.ru — ММО 2019, 8 класс, задача 2 — условие и два решения
  9. problems.ru — Всероссийская олимпиада 1992/93, заключительный этап — задачи этапа
  10. problems.ru — ВсОШ 1993, 9 класс, задача 5 — условие и решение
Редакция блога «Олмат»Готовит материалы вместе с преподавателями школы. Задачи — из официальных архивов олимпиад.

Записаться на бесплатную консультацию

Оставьте телефон — ответим коротко и по делу. Один звонок, без обзвонов и рассылок.