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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Три простые числа $p,q$ и $r$ больше трех и удовлетворяют условию $2p+ 5q = r.$ Для какого наибольшего $n$ число $p+q+ r$ всегда будет делиться на $n?$

Источники: СПбГУ - 2025, 11.3(см. olympiada.spbu.ru)

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

Подсказка 1

Чтобы угадать ответ, попробуйте записать число p + q + r, используя равенство из условия.

Подсказка 2

Скорее всего, вы поняли, что работать надо с делимостью на 3. Быть может, повезёт и даже с девяткой получится.

Подсказка 3

Рассмотрите варианты остатков p и q при делении на 3. Чтобы доказать, что больше 9 нельзя, подберите два примера, чтобы НОД значений p + q + r был 9.

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

Покажем, что $p+ q+ r$ всегда делится на $9.$ Действительно, по условию $2p+ 5q =r,$ поэтому

p +q+ r= 3p+6q = 3(p+2q)

Заметим, что

2p+ 5q = 2(p+ q)+3q

поэтому если $p$ и $q$ дают остатки $1$ и $2$ от деления на три, то $2p+ 5q$ делится на три и больше трех, поэтому $r$ не может быть простым числом. Значит, $p$ и $q$ дают одинаковые остатки от деления на три. Тогда $p+ 2q$ делится на три, а, значит, $p+q+ r$ делится на $9.$

Подберем две различных тройки простых: если $p =11$ и $q = 5,$ то $r= 2p+5q = 47$ — простое число и $p+q+ r= 63.$ Если $p= 17$ и $q = 5,$ то $r= 2p+ 5q =59$ — простое число и $p+ q+r =81.$ Поэтому для чисел из условия задачи $p+ q+r$ гарантированно может делиться только на $Н ОД(63,81)=9.$

Ответ:

$9$

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

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

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

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

Найдите все такие пары целых чисел $m$ и $n >2$ , что $((n − 1)!− n)⋅(n− 2)!= m(m − 2).$

Источники: Всеросс, 2025, РЭ, 9.5 (см. olympiads.mccme.ru)

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

Подсказка 1:

Давай заметим, что в правой части равенства почти полный квадрат. Не хватает 1. Давайте добавим её слева и справа.

Подсказка 2:

Также хотелось бы разложить на скобочки левую часть, притом желательно на взаимно простые. Если не получается угадать разложение, рассмотрите выражение слева как квадратный трёхчлен относительно (n-2)!.

Подсказка 3:

Итак, вы получили равенство ((n - 1)! - 1)((n - 2)! - 1) = (m - 1)². Являются ли скобки в левой части взаимно простыми?

Подсказка 4:

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

Подсказка 5:

Теперь осталось показать, что при больших n какая-то из скобок не сможет быть большим квадратом. Учитывая особенности факториалов, стоит подумать про остатки. Например, при делении на 4 квадраты могут иметь далеко не все остатки.

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

Заметим, что

((n − 1)!− 1)((n− 2)!− 1)=(n− 1)!⋅(n− 2)!− (n− 1)!− (n− 2)!+1 =

2 2 ((n− 1)!− n)⋅(n − 2)!+ 1= m − 2m +1 =(m − 1) .

Пусть $n> 4.$ Заметим, что числа $(n − 1)!− 1$ и $(n− 2)!− 1$ взаимно просты. Предположим, что это не так, и оба этих числа делятся на простое число $p.$ Тогда число

(n− 1)!− 1− ((n− 2)!− 1)⋅(n− 1)= n− 2

тоже делится на $p.$ Тогда $(n− 2)!$ делится на $p,$ а $(n− 2)!− 1$ не кратно $p,$ противоречие. Таким образом, произведение взаимно простых чисел $(n − 1)!− 1$ и $(n− 2)!− 1$ —– точный квадрат, тогда и каждое из них точный квадрат. Однако, число $(n − 1)!− 1$ при $n >4$ даёт остаток 3 при делении на 4, поэтому оно точным квадратом быть не может. Остаётся разобрать случаи $n ≤ 4.$ При $n= 4$ получается $(m − 1)2 = 5,$ решений нет. При $n =3$ мы получаем: $(m − 1)2 = 0,$ что даёт единственное решение $m = 1$ , $n =3.$

