Тема ТЕОРИЯ ЧИСЕЛ

Остатки и сравнения по модулю → .01 Базовый аппарат сравнений по модулю

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела теория чисел

Разделы подтемы Остатки и сравнения по модулю

Базовый аппарат сравнений по модулю

Выбор модуля для доказательства делимости / простоты / степени

Малая теорема Ферма

Функция Эйлера и теорема Эйлера из ТЧ

Китайская теорема об остатках

Обратные остатки

Квадратичные вычеты

Показатели и первообразные корни

Лемма об уточнении показателя

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#85436

Даны простое число $p$ и три различных натуральных числа $a,b$ и $c$ таких, что $ab+ 3,bc+ 3,ac+ 3$ и $abc+ 11$ делятся на $p.$ Чему может быть равно $p?$

Показать ответ и решение

Давайте запишем условия на делимость в виде сравнений:

ab≡ −3 (mod p)

bc≡ −3 (mod p)

ac≡ −3 (mod p)

abc≡ −11 (mod p)

Теперь мы можем перемножить первые три сравнения и получить, что $(abc)2 ≡ −27 (mod p).$ Но из условия $(abc)2 ≡ 121 (mod p).$ Значит, $p$ является делителем числа $121 − (−27)= 148= 22⋅37,$ и может быть равен либо $2,$ либо $37.$ Для $p= 2$ можно взять просто три нечётных числа $a,b,c.$ А для $p =37$ существуют числа $a= 16,b= 16+37,c= 16 +37⋅2.$ Действительно, легко проверить, что все сравнения выполняются, потому что по модулю $37$ они равны $16,$ а $. 163+ 11 ..37.$

Ответ:

$p =2,p= 37$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#89214

Число $1001$ выписали на доску $1001$ раз подряд. Получили натуральное число $a.$ Найдите остаток от деления $a$ на $9999.$

Показать ответ и решение

Заметим, что это число можно записать в следующем виде:

0 4 8 4000 4 8 4000 1001⋅10 +1001⋅10 +1001⋅10 + ...+ 1001⋅10 = 1001(1+ 10 + 10 +...+10 )

Все слагаемые в скобке сравнимы с $1$ по модулю $9999,$ а значит скобка сравнима с $1001,$ то есть всё число сравнимо с $10012.$ Нетрудно посчитать, что $10012 ≡ 2101 (mod 9999).$

Ответ:

$2101$

Ошибка.
Попробуйте повторить позже

Задача 3#89281

Известно, что $a− 2b$ делится на $m$ и $c− 3d$ делится на $m$ . Докажите, что $ac− 6bd$ делится на $m$ .

Показать доказательство

По условию $a− 2b$ делится на $m$ и $c− 3d$ делится на $m.$ Тогда

a ≡2b (mod m)

c≡ 3d (mod m)

Воспользуемся свойством, что сравнения по одному модулю можно перемножить:

ac≡ 6bd (mod m )

Значит, что $ac− 6bd$ делится на $m.$

Ошибка.
Попробуйте повторить позже

Задача 4#89282

Докажите, что $(3n+ 1)n− 2$ делится на $3n− 2$ для любого натурального $n.$

Показать доказательство

Так как

n n 3 + 1≡ 3 (mod 3 − 2),

то

n n n n (3 +1) − 2 ≡ 3 − 2≡ 0 (mod 3 − 2)

Ошибка.
Попробуйте повторить позже

Задача 5#89284

Известно, что $abc+1$ делится на $ab− b+ 1$ . Докажите, что $ac− a+1$ и $bc− c+1$ — тоже.

Показать доказательство

Заметим, что

ab− b+ 1≡ 0 (mod ab − b+ 1)

ab≡ b− 1 (mod ab− b+1)

Значит, раз $abc+ 1$ делится на $ab− b +1,$ то

abc+ 1≡ 0 (mod ab − b+ 1)

(b− 1)c+ 1≡0 (mod ab− b+1)

bc − c+ 1≡ 0 (mod ab− b+ 1)

