Задание 19
тема 4 из 7

Делимость и остатки

Делимость и остатки позволяют быстро отсекать невозможные равенства и сужать перебор в задании 19. Остаток суммы, разности и произведения зависит только от остатков слагаемых и множителей. Если левая и правая части равенства дают разные остатки при делении на одно число, такое равенство невозможно.

Часто в задании19На карте навыков

Деление с остатком и главные правила делимости

Любое целое число aa при делении на натуральное mm единственным образом записывается как a=mq+ra = mq + r, где qq — целое частное, а остаток rr лежит в границах 0≤r<m0 \le r < m (при r=0r = 0 число делится нацело).

  • Остаток суммы, разности и произведения равен остатку суммы, разности и произведения остатков.
  • Два числа дают одинаковые остатки при делении на mm тогда и только тогда, когда их разность делится на mm.
  • Число и сумма его цифр дают один и тот же остаток при делении на 3 и на 9.
  • Делимость на произведение взаимно простых чисел равносильна делимости на каждое из них.
  • Если две части равенства дают разные остатки при делении на одно число, равенство невозможно.

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

ДелительЧисло делится, еслиПример
2последняя цифра чётная: 0, 2, 4, 6, 813581358
3сумма цифр делится на 321452145: 2+1+4+5=122 + 1 + 4 + 5 = 12
4число из двух последних цифр делится на 473167316: 16=4⋅416 = 4 \cdot 4
5последняя цифра 0 или 547354735
6число делится на 2 и на 351365136: чётное, сумма цифр 1515
9сумма цифр делится на 973987398: 7+3+9+8=277 + 3 + 9 + 8 = 27
10последняя цифра 045604560

Сетка остатков

a=4q+r,0≤r<4a = 4q + r,\quad 0 \le r < 4
0123012345678910111213141516171819
Сумма 7+10=177 + 10 = 17 даёт остаток 11. Сумма остатков 3+2=53 + 2 = 5 даёт тот же остаток 11.
Произведение 7⋅10=707 \cdot 10 = 70 даёт остаток 22. Произведение остатков 3⋅2=63 \cdot 2 = 6 даёт тот же остаток 22.
Разность 10−7=310 - 7 = 3 не делится на 44: числа стоят в разных столбцах.
Числа в одном столбце дают одинаковый остаток при делении на выбранный делитель mm, а разность любых двух из них делится на mm. Выбирайте числа касанием и меняйте mm ползунком.

Арифметика остатков и частые инварианты

Эти три факта закрывают большинство пунктов б) в задании 19.

  • Замена на остатки

    a→ra,b→rba \to r_a,\quad b \to r_b

    В сумме, разности и произведении замените числа их остатками, посчитайте и снова возьмите остаток.

  • Одинаковые остатки

    a−b=mka - b = mk

    Все числа с одним остатком rr задаются формулой mk+rmk + r, а разность любых двух делится на mm.

  • Остатки квадратов

    r(n2)∈{0,1}r(n^2) \in \{0, 1\}

    Квадрат целого числа при делении на 3 и на 4 даёт только остаток 0 или 1 — другие остатки невозможны.

Остатки суммы, разности, произведения и степеней

Чтобы найти остаток сложного выражения при делении на mm, не вычисляйте само выражение — замените каждое слагаемое или множитель его остатком от 00 до m−1m - 1 и возьмите остаток результата.

Возможные остатки квадратов и степеней находят перебором всех mm остатков: вместо числа nn достаточно подставить 0,1,…,m−10, 1, \ldots, m - 1.

a=mq+r,0≤r<ma = mq + r,\qquad 0 \le r < m

Частая ошибка. Остаток всегда неотрицателен, даже если число отрицательное. Например, −7=4⋅(−2)+1-7 = 4 \cdot (-2) + 1, поэтому остаток при делении на 4 равен 11, а не −3-3.

Пример

