Делимость и остатки
Делимость и остатки позволяют быстро отсекать невозможные равенства и сужать перебор в задании 19. Остаток суммы, разности и произведения зависит только от остатков слагаемых и множителей. Если левая и правая части равенства дают разные остатки при делении на одно число, такое равенство невозможно.
Деление с остатком и главные правила делимости
Любое целое число при делении на натуральное единственным образом записывается как , где — целое частное, а остаток лежит в границах (при число делится нацело).
- Остаток суммы, разности и произведения равен остатку суммы, разности и произведения остатков.
- Два числа дают одинаковые остатки при делении на тогда и только тогда, когда их разность делится на .
- Число и сумма его цифр дают один и тот же остаток при делении на 3 и на 9.
- Делимость на произведение взаимно простых чисел равносильна делимости на каждое из них.
- Если две части равенства дают разные остатки при делении на одно число, равенство невозможно.
Признаки делимости
| Делитель | Число делится, если | Пример |
|---|---|---|
| 2 | последняя цифра чётная: 0, 2, 4, 6, 8 | |
| 3 | сумма цифр делится на 3 | : |
| 4 | число из двух последних цифр делится на 4 | : |
| 5 | последняя цифра 0 или 5 | |
| 6 | число делится на 2 и на 3 | : чётное, сумма цифр |
| 9 | сумма цифр делится на 9 | : |
| 10 | последняя цифра 0 | |
| 8 | число из трёх последних цифр делится на 8 | : |
| 11 | разность сумм цифр на нечётных и чётных местах делится на 11 | : |
| 25 | две последние цифры — 00, 25, 50 или 75 |
Сетка остатков
Арифметика остатков и частые инварианты
Эти три факта закрывают большинство пунктов б) в задании 19.
Замена на остатки
В сумме, разности и произведении замените числа их остатками, посчитайте и снова возьмите остаток.
Одинаковые остатки
Все числа с одним остатком задаются формулой , а разность любых двух делится на .
Остатки квадратов
Квадрат целого числа при делении на 3 и на 4 даёт только остаток 0 или 1 — другие остатки невозможны.
Остатки суммы, разности, произведения и степеней
Чтобы найти остаток сложного выражения при делении на , не вычисляйте само выражение — замените каждое слагаемое или множитель его остатком от до и возьмите остаток результата.
Возможные остатки квадратов и степеней находят перебором всех остатков: вместо числа достаточно подставить .
Частая ошибка. Остаток всегда неотрицателен, даже если число отрицательное. Например, , поэтому остаток при делении на 4 равен , а не .
Если и , то . Первое слагаемое кратно , поэтому остаток совпадает с остатком . То же верно для .
Пример
Может ли квадрат натурального числа давать остаток 3 при делении на 4?
- 1.При делении на 4 натуральное число даёт остаток 0, 1, 2 или 3.
- 2.Возводим остатки в квадрат и берём остаток на 4: , , (остаток 0), (остаток 1).
- 3.Возможны только остатки 0 и 1, поэтому остаток 3 невозможен.
Ответ: нет
Одинаковые остатки и разность чисел
Два числа дают один остаток при делении на тогда и только тогда, когда их разность делится на : при вычитании остаток исчезает.
Такая структура возникает в задачах, где среднее любых чисел набора целое. Чтобы проверить, может ли число лежать на доске, сравните его остаток на с общим остатком .
Пример
Все числа на доске дают одинаковые остатки при делении на 60, одно из них равно 30035. а) Может ли на доске быть число 325? б) Может ли одно число на доске быть в 7 раз больше другого?
- 1.Найдём общий остаток по числу 30035: . Значит, все числа на доске имеют вид .
- 2.а) Делим 325 на 60: . Остаток равен 25, а не 35 — числа 325 на доске быть не может.
- 3.б) Умножим число на 7: . Число даёт остаток 5, а не 35, поэтому на доске его нет.
Ответ: а) нет; б) нет
Число и сумма его цифр
Любое натуральное число и сумма его цифр дают один и тот же остаток при делении на 9 (а значит, и на 3). Отсюда сразу следуют признаки делимости на 3 и на 9.
Если построить цепочку, где каждое следующее число равно сумме цифр предыдущего, у всех чисел цепочки будет один и тот же остаток при делении на 9 и на 3.
В десятичной записи каждое разрядное слагаемое имеет вид . Число всегда делится на 9, поэтому разность кратна 9.
Пример
На доске написаны три различных натуральных числа. Второе число равно сумме цифр первого, а третье — сумме цифр второго. Может ли сумма этих трёх чисел быть равна 2024?
- 1.Число и сумма его цифр дают одинаковые остатки при делении на 3, поэтому все три числа имеют один и тот же остаток .
- 2.Их сумма даёт при делении на 3 тот же остаток, что и , то есть обязана делиться на 3.
- 3.Сумма цифр числа 2024 равна — на 3 не делится. Значит, сумма не может равняться 2024.
Ответ: нет
Делимость на произведение взаимно простых чисел
Два числа называют взаимно простыми, если их наибольший общий делитель равен 1. Делимость на произведение взаимно простых и равносильна одновременной делимости на и на : например, для проверяют 5 и 9, а для — 3 и 4.
Если каждое слагаемое делится на , то сумма и разность тоже делятся на .
Частая ошибка. Взаимная простота обязательна! Число 18 делится и на 2, и на 6, но не делится на , потому что у 2 и 6 есть общий делитель 2.
Пример
Каждое из двух натуральных чисел делится на 45. Может ли их сумма быть равна 3435?
- 1.Сумма двух чисел, кратных 45, обязана делиться на .
- 2.Так как 5 и 9 взаимно просты, сумма должна делиться и на 5, и на 9.
- 3.Сумма цифр числа 3435 равна , что не делится на 9. Значит, 3435 не делится на 45.
Ответ: нет
Сокращение общего множителя в делимости
Если произведение делится на , а числа и взаимно просты, то на обязан делиться второй множитель : все простые множители числа вынуждены находиться в .
Если у и есть общий делитель больше 1, сначала разделите на него оба числа — как при сокращении дроби. Этот шаг регулярно даёт оценку через делимость в пункте в).
Пример
Найдите наименьшее натуральное , при котором делится на 90.
- 1.Сократим условие « делится на 90» на общий делитель 6: получим « делится на 15».
- 2.Числа 7 и 15 взаимно просты, значит, на 15 делится само число .
- 3.Наименьшее натуральное кратное 15 — это 15. Проверка: .
Ответ: 15
Делимость произведения на простое число
Если простое число делит произведение , оно обязано делить хотя бы один из множителей: или .
В задачах часто раскладывают на множители выражения вроде и : соседние числа и взаимно просты, и одно из них обязательно чётно.
Частая ошибка. Для составного делителя правило не работает: делится на 6, хотя ни 2, ни 3 на 6 не делятся. Составной делитель сначала раскладывайте на взаимно простые множители.
Пример
Найдите наименьшее натуральное , при котором делится на 28.
- 1.Разложим выражение и делитель: должно делиться на (4 и 7 взаимно просты).
- 2.Простое число 7 делит , значит, 7 делит или . Получаем кандидатов:
- 3.Учтём делимость на 4: при чётном оба множителя нечётны, а при нечётном оба чётны и их произведение делится на 4. Значит, нечётно.
- 4.Из списка 6 и 8 отпадают, первое подходящее значение — . Проверка: .
Ответ: 13
Уравнения в целых числах и остатки
Чтобы решить уравнение в целых числах вида , сравните остатки обеих частей при делении на один из коэффициентов. Выбирая деление на 5, вы обнуляете слагаемое и получаете простое условие на остаток переменной .
Подходящие значения идут с шагом, равным выбранному делителю — остаётся проверить немногочисленных кандидатов в границах условия.
Пример
На столе лежат 3 камня по 5 кг и 11 камней по 13 кг. Можно ли разложить их на две кучки равной массы?
- 1.Общая масса камней: кг. В каждой кучке должно быть ровно кг.
- 2.Получаем уравнение , где и .
- 3.Берём остатки при делении на 5: даёт 0, даёт тот же остаток, что и , а 79 даёт остаток 4. Перебирая остатки для , находим
- 4.При получаем , то есть (невозможно). При уже . Значит, разложить камни поровну нельзя.
Ответ: нет
Числа, кратные данному, в ряду подряд
Среди любых подряд идущих натуральных чисел ровно одно делится на . Разделив длину ряда на с остатком (), вы сразу видите: полные блоки дают кратных, а хвост из чисел добавляет 0 или 1 кратное.
Обратно: если в ряду подряд ровно чисел, кратных , между первым и последним укладывается промежутков по , а всего чисел не может быть или больше — иначе набралось бы уже кратное.
Пример
Сколько чисел, кратных 7, может быть среди 30 натуральных чисел, идущих подряд?
- 1.Делим длину ряда на 7 с остатком: . Четыре полные семёрки дают 4 кратных, а хвост из 2 чисел — ещё 0 или 1.
- 2.Значит, кратных может быть 4 или 5. Оба случая достигаются: от 1 до 30 их 4 (7, 14, 21, 28), от 7 до 36 их 5 (7, 14, 21, 28, 35).
Ответ: 4 или 5
Чётность и попарно взаимно простые числа
Сумма целых чисел чётна тогда и только тогда, когда в ней чётное число нечётных слагаемых. Сумма и разность всегда имеют одинаковую чётность, потому что отличаются на чётное число .
В наборе попарно взаимно простых чисел может быть не больше одного чётного (любые два чётных делятся на 2). А у остальных чисел больше 1 наименьшие простые делители различны — это сразу даёт нижнюю оценку суммы и работает в доказательстве невозможности.
Пример задания
Открытый банк ФИПИ
На доске написано 10 натуральных чисел, среди которых нет одинаковых. Оказалось, что среднее арифметическое любых четырех или семи чисел из записанных является целым числом.
а) Могут ли среди записанных на доске чисел одновременно быть числа 567 и 1414?
б) Может ли одно из записанных на доске чисел быть квадратом другого, если среди записанных на доске чисел есть число 567?
в) Известно, что среди записанных на доске чисел есть число и его квадрат Найдите наименьшее возможное значение
Проверьте себя
00