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

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

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

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

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

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

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

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

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

Задача 21#64854Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1

По определению, если выражение делится на m, то оно сравнимо с 0 (mod m)

Подсказка 2

С чем тогда сравнимо по модулю 13 число а? А с чем число b? Когда придет осознание, запишите сравнение по модулю 13 для ab-20cd, заменяя а и b на нужные выражения

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

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

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

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

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

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

Задача 22#64951Максимум баллов за задание: 7

Для какого наибольшего натурального числа $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

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

Задача 23#65617Максимум баллов за задание: 7

Сумма и произведение трёх попарно взаимно простых чисел делятся на 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, противоречие.

Ответ: нет

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

Задача 24#31493Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1

Очевидно, что напрямую мы это не вычислим, значит, нужно пользоваться сравнениями. Но с тройкой не очень приятно работать по модулю 10, как можно преобразовать 3^222 в более удобный вид?

Подсказка 2

3^222 = 9^111, а с девяткой уже приятнее работать по модулю 10.

Подсказка 3

Действительно, 9 ≡ -1 (mod 10), а значит 9^111 ≡ (-1)^111 (mod 10)

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

Заметим, что

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

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

−1 ≡109

Ответ:

$9$

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

Задача 25#31494Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1

Замените основания степеней на их остатки по модулю 7.

Подсказка 2

Да, получится сумма, где только двойки в степенях. Советуем выделить общий множитель :)

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

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$ очевидна.

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

Задача 26#31495Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1

В условии написано про делимость. Часто бывает, что вместо делимости удобнее использовать сравнения. Перепишите условие в терминах сравнений по модулю и подумайте, что после этого хочется сделать.

Подсказка 2

Сравнения, сравнения… страшно? мне тоже. А вот ДА на вебинарах говорил, что можно с некоторыми оговорками считать сравнения знаком равенства. Как бы вы решали эту задачу, если вместо сравнений написать везде равенства?

Подсказка 3

Выразите постепенно каждую переменную с помощью сравнений по модулю p через a и подставьте в то, что нужно доказать

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

Из условия: $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).$

Курсы

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

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

Задача 27#31496Максимум баллов за задание: 7

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

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

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

Подсказки к задаче

Подсказка 1

Если хотят делимость на 1993, то и модуль m будет равен 1993. Заметим, что 2 = 1993-1991, 4 = 1993-1989 ...

Подсказка 2

Да, будем заменять по модулю m 2 на -1991, 4 на -1989, действуя так, получим новое, очень похожее на 1991!! выражение (или равное ему?)

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

Заметим, что $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.$

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

Задача 28#31497Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1

Нам дали условие делимости на 11. Попробуем тогда понять что-нибудь о k, иначе совсем непонятно, как подобраться к задаче. Так как остатки у нас всегда зацикливаются, давайте узнаем, при какой степени двойки, число даст остаток 1.

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

Разберемся сначала, при каком условии на $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$ .

Ответ:

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

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

Задача 29#33969Максимум баллов за задание: 7

Найдите остаток от деления числа $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

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

Задача 30#34024Максимум баллов за задание: 7

Какие остатки может давать точный квадрат при делении на 5?

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

Как можно вычислить остаток точного квадрата, если мы знаем, например, остаток самого числа? Пусть остаток нашего числа при делении на 5 равен $r$ , то есть число имеет вид $5x +r$ , где $0≤ r< 5$ . Тогда квадрат имеет вид $2 2 2 2 2 (5x+ r) =25x + 10xr+ r = 5(5x + 2xr)+ r$ , то есть его остаток при делении на 5 равен остатку $2 r$ при делении на 5 (мы берем именно остаток от него, так как само $2 r$ может быть $≥5$ и не являться уже остатком). Осталось рассмотреть, какие остатки дают квадраты чисел 0, 1, 2, 3 и 4. Это, соответственно, 0, 1, 4, 4, 1.

Ответ: 0, 1, 4

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