Может ли квадрат натурального числа давать остаток 3 при делении на 4?

  1. 1.При делении на 4 натуральное число nn даёт остаток 0, 1, 2 или 3.
  2. 2.Возводим остатки в квадрат и берём остаток на 4: 02=00^2 = 0, 12=11^2 = 1, 22=42^2 = 4 (остаток 0), 32=93^2 = 9 (остаток 1).
  3. 3.Возможны только остатки 0 и 1, поэтому остаток 3 невозможен.

Ответ: нет

Одинаковые остатки и разность чисел

Два числа дают один остаток rr при делении на mm тогда и только тогда, когда их разность делится на mm: при вычитании (mk1+r)−(mk2+r)=m(k1−k2)(mk_1 + r) - (mk_2 + r) = m(k_1 - k_2) остаток исчезает.

Такая структура возникает в задачах, где среднее любых kk чисел набора целое. Чтобы проверить, может ли число лежать на доске, сравните его остаток на mm с общим остатком rr.

a и b дают один остаток на m  ⟺  a−b=mka \text{ и } b \text{ дают один остаток на } m \iff a - b = mk

Пример

Все числа на доске дают одинаковые остатки при делении на 60, одно из них равно 30035. а) Может ли на доске быть число 325? б) Может ли одно число на доске быть в 7 раз больше другого?

  1. 1.Найдём общий остаток по числу 30035: 30035=60⋅500+3530035 = 60 \cdot 500 + 35. Значит, все числа на доске имеют вид 60k+3560k + 35.
  2. 2.а) Делим 325 на 60: 325=60⋅5+25325 = 60 \cdot 5 + 25. Остаток равен 25, а не 35 — числа 325 на доске быть не может.
  3. 3.б) Умножим число x=60k+35x = 60k + 35 на 7: 7x=420k+245=60(7k+4)+57x = 420k + 245 = 60(7k + 4) + 5. Число 7x7x даёт остаток 5, а не 35, поэтому на доске его нет.

Ответ: а) нет; б) нет

Число и сумма его цифр

Любое натуральное число и сумма его цифр S(N)S(N) дают один и тот же остаток при делении на 9 (а значит, и на 3). Отсюда сразу следуют признаки делимости на 3 и на 9.

Если построить цепочку, где каждое следующее число равно сумме цифр предыдущего, у всех чисел цепочки будет один и тот же остаток при делении на 9 и на 3.

N−S(N) делится на 9N - S(N) \text{ делится на } 9

Пример

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

  1. 1.Число и сумма его цифр дают одинаковые остатки при делении на 3, поэтому все три числа имеют один и тот же остаток rr.
  2. 2.Их сумма даёт при делении на 3 тот же остаток, что и r+r+r=3rr + r + r = 3r, то есть обязана делиться на 3.
  3. 3.Сумма цифр числа 2024 равна 2+0+2+4=82 + 0 + 2 + 4 = 8 — на 3 не делится. Значит, сумма не может равняться 2024.

Ответ: нет

Делимость на произведение взаимно простых чисел

Два числа называют взаимно простыми, если их наибольший общий делитель равен 1. Делимость на произведение взаимно простых mm и nn равносильна одновременной делимости на mm и на nn: например, для 45=5⋅945 = 5 \cdot 9 проверяют 5 и 9, а для 12=3⋅412 = 3 \cdot 4 — 3 и 4.

Если каждое слагаемое делится на mm, то сумма и разность тоже делятся на mm.

НОД(m,n)=1  ⟹  (a кратно mn  ⟺  a кратно m и n)\text{НОД}(m, n) = 1 \implies \big(a \text{ кратно } mn \iff a \text{ кратно } m \text{ и } n\big)

Частая ошибка. Взаимная простота обязательна! Число 18 делится и на 2, и на 6, но не делится на 2⋅6=122 \cdot 6 = 12, потому что у 2 и 6 есть общий делитель 2.