Ответ:

$m = 1,n = 3.$

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

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

Найти все натуральные числа $n ≥3$ такие, что для любого целого числа $m ≥0$ существуют $n$ целых чисел $x,...,x 1 n$ таких, что $x1+ ⋅⋅⋅+ xn = 0$ и $x1x2+ x2x3+⋅⋅⋅+$ $xn−1xn+ xnx1 = −m.$ Среди чисел $x1,...,xn$ могут быть совпадающие.

Источники: Всесиб - 2025, 10.4 ( см. sesc.nsu.ru)

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

Подсказка 1

Давайте попробуем пойти снизу-вверх. Что, если n = 3?

Подсказка 2

Попробуйте обозначить x₁, x₂ и x₃. Какими должны быть это обозначения, чтобы x₁ + x₂ + x₃ = 0?

Подсказка 3

Например, x₃ = - x₁ - x₂.

Подсказка 4

Попробуйте посмотреть на остатки от деления.

Подсказка 5

Быть может, с n = 4 нам подойдут аналогичные иксы?

Подсказка 6

Попробуйте увидеть полный квадрат.

Подсказка 7

Кажется, что с n = 5 противоречий не находится. Может, стоит попробовать придумать пример в общем виде?

Подсказка 8

Нам бы хотелось, чтобы сумма попарных произведений по циклу равнялась -m... То есть, вероятно, m должно быть среди иксов.

Подсказка 9

А давайте вспомним пример для n = 3.

Подсказка 10

Чтобы он работал и для n = 4, можно, например, докинуть 0.

Подсказка 11

А можем ли мы при помощи 0 доказать, что и для n ≥ 5 условия выполняются?

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

Пусть $n =3.$

Положим $x1 = a,x2 =b,x3 = −a− b,$ тогда

x1x2+ x2x3+ x3x1 =ab− b(a +b)− a(a+ b) =

2 2 = −a − b − ab= −m

m = a2+ b2+ ab= (a − b)2+3ab

Из последнего равенства следует, что остаток от деления числа $m$ на 3 совпадает с остатком от деления $(a − b)2$ на 3, а он может быть равен только 0 и 1. Следовательно, числа $− m$ для всех $m,$ дающих при делении на 3 остаток 2, не могут быть представлены требуемым в условии образом, поэтому $n =3$ не подходит.

Пусть $n= 4.$

Положим $x1 = a,x2 =b,x3 = c,x4 = d= −a − b− c.$ Тогда

ab+bc+ cd +da= (a+c)(b+ d)=

=− (a +c)2 =− m

m =(a+ c)2

Следовательно, в требуемом в условии виде представляются только те числа $− m,$ для которых $m$ является точным квадратом, поэтому случай $n = 4$ тоже нам не подходит.

Пусть $n≥ 5$

Для произвольного $m ≥ 0$ рассмотрим $n$ целых чисел:

{− m;1;0;m − 1;0;0;...;0}

Их сумма равна 0, а сумма попарных проиведений по циклу равна $− m,$ следовательно, любое $n≥ 5$ удовлетворяет условию задачи.

Ответ:

$n ≥5$

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

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

Докажите, что для каждого натурального $a >1$ существует простое $p$ такое, что число $1+ a+ a2+ ...+ap−1$ — составное.

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

Заметим, что для $a= 2$ подойдет $p= 11,$ действительно:

0 1 10 2 +2 + ...+ 2 = 2047=23⋅89.

Далее $a >2.$

Выберем в качестве $p$ простой делитель числа $a− 1>1.$ Тогда:

1+a +a2+ ...+ ap−1 ≡1 +1+ ...+ 1≡ 0 (mod p). ◟----◝◜p----◞

Значит, наше число кратно $p,$ осталось лишь показать, что это число больше $p.$ Это действительно так, поскольку $a$ уже больше $p.$

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

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

Докажите, что для каждого натурального $n$ число $11⋅14n+ 1$ — составное.

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

Заметим, что $14 ≡− 1 (mod 15),$ поэтому