Задача 31#34025Максимум баллов за задание: 7

Какие остатки может давать $5k$ при делении на 11?

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

Организуем такой процесс: начнем с первой степени, на каждом шаге будем отмечать остаток числа при делении на 11 и переходить к следующей степени, домножая число на на 5. Если на нынешнем шаге мы знаем, что остаток числа равен $r$ , то есть число имеет вид $11x+ r$ , то после домножения на 5 число будет иметь вид $11⋅5x +5r$ и, соответственно, остаток, равный остатку $5r$ при делении на 11 (так как оставшаяся часть и так делится на 11). То есть по факту мы просто каждый раз умножаем остаток на 5 и делим его на 11 с остатком.

Что получается?

$1 5$ имеет остаток 5 при делении на 11,

$2 5$ имеет остаток, равный остатку $5 ⋅5 =25$ при делении на 11, то есть 3,

$3 5$ — остаток 4 (остаток $3⋅5= 15$ при делении на 11),

$54$ — остаток 9 (остаток $4⋅5= 20$ при делении на 11),

$55$ — остаток 1 (остаток $9⋅5= 45$ при делении на 11),

$56$ — остаток 5 (остаток $1⋅5= 5$ при делении на 11).

Остановимся здесь и увидим, что мы снова получили остаток 5, то есть после него будут остатки 3, 4, 9, 1, 5,..., как и с самого начала. Почему мы можем так утверждать? Заметим, что каждый остаток на очередном шаге зависит ТОЛЬКО от предыдущего остатка (больше ни от чего другого, так как мы просто каждый раз домножаем на константу 5 и берем остаток при делении на константу 11). То есть, если какой-то остаток повторился, то мы уже знаем, какие остатки будут дальше, так как мы уже ходили по этому пути.

Значит, наши остатки зациклились, а весь цикл имеет вид: 5 — 3 — 4 — 9 — 1. Теперь мы даже можем узнать точный остаток какой-то очень большой степени 5, нужно только понять на какой остаток из цикла попадает эта степень. А наш ответ: дает остатки 5, 3, 4, 9, 1.

Ответ: 5, 3, 4, 9, 1

Интенсивы

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

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

Задача 32#36176Максимум баллов за задание: 7

Найдите количество пар натуральных чисел $(x,y)$ таких, что $1≤ x≤ 1000,1≤y ≤1000$ и $x2+y2$ делится на $5$ .

Подсказки к задаче

Подсказка 1

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

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

Всего у нас есть по $200$ чисел, дающих каждый из остатков $0,1,2,3,4$ при делении на $5$ . Квадраты чисел $0,1,2,3,4$ дают остатки $0,1,−1,− 1,1$ по модулю $5$ , мы хотим выбрать такие два из них, что их сумма будет $0$ . Отсюда возможны два случая:

а) числа $x,y$ оба кратны $5$

б) одно из чисел дает остаток $1$ или $4$ (и квадрат даст остаток $1$ ), а другое — $2$ или $3$ при делении на $5$ (то есть квадрат даст $− 1$ ).

В первом случае получаем $200 ⋅200= 40000$ вариантов, поскольку $x$ и $y$ независимо выбираются из множества ${5,10,...1000}$ . Во втором имеем $2⋅400⋅400 =320000$ способов, тут оба множества размера $400$ , а также важен остаток, который соответствует каждой переменной (есть $2$ способа выбрать, квадрат какой из них даст остаток $1$ ). Всего $40000+ 320000= 360000$ пар.

Ответ:

$360000$

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

Задача 33#37808Максимум баллов за задание: 7

Сколько существует натуральных чисел $n$ , меньших $10000$ , для которых $2n− n2$ делится на $7?$

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

Заметим, что $2n$ даёт только остатки $1,2,4$ по модулю $7$ для $n = 3k,3k+ 1,3k+ 2,k ∈ℕ ∪{0}$ соответственно.

Для $2 n$ имеем