Следовательно, $bc− c+ 1$ делится на $ab− b+ 1,$ а также

bc≡ c− 1 (mod ab− b+1)

Благодаря этому получаем

abc+ 1≡ 0 (mod ab − b+ 1)

a(c− 1)+ 1≡ 0 (mod ab− b+1)

ac − a+ 1≡ 0 (mod ab− b+ 1)

Следовательно, $ac − a+ 1$ делится на $ab− b+1.$

Ошибка.
Попробуйте повторить позже

Задача 6#89285

Докажите, что $11n+2 +122n+1$ делится на 133 при любом натуральном $n$ .

Показать доказательство

Заметим, что

2 2 12 ≡11 (mod 133) и 11 ≡− 12 (mod 133)

Тогда

n 2 2n n n 11 ⋅11 +12 ⋅12≡ −12⋅11 +12⋅11 = 0 (mod 133)

Значит, $11n+2+ 122n+1$ делится на 133.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#90281

Вася хочет заполнить квадратную таблицу (криптографическую мозаику) размера $4× 4$ целыми числами от 1 до 16 по следующему правилу. Сначала он выбирает четыре целых числа $b1,b2,b3,b4 ∈{0,1,...,16}$ . Затем первую строку Вася заполняет числами

(1) ai ≡ (bi+1)(mod17), i=1,2,3,4;

вторую строку — числами

(2) ai ≡ (bi+4)(mod17), i=1,2,3,4;

третью

(3) ai ≡(bi+13)(mod17), i= 1,2,3,4

и, аналогично, четвертую

(4) ai ≡ (bi+ 16)(mod17), i=1,2,3,4.

При этом числа $b1,b2,b3,b4$ Вася выбрать должен так, чтобы все числа в таблице оказались различными. Сумеет ли Вася это сделать? Если да, то чему равны $b1,b2,b3,b4$ ?

Источники: Верченко - 2024, 11.6 (см. ikb.mtuci.ru)

Показать ответ и решение

Заметим, что

bi+16= bi+1(mod17)

bi+13= bi− 4(mod17)

Представим остатки полученных $a(ij)$ от $bi$ в виде круга остатков. Числа получаются от $bi$ смещением на $1$ или $4$ шага по часовой или против часовой стрелки в зависимости от знака.

Крестиком выделены полученные числа a(j)то есть столбец в табл&#x0438 i i

$PIC$

Заметим, что важен лишь набор $b1,b2,b3,b4$ , а не их порядок, тогда без ограничения общности выберем пару $b1$ , $b2$ — одно из чисел $(j) a1$ или такое число, которого нет в таблицы. Докажем, что $b2$ тогда обязательно соседняя с $b1$ .

Предположим противное, то есть что ни одна пара $bi$ , $bj$ не являются соседями (так как иначе можем взять их в качестве $b1$ , $b2$ ).

$1$ случай ( $b2 = b1+4(mod 17)$ ): возьмём $b1 =6$ (если все различные числа сдвинуть на одинаковое число по модулю $17$ , то они останутся одинаковыми, а значит мы можем взять $b1 =6$ ), в таблицу уже попали числа: $1,2,3,5,6,7,10,15$ , тогда “запрещённые” позиции — $0,..,11,14,15,16$ (они получены путём прибавления и вычитания $1$ , $4$ по модулю $17$ к полученным клеткам в таблице), а значит, $b3,b4$ — $12,13$ , но тогда они соседи — противоречие.

$2$ случай ( $b2 = b1− 4(mod 17)$ ): переименуем $b1$ , $b2$ в $b2$ , $b1$ и получится случай 1.

$PIC$

$3$ случай ( $b2 = 6$ аналогично, без ограничения общности, не входит в таблицу): Все остальные числа входят, так как с каждой $bi$ в таблицу добавляются по 4 числа. Рассмотрим число $3$ , у нас уже "запрещены"числа $2,5,7,10$ для $b1$ , иначе $b2$ входит в таблицу и $1,3,4,6,8,9,11,15$ , иначе в таблице есть повторяющиеся числа, тогда $b1+ 1!= 3(mod 17)(b1 = 2),b1− 1!= 3(mod 17)(b1 =4),b1− 4!=3(mod 17)(b1 = 7)$ , получается, что $b2+ 4= 3(mod 17)$ , т.е. $b2 = 16)$ .