n n 11⋅14 + 1≡ 11 ⋅(−1) + 1 (mod 15)

Если $n$ чётное, то $(−1)n = 1,$ и выражение сравнимо с $12 (mod 15),$ то есть делится на 3.

Если $n$ нечётное, то $(−1)n =− 1,$ и выражение сравнимо с $− 10 ≡5 (mod 15),$ то есть делится на 5.

Так как при любом $n$ значение $11⋅14n+ 1> 5,$ то делимость на 3 или 5 означает, что оно составное.

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

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

Найдите все пары натуральных чисел $(a,b)$ такие, что $aa +bb$ делится на $ab⋅ba.$

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

Если $a =b,$ то $2aa$ делится на $aa⋅aa,$ то есть $2$ делится на $aa.$ Это возможно только при $a =1.$

Пусть теперь числа не равны, и не умаляя общности, $a> b.$ Тогда $a a$ делится на $b a ,$ значит, $b b$ должно делиться на $b a ,$ но $b b b < a.$ Противоречие.

Ответ:

$(1,1)$

Курсы

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

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

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

Докажите, что не существует натурального $a$ такого, что

2023 2023 (2a +1) − a(2+ a)

является простым.

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

Подсказка 1.

Как можно проверять, что число не является простым?

Подсказка 2.

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

Подсказка 3.

Правильно! Давайте проверять делимость на многочлены первой степени от a! Попробуйте перебрать самые простые из них и понять, делится ли наш исходный многочлен на них.

Подсказка 4.

На самом деле наш многочлен делится на a + 1 и a − 1. К сожалению, задача пока не решилась. Какое условие на a позволит нам сказать, что мы решили задачу? А остальные a переберём и проверим прямой подстановкой.

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

Докажем, что

2023 2023 (2a +1) − a(2+ a)

делится на $a+ 1$ в смысле делимости многочленов от $a.$ Поскольку $a ≡a+1 −1$ имеем

2023 2023 (2a+ 1) − a(2+ a) ≡a+1 − 1+1 ≡a+1 0

Аналогично можно показать, что исходный многочлен делится и на $a− 1.$ Таким образом, единственный случай, когда наше число является простым, возможен лишь при $a− 1≤ 2,$ то есть при $a= 2$ или $a =3.$ При $a= 3$ число

(a− 1)⋅(a+ 1)=8,

поэтому исходное число не является простым. Пусть $a= 2.$ Тогда исходное число равно

52023 − 2⋅42023,

а, с другой стороны, оно должно быть равно 3. Ясно, что это не так, поскольку

52023 > 3+ 2⋅42023.

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

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

(a) Докажите, что многочлен $4 3 2 x + 3x + 2x + 3x− 1$ не делится на многочлен $2 x +1.$

(b) Найдите все целые $x,$ при которых число $4 3 2 x + 3x +2x + 3x− 1$ делится на $2 x +1.$

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

(a) Заметим, что $x2 ≡ −1. x2+1$ Следовательно,

4 3 2 2 2 2 2 x +3x + 2x +3x− 1= x ⋅x + 3x ⋅x +2x + 3x +1 ≡x2+1 −2.

Откуда и следует утверждение.

(b) Как мы поняли в пункте (a), остаток от деления равен $− 2.$ Поэтому хотим найти $x$ такое, что $− 2$ делится на $x2+ 1.$ Это возможно только при $x∈ {0,1,−1}.$

Ответ:

(b) $x =0;±1$

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

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

Существует ли непостоянный многочлен с целыми коэффициентами, значения которого во всех целых точках являются простыми числами?

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

Предположим, что такой многочлен существует. Обозначим его через $P(x).$ Тогда $P (n)= p$ для некоторого целого $n$ и простого $p$ (возьмём $n$ составным). Заметим, что тогда

P(n+ pk) ≡p P(n)≡p 0, ∀k∈ℕ.

Следовательно, $P(n +pk)= p$ для любого натурально $k,$ так как другого простого числа, которое делится на $p,$ не существует. В силу непостоянности многочлена, он не может принимать в бесконечном количестве точек одно значение. Противоречие.

Ответ:

нет

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

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