2 n ≡7 1 при n ≡7 ±1

n2 ≡7 2 при n ≡7 ±3

n2 ≡ 4 при n ≡±2 7 7

По условию нам нужно $2n ≡ n2 7$

В качестве примера рассмотрим $2n ≡ n2 ≡ 1 7 7$ . Здесь накладываются два условия $n≡ 0,n≡ ±1 3 7$ . Уместно воспользоваться Китайской теоремой об остатках, которая говорит нам, что таких чисел будет ровно два в наборе ${1,2...21= 3⋅7}$ , но можно и явно найти эти числа — $15,6$ . Здесь легко видеть, что от сдвига набора ничего не поменяется, поскольку нам важно только наличие всех остатков по модулю $21$ ровно по одному разу.

Абсолютно аналогично по два числа в каждом наборе из $21$ подряд идущего подойдут для остатков $2$ и $4$ , то есть в итоге из каждых $21$ нам подойдут $6$ чисел.

Поскольку $10000= 476⋅21+4$ , то из первых $476$ групп подойдут $476⋅6$ . Остаются числа чисел $9997,9998,9999$ , из которых подходит $9998≡7 2$ . Получаем ответ

6⋅476+ 1= 2857

Ответ: 2857

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

Задача 34#41306Максимум баллов за задание: 7

Докажите, что для каждого натурального числа $n$ число

2n n+2 n 5 + 3 + 3

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

Источники: ОММО-2022, номер 1, (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

Какое слагаемое из этой суммы выбивается сильнее других? Как можно его исправить?

Подсказка 2

Сильнее других выбивается 5^2n. При этом мы рассматриваем выражение по модулю 11(так как хотим, чтобы на 11 делилось выражение). Как исправить 5^(2n), чтобы оно имело такой же вид, как и другие слагаемые?

Подсказка 3

Рассмотреть сравнение 5^2 = 3(mod 11). В таком случае можно возвести сравнение в степень n и подставить в изначальное выражение, то есть заменить 5^(2n) на выражение с тем же остатком по модулю 11

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

Первое решение.

Поскольку $2 5 ≡113$ , то по модулю $11$ имеем

n n n n 3 + 9⋅3 + 3 = 11⋅3 ≡11= 0

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Докажем утверждение задачи для целых неотрицательных $n$ индукцией по $n.$

База: Если $n =0,$ то $52n+ 3n+2 +3n =50+ 32+30 = 11$ — делится на $11.$

Переход: Предположим, что при $n = k$ число $52n +3n+2+ 3n = 52k+ 10⋅3k$ делится на $11,$ и докажем, что при $n= k+ 1$ число $52n+ 3n+2 +3n = 52k+2 +10⋅3k+1$ также делится на $11.$ Заметим, что

( ) 52k+2+10⋅3k+1 = 3⋅ 52k+ 10⋅3k + 22⋅52k

Первое слагаемое в правой части делится на $11$ по предположению индукции, а второе — потому что содержит множитель $22.$ Значит, и вся сумма делится на $11.$ Переход доказан.

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

Задача 35#72039Максимум баллов за задание: 7

Обозначим через $a n,m$ число, полученное записью подряд всех натуральных чисел от $n$ до $m,$ здесь $n$ и $m$ — натуральные числа, причем $n >m ≥ 1.$ Так, например, число $a4,2 =432,$ а число $a11,7 =1110987.$ Докажите, что среди таких чисел есть число, делящееся на $2022.$

Источники: Межвед-2022, 11.7 (см. www.academy.fsb.ru)

Подсказки к задаче

Подсказка 1

Наверное, конкретные m и n мы не предъявим, а нужно как-то построить их. Тогда полезно поискать какие-то свойства таких чисел. Подумайте, что мы можем сказать про разность a(m,1)-a(n,1)...

Подсказка 2

Из определения этих чисел следует, что это будет a(m,n+1)*10ⁿ. Тогда, если a(m,1)-a(n,1) поделится на 1011, то и a(m,n+1)*10ⁿ поделится на 1011. Найдутся ли такие m и n?

Подсказка 3

Найдутся! Действительно, если чисел a(k,1) бесконечно много, то существуют два числа a(m,1) и a(n,1) такие, что их остатки при делении на 1011 совпадают. Это значит, что a(m,n+1)*10ⁿ делится на 1011⇒a(m,n+1) делится на 1011. Осталось только придумать что-то с четностью. Когда число a(m,n+1)- четное?

Подсказка 4

Когда n- нечетное! Подумайте, сможем ли мы найти такую пару a(m,1) и a(n,1), где m и n- оба нечетные, и завершите решение!

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

Рассмотрим числа вида $a n,1$ , где $n$ — нечётное. Так как чисел указанного вида бесконечно много, то среди них найдутся два числа $a n,1$ и $ak,1,n> k,$ имеющие одинаковые остатки от деления на $2022.$ Тогда разность $an,1− ak,1$ делится нацело на $2022.$ При этом $n−k an,1 − ak,1 =an,k+1⋅10$ и число $an,k+1$ является чётным. Так как $2022 =2 ⋅1011$ и числа $1011$ и $n−k 10$ взаимно просты, то число $an,k+1$ делится нацело на $1011,$ а следовательно, и на $2022.$

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

Задача 36#72763Максимум баллов за задание: 7

Докажите, что если выражение $x2 +y2$ делится на $3,$ где $x$ и $y$ — целые, то $x$ и $y$ делятся на $3.$

Подсказки к задаче

Подсказка 1

Вспомните, какие остатки по модулю 3 может давать квадрат целого числа?

Подсказка 2

Только 0 или 1! А если сумма таких дает 0, то какими они могут быть?)

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