Посмотрим на “запрещённые” числа для $b3$ : $0,..,12,15,16$ , но $13,14$ снова соседние.

Мы получили, что обязательно должны быть 2 соседних числа. С одной стороны, зачёркнутые ячейки на расстоянии $4$ от $b1$ и $b2$ образуют место для $b 3$ и $b 4$ (поскольку есть две свободные ячейки вокруг двух зачеркнутых чисел). С другой стороны, при выборе двух $b$ , набор двух оставшихся определяется однозначно, поэтому итого вариантов выбора комбинации столько же, сколько и выбор двух подряд идущих чисел в круге, т.е. $17$ .

Один из возмож ных случаев:

$PIC$

Ответ:

$0 1 7 11, 1 2 8 12, 2 3 9 13, 3 4 10 14, 4 5 11 15, 5 6 12 16, 0 6 7 13, 1 7 8 14, 2 8 9 15, 3 9 10 16, 0 4 10 11, 1 5 11 12, 2 6 12 13, 3 7 13 14, 4 8 14 15, 5 9 15 16, 0 6 10 16$

Ошибка.
Попробуйте повторить позже

Задача 8#96954

Найдите все целые $b$ такие, что при любом натуральном $a$ число $(a2+ 1)100 +b− a$ делится на $a2+ a+1.$

Показать ответ и решение

Заметим, что $a2+1$ сравнимо с $− a$ по модулю $a2+ a+ 1,$ а значит, $(a2+1)100+ b− a$ сравнимо с

100 100 99 (−a) + b− a= a + b− a =a(a − 1)+ b

Заметим, что $a99 − 1$ делится на $a3− 1= (a − 1)(a2+ a+ 1).$ То есть необходимое и достаточное условие — делимость $b$ на $a2+ a+ 1$ для любого натурального $a,$ что возможно лишь при $b= 0.$

Ответ:

$b= 0$

Ошибка.
Попробуйте повторить позже

Задача 9#105466

Натуральные числа $a,b,c$ таковы, что $ab− cd$ делится на $a +b+ c+ d.$ Докажите, что $a+ b+ c+d$ — составное.

Показать доказательство

Предположим противное, тогда число

p =a +b+ c+ d — простое

и имеет место сравнение

d≡ −(a+ b+c) (mod p)

Из условия получим сравнение

ab≡ cd (mod p)

следовательно,

ab≡ −c(a+b+ c) (mod p)

что после преобразование равносильно

(a+ c)(b+ c)≡ 0 (mod p)

но тогда по крайней мере одно из чисел $a+ c< p$ и $b+c< p$ делится на $p,$ что влечет противоречие.

Ошибка.
Попробуйте повторить позже

Задача 10#105467

(a) Известно, что $2 2 (4a − 1)$ делится на $4ab − 1.$ Докажите, что $2 (a− b)$ — тоже.

(b) Известно, что $n3+ 1$ делится на $mn − 1.$ Докажите, что $m3+ 1$ — тоже.

Показать ответ и решение

(a) Перепишем условие на делимость в виде сравнения и домножим обе части на $2 b$

2 2 2 b(4a − 1) ≡ 0 (mod 4ab− 1)

Заметим, что $4ab≡1 (mod 4ab− 1),$ следовательно,

2 2 2 2 2 2 0≡ b(4a − 1) ≡ (4a b− b) ≡ (a − b) (mod 4ab− 1)

что влечет требуемое.

(b) Перепишем условие на делимость в виде сравнения и домножим обе части на $m3$

3 3 m (n + 1)≡0 (mod mn − 1)

Заметим, что $mn ≡ 1 (mod mn − 1),$ следовательно,

0≡ m3(n3+ 1) ≡(mn)3+ m3 ≡ 1+ m3 (mod mn − 1)