Найдите все простые числа $p,$ для которых существуют натуральные числа $a,$ $b$ и $c$ такие, что $(a+ 2b)(b+2c)(c+ 2a)$ является натуральной степенью числа $p.$

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

Подсказка 1:

Из такой делимости следует, что как минимум каждая из скобок делится на p. Что с этим можно сделать?

Подсказка 2:

Но тогда можно рассмотреть, например, сумму выражений в скобках, она тоже будет делиться на p. Она равна 3(a + b + c), возникает два случая.

Подсказка 3:

Интереснее всего случай, когда a + b + c делится на p. То есть теперь есть четыре выражения, кратных p. Попробуйте как-нибудь повычитать их друг из друга, чтобы получить новые выражения, кратные p.

Подсказка 4:

Например, (a + 2b) – (a + b + c) = b – c кратно p. Если рассмотреть аналогичные разности с другими скобками, получится, что все переменные имеют одинаковый остаток при делении на p. Если p не делится на 3, то a, b, c кратны p. Как насчет того, чтобы каждую из них поделить на p?

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

Будем считать, что одно из чисел не делится на $p,$ иначе можно сократить на $p.$ По условию каждая из скобок делится на $p.$ Тогда их сумма

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

Если $p⁄= 3,$ то

a+ b+ c≡ 0 (mod p)

Вычитая из первой скобки, получаем $b− c ≡0 (mod p).$ Из второй скобки получаем $c− a ≡0 (mod p).$ Тогда все три числа делятся на $p,$ противоречие. При $p= 3$ подойдут $a= b=c =1.$

Ответ:

$3$

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

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

Дано натуральное $n >1.$ Докажите, что существуют $n$ натуральных чисел таких, что произведение любых $n− 1$ из них даёт остаток $1$ при делении на оставшееся число.

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

Положим $a = 2,a = 3,a =a a ...a + 1 1 2 k 1 2 k−1$ при $3 ≤k <n$ и, наконец, $a = aa ...a − 1. n 12 n−1$ Тогда $aa ...a ≡1 (mod a ) 12 n−1 n$ очевидным образом. Рассмотрим члены нашей последовательности по модулю $ak$ при $k< n.$ Если $k< j < n,$ имеем $aj ≡ 1 (mod ak),$ а $an ≡− 1 (mod ak).$ Поэтому

a1a2...ak−1ak+1...an ≡ −a1a2...ak− 1 ≡ −(− 1) ≡1 (mod ak)

что и требовалось.

Интенсивы

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

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

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

Натуральные числа $a$ и $b$ таковы, что $ab+ 1$ делится на $b+2.$ Докажите, что $2a> b.$

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

Подсказка 1

Подумайте, за счëт чего одно натуральное число может быть больше другого.

Подсказка 2

Вот пусть у нас есть два натуральных числа x и y такие, что x делится на y. Что вы можете сказать про них? Какое из них не меньше другого?

Подсказка 3

Если применять предыдущие подсказки к задаче, то становится ясно, что нужно доказать некоторую делимость, из которой будет следовать, что 2a > b. Попробуйте рассмотреть число ab+1 по модулю b + 2. Что можно про него сказать, с какими числами оно сравнимо?

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

Заметим, что $b≡ −2 (mod b+2),$ откуда $ab+ 1≡ −2a+ 1 (mod b+2).$ Значит, $2a− 1$ кратно $b+2,$ откуда $2a− 1 ≥b+ 2,$ то есть $2a≥ b+ 3> b,$ что и требовалось.

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

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

Даны натуральные числа $a,b,c.$ Оказалось, что $b2+ c2− a2$ делится на $a+ b+ c.$ Докажите, что $a+ b+ c$ — составное.

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

Подсказка 1:

Попробуйте рассуждать от противного, пусть a + b + c - простое, поищите противоречие. Подумайте, каким оно может быть в этой задаче.

Подсказка 2:

Вспомним известный факт. Если некоторое число mn делится на простое число p, то либо m кратно p, либо n. Попробуйте получить подобную делимость, используя условие.

Подсказка 3:

Если оба числа m и n будут меньше p, то делимость будет невозможна. Попробуйте найти такое число mn, делящееся на a + b + c, и вы решите задачу.

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

Вспомним известное тождество $(a+ b+c)2 = a2+b2+ c2 +2(ab+bc+ ac).$ Перепишем его в следующем виде:

2 2 2 2 2 (a+b+ c) =b + c − a + 2(ab+ bc+ac+ a)

Числа $(a+ b+ c)2$ и $b2+c2− a2$ делятся на $a+ b+c,$ а значит, и число $2(ab+bc+ ac+a2)$ также будет делиться на $a+ b+ c.$ Заметим, что

2 2(ab+ bc+ ac+a )= 2(a +c)(a+ b)≡2bc (mod a+b+ c)

То есть $2bc$ делится на $a+ b+ c.$

Предположим, что $a+ b+ c$ — простое. Тогда есть $3$ случая:

$1)2$ кратно $a+ b+ c,$ но тогда $2= a+ b+ c,$ что невозможно, потому что $a+ b+ c≥ 3,$ потому что числа натуральные.

$2)b$ кратно $a+ b+c,$ что также невозможно, потому что $b< a+ b+ c.$

Аналогично разбирается случай, когда $c$ кратно $a+ b+ c.$

Пришли к противоречию, значит, $a+ b+ c$ — составное.

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

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

Докажите, что существует лишь конечное число натуральных $n,$ для которых $10n10+ 9n9+...+2n2+ n+ 1$ делится на $n − 10.$

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

Подсказка 1

Попробуйте рассмотреть задачу попроще. Докажите, что существует конечное количество натуральных n таких, что 10 кратно n - 10. Это очевидно, так как 10 конкретное число, оно имеет лишь конечное число делителей.

Подсказка 2

Посмотрите на многочлен из условия по модулю n - 10. Подумайте, с чем он сравним. Возможно, он сравним с каким-то конкретным числом, тогда задача станет похожа на задачу из подсказки 1.

Подсказка 3

Ясно, что если мы найдем остаток при делении n на n - 10, то мы найдем и остаток при делении многочлена n - 10. Чему он равен?

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

Обозначим многочлен $10n10 +9n9+ ...+ 2n2 +n +1$ через $f(n).$ Ясно, что $n≡ 10 (mod n− 10).$ Значит, $f(n)≡f(10) (mod n − 10).$ То есть делимость $f(n)$ на $n− 10$ равносильна делимости $f(10)$ на $n− 10.$ Очевидно, что существует лишь конечное количество $n,$ подходящее под эту делимость, потому что у $f(10)$ конечное количество делителей.

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

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

Докажите, что $pp+2 +(p+ 2)p ≡ 0 (mod 2p+2),$ где $p> 2$ — простое число.

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

Подсказка 1

Что интересного можно сказать о основаниях степеней слагаемых в левой части сравнения?

Подсказка 2

Их сумма равна 2p+2 и равна модулю, по которому ведется сравнения. Как это можно использовать?

Подсказка 3

В частности, это значит, что одно из чисел сравнимо с числом, противоположным по знаку со вторым, так p+2≡-p по модулю 2p+p. Какой вид теперь имеет сравнение?

Подсказка 4

Левая часть p^{p+2}-p^p=p^p(p^2-1). Как теперь можно закончить решение?

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

p+2 p p+2 p p + (p+2) ≡ p +(−p) (mod 2p+ 2)

Поскольку $p> 2$ простое, то оно и нечетное. Значит,

p+2 p p+2 p p 2 p p + (−p) ≡ p − p ≡ p (p − 1)≡ p(p− 1)(p+1) (mod 2p+2)

Поскольку $p+ 1...p+ 1$ и $p− 1 ...2,$ то $pp(p− 1)(p+1)≡ 0 (mod 2p+2)$

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

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

Натуральные числа $x$ и $y$ таковы, что $(ax+ by)2022+ (bx+ ay)2022$ делится на $a+ b$ для любых натуральных $a,b.$ Докажите, что $x =y.$

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

Подсказка 1

Как известно, любое натуральное число имеет конечное количество делителей. Попробуйте найти противоречие с этим утверждением.