Если целое число $a$ дает остаток $0$ или $1$ при делении на $3,$ то и $a2$ тоже. Если же $a$ дает остаток $2$ при делении на $3,$ то его квадрат дает остаток $1$ при делении на $3.$ То есть квадраты целых чисел дают остатки $0$ и $1$ при делении на $3.$ Тогда если выражение $2 2 x + y$ делится на $3,$ то $x$ и $y$ делятся на $3.$

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

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

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

Задача 37#74789Максимум баллов за задание: 7

Клетки кубической таблицы $7× 7× 7$ (то есть маленькие кубики) пронумеровали по порядку числами от 1 до 343. (Сначала нумеруются клетки верхнего слоя: в первой строке слева направо от 1 до 7, в следующей от 8 до 14, и так далее до 49. Далее в таком же порядке нумеруются Клетки второго слоя и т. А.) После этого из таблицы удалили несколько непересекающихся кубов $2× 2× 2$ , а все оставшиеся числа сложили. Чему может равняться остаток от деления полученной суммы на 8 ?

Источники: ФЕ-2022, 11.6 (см. www.formulo.org)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Заметим, что сумма всех числе равна 8a+4*57. Что тогда можем сказать об изменении остатка от деления на 8?

Подсказка 3

Он либо сохраняет, либо изменяет остаток на 4!

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

Рассмотрим произвольный вырезаемый куб $2×2 ×2$ . Если наименьшее число обозначить $a$ , то остальные числа будут $a+ 1,a+7,a+ 8,a +49,a+49+ 1,a +49+ 7$ , $a+ 49 +8$ . Значит, их сумма $− 8a +4× 1+ 4× 7+4 ×49= 8a+ 4×57$ , то есть имеет остаток 4 от деления на 8. Значит, вырезание кубиков либо сохраняет суммарный остаток от деления на 8, либо изменяет его на 4. Осталось узнать, чему этот остаток равнялся изначально. Сумма чисел от 1 до 343 равна их среднему арифметическому $(1+343 ) 2 = 172$ на их количество 343. 172 делится на 4 , но не на 8 , а 343 нечётно, поэтому исходный остаток равен 4.