Пример

Каждое из двух натуральных чисел делится на 45. Может ли их сумма быть равна 3435?

  1. 1.Сумма двух чисел, кратных 45, обязана делиться на 45=5⋅945 = 5 \cdot 9.
  2. 2.Так как 5 и 9 взаимно просты, сумма должна делиться и на 5, и на 9.
  3. 3.Сумма цифр числа 3435 равна 3+4+3+5=153 + 4 + 3 + 5 = 15, что не делится на 9. Значит, 3435 не делится на 45.

Ответ: нет

Сокращение общего множителя в делимости

Если произведение abab делится на mm, а числа aa и mm взаимно просты, то на mm обязан делиться второй множитель bb: все простые множители числа mm вынуждены находиться в bb.

Если у aa и mm есть общий делитель больше 1, сначала разделите на него оба числа — как при сокращении дроби. Этот шаг регулярно даёт оценку через делимость в пункте в).

ab кратно m,  НОД(a,m)=1  ⟹  b кратно mab \text{ кратно } m,\; \text{НОД}(a, m) = 1 \implies b \text{ кратно } m

Пример

Найдите наименьшее натуральное bb, при котором 42b42b делится на 90.

  1. 1.Сократим условие «42b42b делится на 90» на общий делитель 6: получим «7b7b делится на 15».
  2. 2.Числа 7 и 15 взаимно просты, значит, на 15 делится само число bb.
  3. 3.Наименьшее натуральное кратное 15 — это 15. Проверка: 42⋅15=630=90⋅742 \cdot 15 = 630 = 90 \cdot 7.

Ответ: 15

Делимость произведения на простое число

Если простое число pp делит произведение abab, оно обязано делить хотя бы один из множителей: aa или bb.

В задачах часто раскладывают на множители выражения вроде n2−n=n(n−1)n^2 - n = n(n - 1) и n2−1=(n−1)(n+1)n^2 - 1 = (n - 1)(n + 1): соседние числа n−1n - 1 и nn взаимно просты, и одно из них обязательно чётно.

p простое и делит ab  ⟹  p делит a или p делит bp \text{ простое и делит } ab \implies p \text{ делит } a \text{ или } p \text{ делит } b

Частая ошибка. Для составного делителя правило не работает: 2⋅3=62 \cdot 3 = 6 делится на 6, хотя ни 2, ни 3 на 6 не делятся. Составной делитель сначала раскладывайте на взаимно простые множители.

Пример

Найдите наименьшее натуральное n>1n > 1, при котором n2−1n^2 - 1 делится на 28.

  1. 1.Разложим выражение и делитель: n2−1=(n−1)(n+1)n^2 - 1 = (n - 1)(n + 1) должно делиться на 28=4⋅728 = 4 \cdot 7 (4 и 7 взаимно просты).
  2. 2.Простое число 7 делит (n−1)(n+1)(n - 1)(n + 1), значит, 7 делит n−1n - 1 или n+1n + 1. Получаем кандидатов: n=6,8,13,15,…n = 6, 8, 13, 15, \ldots
  3. 3.Учтём делимость на 4: при чётном nn оба множителя нечётны, а при нечётном nn оба чётны и их произведение делится на 4. Значит, nn нечётно.
  4. 4.Из списка 6 и 8 отпадают, первое подходящее значение — n=13n = 13. Проверка: 132−1=168=28⋅613^2 - 1 = 168 = 28 \cdot 6.

Ответ: 13

Уравнения в целых числах и остатки

Чтобы решить уравнение в целых числах вида 5a+13b=795a + 13b = 79, сравните остатки обеих частей при делении на один из коэффициентов. Выбирая деление на 5, вы обнуляете слагаемое 5a5a и получаете простое условие на остаток переменной bb.

Подходящие значения bb идут с шагом, равным выбранному делителю — остаётся проверить немногочисленных кандидатов в границах условия.