Подсказка 2

В выражении слишком много переменных. Попробуйте уменьшить их количество с помощью сравнений, тогда рассуждать будет попроще.

Подсказка 3

a сравнимо с -b по модулю a+b. Этот факт сильно упрощает выражение. Подумайте, как теперь свести задачу к противоречию из 1 подсказки.

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

Заметим, что $a≡ −b (mod a+b).$ Значит,

2022 2022 2022 2022 (ax +by) +(bx+ay) ≡ 2b (x− y) (mod a+ b)

Получается, что $2b2022(x − y)2022$ кратно $a+ b$ при любом $a$ и $b.$ Давайте зафиксируем $b.$ Тогда понятно, что если число $2b2022(x − y)2022$ ненулевое, то тогда найдётся такое $a,$ что $a+ b$ будет больше, чем $2b2022(x− y)2022,$ то есть делимости не будет. Значит, $2b2022(x − y)2022 = 0,$ откуда $x =y.$

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

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

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

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

Натуральные числа $x,y,z$ и $n$ таковы, что $n= xy+ yz+zx,$ а число $(x+ y)50+ (y +z)50 +(z+ x)50$ делится на $n.$ Докажите, что существуют натуральные числа $a,b$ и $c,$ меньшие $n,$ и такие, что число $100 100 100 a + b + c$ делится на $n.$

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

Подсказка 1:

Попробуйте провернуть некоторые манипуляции с изначальным выражением, чтобы получить выражение формата a^100 + b^100 + c^100, делящееся на n.

Подсказка 2:

С выражениями x + y, y + z, z + x очень трудно работать по модулю xy+xz+yz. Попробуйте превратить их в более удобные.

Подсказка 3:

Умножьте изначальное выражение на некоторый многочлен от x, y, z, чтобы реализовать предыдущую подсказку.

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

Домножим выражение из условия на $(xyz)50.$ Заметим, что

50 50 50 50 50 50 100 (xyz) (x +y) ≡(xy) (xz+yz) ≡(xy) (− xy) ≡ (xy) (mod n)

Аналогично два других слагаемых сравнимы с $(yz)100$ и $(zx)100.$ Тогда получаем, что выражение $(xy)100+ (yz)100 +(zx)100$ делится на $n.$ Значит, можно взять $a= xy,b= yz,c=zx.$

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

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

Докажите, что для каждого натурального $n$ число $19⋅8n +17$ — составное.

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

Подсказка 1

Явно найти делитель числа — вероятно, самый простой способ доказать, что оно не является простым. Еще проще будет проверять делимость на число, не зависящее от n. Найдите значения при первых нескольких n, это может найти постоянные делители (возможно, с дополнительным условием на n), если они зависят от n.

Подсказка 2

8^n растет довольно быстро, тем не менее значения выражения при n = 1, 2, 3 посчитать несложно, они равны соответственно 169, 1233, 9745. Проверять делимость по большому модулю затруднительно, поэтому стоит начать с минимальных делителей - соответственно 13, 3, 5. Например, чему должно удовлетворять число n, чтобы 19*8^n+17 было кратно 3 (заметьте, что n=2 должно удовлетворять этому условию)?

Подсказка 3

Покажите, что при всех четных n число кратно 3. С чем должно быть сравнимо 8^n при этом условии?

Подсказка 4

С 1. Вообще доказывать сравнимость с 1 числа вида a^b довольно просто - для каждого числа a взаимнопростого с числом m существует b такое, что a^b сравнимо с 1 по модулю m, но тогда для любого k число a^{kb} так же сравнимо с 1. Так, 8^2=64 сравнимо с 1 по модулю. Какие условия можно наложить на число n, чтобы оно делилось на 13 и 5?

Подсказка 5

Мы уже доказали утверждения задачи для всех четных n. Доказать делимость на некоторое фиксированное число для любого нечетного n будет трудно, ведь это неправда - числа 169, 9745 взаимнопросты. Остается надеяться, что это можно сделать, для всех n сравнимых с фиксированным остатком по модулю 4.

Подсказка 6

Таким образом, осталось показать, что выражение делится на 13 при всех n=4k+1 и на 5 при всех n=4k+3.

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