Ответ:

0 или 4

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

Задача 38#74951Максимум баллов за задание: 7

Пусть задано множество остатков от деления на 11, $A= {0,1,2,3,4,5,6,7,8,9,10}$ . Пусть над этим множеством задана степенная функция четвертой степени $($ т.е. все значения переменных и коэффициенты принадлежат только множеству $A)$

4 3 2 f(x)= x + 3x +7x + 6x+10

Найдите элемент множества $A,$ являющийся суммой корней уравнения $f(x)= 0.$

Источники: САММАТ-2022, 11.7 (см. sammat.samgtu.ru)

Подсказки к задаче

Подсказка 1

Остатков не так много, поэтому значения функции можно даже перебрать ;)

Подсказка 2

Приходим к тому, что корней всего 3 :)

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

Просто переберём остатки по модулю 11:

f(0)≡ 10⁄≡ 0mod 11

f(1)≡5 ⁄≡0 mod11

f(2)≡2 ⁄≡0 mod11

f(3)≡ 0mod 11

f(4)≡ 0mod 11

f(5)⁄≡ 0mod 11

f(6)⁄≡ 0mod 11

f(7)⁄≡ 0mod 11

f(8)≡ 0mod 11

f(9)⁄≡ 0mod 11

f(10) ⁄≡0 mod11

Итак, $f(3)≡0 mod11,f(4)≡ 0mod 11,f(8)≡ 0mod 11.$

Так как многочлен степени 4, то какой-то корень кратный. Убеждаемся, что

(x4+ 3x3 +7x2+ 6x +10)= (x − 3)(x − 4)2(x− 8) mod11

Значит, сумма равна

3+4 +4+ 8≡ 8mod 11

Ответ: 8

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

Задача 39#89283Максимум баллов за задание: 7

Докажите, что число $570+ 670$ делится на 61.

Источники: ОММО-2022, номер 1, (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

Может, стоит начать с чего-то малого, а не с семидесятой степени?

Подсказка 2

Попробуйте заменить семидесятую степень у наших чисел на вторую. Можно ли сделать какие-то выводы о их сумме?

Подсказка 3

Если бы у нас была вторая степень, то полученное число точно бы делилось на 61. Как это использовать, чтобы сравнить число 5⁷⁰ по модулю 61?

Подсказка 4

Для этого представим 5⁷⁰ как (5²)³⁵, 6⁷⁰ — как (6²)³⁵, а также вспомним, что 25 сравнимо с (-36) по модулю 61.

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

Заметим, что

25≡ −36 (mod 61)

Значит,

70 70 35 35 35 35 5 + 6 =25 +36 ≡ −36 + 36 =0 (mod 61)

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

Задача 40#135021Максимум баллов за задание: 7

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

Источники: ВСОШ, РЭ, 2022, 10.6 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Попробуйте в явном виде записать суммы этих остатков. Обозначьте остаток первого числа через r и посмотрите, что получится.

Подсказка 2:

Вероятно, вы столкнулись с проблемой, что в некоторых случаях остатки двух других чисел будут выглядеть r + 2 и r + 4, а в некоторых других — иначе. Разберите эти случаи отдельно.

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

Пусть $r$ — остаток меньшего из данных нечётных чисел при делении на 2022, так что $r$ — некоторое нечётное число множества ${1,3,5,$ …, $2021}.$ Если $r≤2017,$ то два других остатка — $r+2$ и $r+ 4,$ так что сумма остатков равна

r+ (r+2)+ (r+ 4)= 3(r+ 2).

Это число составное, так как делится на 3 и больше 3. Отдельно рассмотрим случаи $r =2019$ и $r=2021.$ В первом случае остатки данных чисел равны 2019, 2021 и 1. Во втором случае остатки данных чисел равны 2021, 1 и 3. В обоих случаях сумма остатков делится на 3 и больше 3.

Ответ:

не может