что влечет требуемое.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 11#61484

Пусть $a$ и $b$ - целые числа. Докажите, что если $a2+ 9ab+ b2$ делится на $11$ , то и $a2 − b2$ делится на $11.$

Показать ответ и решение

Так как выражение из условия делится на $11$ , то после вычитания из него $11ab$ получится кратное $11$ число.

2 2 2 a + 9ab− 11ab+b = (a− b)

Итак, $(a− b)2$ кратно $11$ , откуда $a− b$ также делится на $11$ , поскольку это число простое. Остаётся заметить, что $a2− b2 = (a− b)(a+ b)$ кратно $a − b$ , потому также кратно $11$ .

Ответ:

что и требовалось доказать

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#64854

Известно, что $a+ 5c$ и $b+ 4d$ делятся на $13.$ Докажите, что $ab− 20cd$ делится на $13.$

Показать доказательство

Перепишем через сравнения по модулю и перемножим равенства

({ a ≡ −5c 13 =⇒ ab ≡20cd⇐⇒ ab− 20cd ≡ 0 ( b ≡13−4d 13 13

Ошибка.
Попробуйте повторить позже

Задача 13#64951

Для какого наибольшего натурального числа $n$ число $n3+ 20n2 − 25n− 2025$ делится на число $n+ 10?$

Показать ответ и решение

Заметим, что $n ≡ −10. n+10$ Тогда

3 2 3 2 n +20n − 25n − 2025n≡+10(− 10) + 20 ⋅(−10) − 25⋅(−10)− 2025= −775

Получается, что $( ) n3+ 20n2− 25n− 2025 + 775$ всегда делится на $n+ 10$ .

По условию $n3+ 20n2− 25n− 2025$ делится на $n+ 10$ , а значит, $775$ делится на $n+ 10,$ откуда $775 ≥n +10$ , а наибольшее натуральное $n$ равно $775− 10= 765.$

Ответ: 765

Ошибка.
Попробуйте повторить позже

Задача 14#65617

Сумма и произведение трёх попарно взаимно простых чисел делятся на 13. Может ли их сумма квадратов также делиться на 13?

Показать ответ и решение

Преположим, что числа $x,y,z$ удовлетворяют условию и сумма их квадратов кратна 13. Так как 13 — простое, то хотя бы одно из этих чисел кратно 13, но по условию они попарно взаимно просты, значит, только одно число делится на 13. Пусть это число $z.$ Тогда $x +y1≡30$ , откуда $x ≡13−y.$ Тогда:

2 2 2 2 2 x + y ≡13 (−y) + y =2y ≡130

Получили, что $y$ тоже делится на 13, противоречие.

Ответ: нет

Ошибка.
Попробуйте повторить позже

Задача 15#31493

Найдите остаток числа $3222$ при делении на $10$ .

Показать ответ и решение

Заметим, что

222 111 111 3 = 9 ≡10(− 1) = −1

Осталось не забыть, что остаток при делении на 10 это целое число от 0 до 9:

−1 ≡109

Ответ:

$9$

Ошибка.
Попробуйте повторить позже

Задача 16#31494

Докажите, что при любом натуральном $n$ число $37n+2 +16n+1+ 23n$ делится на $7.$

Показать доказательство

n+2 n+1 n n+2 n+1 n 37 + 16 +23 ≡ 2 + 2 +2 (mod 7)

Осталось заметить, что $2n+2 +2n+1+ 2n = 7⋅2n,$ теперь делимость на $7$ очевидна.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#31495

Дано простое число $p$ и такие целые числа $a,b,c,d,e,$ что числа $a2− b,a3− c,c5− d,b7− e$ делятся на $p.$ Докажите, что и число $ae− d$ делится на $p.$

Показать доказательство

Из условия: $b≡a2 (mod p),c≡ a3 (mod p),d≡ c5 ≡ a15 (mod p),e≡ b7 ≡ a14 (mod p).$ Тогда $ae− d≡ a⋅a14− a15 ≡ 0 (mod p).$

Ошибка.
Попробуйте повторить позже

Задача 18#31496

Докажите, что число

2⋅4⋅6⋅8⋅...⋅1990⋅1992− 1 ⋅3 ⋅5 ⋅7 ⋅...⋅1989⋅1991

делится на $1993.$

Показать доказательство

Заметим, что $2≡ −1991 (mod 1993),4≡ −1989 (mod 1993),...,1992≡ −1 (mod 1993),$ то есть остатки чисел из первого произведения такие же, как числа из второго произведения, а отличаются лишь знаком. Но в этом произведении чётное количество чисел ( $1992 2$ ), поэтому выражение из условия даёт остаток $19292 (− 1) ⋅1 ⋅3 ⋅...⋅1991− 1⋅3⋅...⋅1991= 0$ по модулю $1993,$ то есть делится на $1993.$

Ошибка.
Попробуйте повторить позже

Задача 19#31497

Докажите, что если $2k − 1$ делится на $11$ , то оно делится и на $31$ .

Показать ответ и решение

Разберемся сначала, при каком условии на $k$ выражение $2k− 1$ делится на $11$ . Посмотрим, как зацикливаются степени двойки при делении на $11$ .

21 ≡ 2 (mod 11) 26 ≡ −2 (mod 11) 2 7 23≡ 4 (mod 11) 28≡ −4 (mod 11) 24≡ 8 (mod 11) 29≡ −8 (mod 11) 25 ≡ 5 (mod 11) 2 ≡10 −5 (mod 11) 2 ≡− 1 (mod 11) 2 ≡ 1 (mod 11)

Тогда следующая степень $211$ вновь даст остаток $2$ по модулю $11$ , и остатки зациклятся, так как каждый следующий остаток однозначно определяется предыдущим. Таким образом, чтобы $2k − 1$ делилось на $11$ , то есть $2k$ было сравнимо с 1 по модулю $11$ , $k$ должно делиться на $10$ .

Теперь докажем делимость того же выражения и на 31. Заметим, что $5 2 = 32≡ 1 (mod 31)$ . И так как $.. k.10$ , то при некотором целом $n$ имеем равенство $k= 10n$ , значит, $k 10n 2n 2n 2 = 2 =32 ≡ 1 ≡ 1 (mod 31)$ , откуда и следует делимость исходного выражения на $31$ .

Замечание. Опять же, рассуждения последнего абзаца при желании можно заменить честным поиском цикла двойки по модулю $31$ .

Ответ:

что и требовалось доказать

Ошибка.
Попробуйте повторить позже

Задача 20#33969

Найдите остаток от деления числа $21000$ на 9.

Показать ответ и решение

Как решать подобные задачи? Рассмотрим, какие остатки дают первые несколько степеней.

21 ≡2 (mod 9) 24 ≡ 7 (mod 9) 22 ≡4 (mod 9) 25 ≡ 5 (mod 9) 3 6 2 ≡8 (mod 9) 2 ≡ 1 (mod 9)

Легко видеть, что следующая степень $27$ снова сравнима с 2 по модулю 9. Итак, впервые некоторый остаток повторился. На самом деле после этого все остатки зацикливаются, и после 2 снова будет 4, 8, 7, 5, 1, 2, и т. д. Почему так происходит? Дело в том, что следующий остаток однозначно определяется предыдущим. Значит, если ранее после остатка 2 шел остаток 4, то и сейчас после 2 мы получим остаток 4.

Тем самым мы получили цикл остатков: 2, 4, 8, 7, 5, 1. Поэтому достаточно посчитать, какой номер будет у числа 1000 в данном цикле. А для этого достаточно заметить, что, раз цикл имеет длину 6, то все зависит от того, какой остаток дает число 1000 при делении на 6. Нетрудно посчитать, что этот остаток равен 4. Значит, число 1000 будет четвертым по номеру в этом цикле, таким образом, $1000 2$ дает остаток 7 при делении на 9.

Ответ

Искомый остаток равен 7.

Ответ: 7

Следующая подтема