Рассмотрим $3$ случая:

(a) $n= 2k,$ где $k∈ℤ,$ тогда

2k 2k k 19 ⋅8 + 17= 18 ⋅8 + 1⋅(1 +63) +(18− 1)≡ 0+ 1+ (− 1)≡ 0 (mod 3)

то есть в данном случае $19⋅8n+ 17$ делится на $3.$

(b) $n= 4k+ 1,$ где $k ∈ℤ,$ тогда

4k+1 4k+1 2k 19⋅8 +17= 13⋅8 + 6⋅8⋅64 +17=

13⋅84k+1+ 39 ⋅642k+ 9⋅(1− 65)2k+ (26− 9)≡

0+ 0+ 9+(−9)≡ 0 (mod 13)

то есть в данном случае $19⋅8n+ 17$ делится на $13.$

19⋅84k+3+ 17= 15⋅84k+3+ 4⋅83 ⋅642k+ 17 =

15⋅84k+3 +4⋅510⋅642k+ 4⋅2⋅(1− 65)2k +(25− 8)≡

0 +0+ 8+ (− 8)≡0 (mod 5)

то есть в данном случае $19⋅8n+ 17$ делится на $5.$

Рассмотренные случаи покрывают все натуральные $n.$

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

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

Петя выписал на доску натуральное число $N.$ Каждую минуту он приписывает справа к числу $87.$ Докажите, что в течение каждого часа на доске хотя бы раз будет появляться составное число.

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

Подсказка 1

Какие модули бывает полезно рассматривать в задачах на десятичную запись числа?

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

Пусть $N = aa-...a- 12 n$ и $P = a − a +a − ...+ (− 1)na . n n− 1 n−2 1$

Пусть прошло $k$ минут. Тогда на доске записано число вида $-------------- Nk = a1a2...an87...87.$ Обозначим за

n Pk = 8− 7 +8− 7+ ...+ 8− 7 +an− an−1+ an− 2− ...+(−1)a1 =k +P

Получается, что за ближайшие $11$ минут $P k$ будет иметь всевозможные остатки по модулю $11.$ Значит, за эти $11$ минут, какое-то из $P k$ поделится на $11.$ Но по признаку делимости на 11 $N ≡ P (mod 11). k k$ Т.е. начиная с какого-то момента, каждые $11$ минут, $N k$ будет делиться на $11,$ что и требовалось доказать.

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

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

Решите в натуральных числах уравнение:

2022 b c a + 2015 = 2022 − 2

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

Подсказка 1

Разность чисел 2015 и 2022 относительно небольшая. Этим можно воспользоваться при выборе модуля, по которому мы будем рассматривать исходное уравнение.

Подсказка 2

Число a²⁰²² является одновременно квадратом и кубом натурального числа. По какому модулю квадраты и кубы дают "приятные" остатки? Помните, что мы хотим отловить разницу чисел 2015 и 2022 за счет выбора модуля.

Подсказка 3

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

Подсказка 4

Левая часть сравнима с 4 при с=1, с 2 при с=2, с -2 при всех следующих значениях с. Какие может правая часть по модулю 8 в зависимости от четности чисел a и b? При каких значениях (a, b, c) достигается равенство остатков?

Подсказка 5

Равенство возможно лишь в случае, когда a — нечетное, b — четное и c =2. То есть левая часть равна 2²⁰²²-1. Что можно сказать о левой части в случае, если a>1 или b>2?

Подсказка 6

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

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

⌊ −1, при a четное, b нечетное 1 − (−1)a || 0, при a нечетное, b нечетное a2022 +2015b ≡----2-- + (− 1)b = || (mod 8) ⌈ 1, при a четное, b четное 2, при a нечетное, b четное

⌊ 4, при c= 1 2022c− 2≡ (−2)c− 2= |⌈ 2, при c= 2 (mod 8) −2, при c≥3

Получается, что правая и левая части могут быть сравнимы по модулю $8$ только в случае, когда $a$ нечетное, $b$ четное и $c =2.$ Тогда обе части уравнения сравнимы с $2$ по модулю $8.$