5a+13b=79  ⟹  3b и 4 дают один остаток на 55a + 13b = 79 \implies 3b \text{ и } 4 \text{ дают один остаток на } 5

Пример

На столе лежат 3 камня по 5 кг и 11 камней по 13 кг. Можно ли разложить их на две кучки равной массы?

  1. 1.Общая масса камней: 3⋅5+11⋅13=1583 \cdot 5 + 11 \cdot 13 = 158 кг. В каждой кучке должно быть ровно 158:2=79158 : 2 = 79 кг.
  2. 2.Получаем уравнение 5a+13b=795a + 13b = 79, где 0≤a≤30 \le a \le 3 и 0≤b≤110 \le b \le 11.
  3. 3.Берём остатки при делении на 5: 5a5a даёт 0, 13b13b даёт тот же остаток, что и 3b3b, а 79 даёт остаток 4. Перебирая остатки для bb, находим b=3,8,13,…b = 3, 8, 13, \ldots
  4. 4.При b=3b = 3 получаем 5a=79−39=405a = 79 - 39 = 40, то есть a=8>3a = 8 > 3 (невозможно). При b=8b = 8 уже 13⋅8=104>7913 \cdot 8 = 104 > 79. Значит, разложить камни поровну нельзя.

Ответ: нет

Числа, кратные данному, в ряду подряд

Среди любых mm подряд идущих натуральных чисел ровно одно делится на mm. Разделив длину ряда kk на mm с остатком (k=mq+rk = mq + r), вы сразу видите: полные блоки дают qq кратных, а хвост из rr чисел добавляет 0 или 1 кратное.

Обратно: если в ряду подряд ровно pp чисел, кратных mm, между первым и последним укладывается p−1p - 1 промежутков по mm, а всего чисел не может быть m(p+1)m(p + 1) или больше — иначе набралось бы уже p+1p + 1 кратное.

m(p−1)+1≤k≤m(p+1)−1m(p - 1) + 1 \le k \le m(p + 1) - 1

Пример

Сколько чисел, кратных 7, может быть среди 30 натуральных чисел, идущих подряд?

  1. 1.Делим длину ряда на 7 с остатком: 30=7⋅4+230 = 7 \cdot 4 + 2. Четыре полные семёрки дают 4 кратных, а хвост из 2 чисел — ещё 0 или 1.
  2. 2.Значит, кратных может быть 4 или 5. Оба случая достигаются: от 1 до 30 их 4 (7, 14, 21, 28), от 7 до 36 их 5 (7, 14, 21, 28, 35).

Ответ: 4 или 5

Чётность и попарно взаимно простые числа

Сумма целых чисел чётна тогда и только тогда, когда в ней чётное число нечётных слагаемых. Сумма a+ba + b и разность a−ba - b всегда имеют одинаковую чётность, потому что отличаются на чётное число 2b2b.

В наборе попарно взаимно простых чисел может быть не больше одного чётного (любые два чётных делятся на 2). А у остальных чисел больше 1 наименьшие простые делители различны — это сразу даёт нижнюю оценку суммы и работает в доказательстве невозможности.

a+b и a−b всегда одной чётностиa + b \text{ и } a - b \text{ всегда одной чётности}

Пример задания

Открытый банк ФИПИ

На доске написано 10 натуральных чисел, среди которых нет одинаковых. Оказалось, что среднее арифметическое любых четырех или семи чисел из записанных является целым числом.
а)  Могут ли среди записанных на доске чисел одновременно быть числа 567 и 1414?
б)  Может ли одно из записанных на доске чисел быть квадратом другого, если среди записанных на доске чисел есть число 567?
в)  Известно, что среди записанных на доске чисел есть число nn и его квадрат n2.n^{2} . Найдите наименьшее возможное значение n.n .

Проверьте себя

00

Потренируйте навык

Все задания на этот навык

Решать