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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1#122423

Три простые числа $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

Найдите все такие пары целых чисел $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

Найти все натуральные числа $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

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

Докажите, что для каждого натурального $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#85917

Дано натуральное $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)

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

Курсы

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

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

Задача 7#89212

Натуральные числа $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,$ что и требовалось.

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

Задача 8#89217

Даны натуральные числа $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$ — составное.

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

Задача 9#89222

Докажите, что существует лишь конечное число натуральных $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)$ конечное количество делителей.

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

Задача 10#89225

Докажите, что $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)$

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

Задача 11#89227

Натуральные числа $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.$

Интенсивы

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

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

Задача 12#89228

Натуральные числа $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.$

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

Задача 13#89721

Докажите, что для каждого натурального $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.$

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

Задача 14#89722

Петя выписал на доску натуральное число $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,$ что и требовалось доказать.

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

Задача 15#89723

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

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.$

При $a> 1:a2022+ 2015b > 22022 > 20222− 2.$

При $b> 2:a2022+ 2015b > 20153 > 20222 − 2.$

Т.е. единственный возможный вариант: $a= 1,b= 2.$ Но тогда $12022+ 20152 ⁄= 20222− 2.$ Т.е. решений данное уравнение в натуральных числах не имеет.

Ответ:

нет решений

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

Задача 16#90453

Докажите, что число, состоящее из 21 единицы и нескольких нулей, не может быть квадратом целого числа.

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

Предположим, что $x= n2$ — число, состоящее из $21$ единициы и нескольких нулей. Тогда сумма цифр этого числа равна $21.$ По признаку делимости на $3$ и $9$ данное число делится на $3,$ но не делится на $9.$ (так как сумма цифр делится на $3,$ но не делится на $9$ )

Однако $2 n$ либо не делится на $3,$ либо делится сразу на $9.$ Следовательно, возникает противоречие, и мы приходим к выводу, что числа, состоящего из $21$ единицы и некоторого количества нулей, не существует.

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

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

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

Задача 17#90454

Докажите, что сумма квадратов трёх нечётных чисел не может быть квадратом целого числа.

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

Рассмотрим таблицу остатков при делении квадратов на 4:


$x$	$x2$

$0$	$0$

$1$	$1$

$2$	$0$

$3$	$1$

Заметим, что нечётные числа могут давать остатки 1 и 3 при делении на 4, соответственно, квадраты нечётных чисел будут давать осаток 1. Таким образом, сумма квадратов трёх нечётных чисел будет сравнима с $1+ 1+1 =3$ по модулю 4, а квадрат целого числа не может давать остаток 3 при делении на 4. Отсюда, сумма квадратов трёх нечётных чисел не может быть квадратом целого числа.

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

Задача 18#91135

Можно ли в числе 123456 переставить цифры так, чтобы оно стало квадратом?

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

Предположим, что это возможно. Тогда сумма цифр этого квадрата $21.$ Следовательно, число делится на $3.$ Но раз это квадрат, то он должен делиться на $9,$ но сумма цифр не делится на $9,$ значит, это невозможно.

Ответ: нет

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

Задача 19#97687

Докажите, что не существует натуральных чисел $b> a+ 1,$ для которых число $b(2a+ b)2023− a(2b+ a)2023$ является простым.

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

Подсказка 1

Можем ли мы найти какой-то модуль, по которому остаток выражения будет 0?

Подсказка 2

В условии не просто так дано, что b>a+1. Это даёт нам, что b-a>1. Конечно, подходящий для делимости модуль должен быть больше 1.

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

Пусть $x =b− a.$ Покажем, что значение выражения делится на $x.$ Далее все сравнения по модулю $x.$

2023 2023 2023 2023 (a+ x)(3a+x) − a(2x+ 3a) ≡a(3a) − a(3a) ≡ 0

То есть это выражение делится на $x> 1.$ Оно больше, чем $x,$ поэтому является составным числом.

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

Задача 20#97692

Вадим выписывает числа на доску. Изначально он пишет на доске какое-то число, большее $100.$ Далее Вадим берет число $x,$ выписанное последним, и дописывает на доску число $2 x − 1.$ Может ли Вадим выбрать начальное число так, чтобы для любого простого числа рано или поздно на доске появилось число, которое делится на это простое?

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

Подсказка 1

Предположим, что изначально остаток по модулю р для какого-то р был произвольным? Каким он должен стать, чтобы прийти в итоге к делимости через х²-1?

Подсказка 2

Мы должны прийти к остатку 1 по модулю р (почему к -1 не получится?). Для этого должно быть разрешимо уравнение x²≡2 (mod p). Для каких р это сравнение неразрешимо?

Подсказка 3

Сравнение неразрешимо для p=8k+3 или p=8k+5. Чтобы это доказать, стоит рассмотреть произведение чётных чисел, меньших р и нечётных, меньших р. Можем ли мы выбрать такое р, чтобы остаток у n по его модулю был не 1?

Подсказка 4

Такое простое найдётся, если простых нужного вида бесконечно. Чтобы доказать их бесконечность, можно использовать доказательство от противного.

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

Далее все сравнения по модулю $p.$ Заметим, что если исходно $x$ не делилось на $p,$ то мы должны на каком-то шаге получить $x2 ≡ 1.$ Значит, или $x≡ 1$ или $x ≡− 1.$ Во втором случае остаток $− 1$ мы могли получить только из $2 x − 1≡ −1,$ но тогда $p|x,$ чего не бывает. Значит, на каком-то шаге $2 x ≡ 2.$

______________________________________________________________________________________________________________________________________________________

Найдём для начала такие простые числа, для которых не существует решения такого уравнения в целых числах.

p−1- p− 1 p−1- 2 2 ⋅(1⋅2⋅...⋅-2--)= 2⋅4 ⋅...⋅(p− 1)≡ (−1)⋅(p− 2)⋅...⋅(−1)⋅1= 1⋅3⋅...⋅(p− 2)⋅(−1)2

Теперь заменим четные числа $a$ из левой скобки на $(− 1)⋅(p− a).$ Пусть $p= 8k+ 3.$ Тогда этих чётных чисел $2k.$

p−1 2-2-⋅(1⋅3⋅...⋅(p− 2))⋅(− 1)2k ≡ 1⋅3⋅...⋅(p− 2)⋅(−1)4k+1

Значит, $p−1- 2 2 ≡ −1$ для $p=8k +3.$ Пусть $p= 8k+ 5.$ Тогда этих чётных чисел $2k+ 1.$

p−1 2 2 ⋅(1⋅3⋅...⋅(p− 2))⋅(− 1)2k+1 ≡ 1⋅3⋅...⋅(p− 2)⋅(−1)4k+2

Значит, $p−1- 2 2 ≡ −1$ для $p=8k +5.$

______________________________________________________________________________________________________________________________________________________

Покажем, что простых вида $8k+ 4± 1$ бесконечно много. Пусть их конечно, они $p1,p2,...,pn.$ Рассмотрим число $72p1p2...pn+ 3.$ Оно даёт остаток $3$ по модулю $8,$ при этом не делится на $9,$ поскольку первое слагаемое делится, а второе — нет. Также оно не делится на все из простых чисел нужного вида (кроме тройки, но она только в первой степени). Значит, имеется ещё какой-то делитель нужного вида (ведь мы не можем получить остаток $3$ по модулю $8$ произведением остатков $±1).$

______________________________________________________________________________________________________________________________________________________

Пусть есть решение у $x2 ≡ 2.$ Возведём в степень $p−1 -2-.$ Тогда для $p= 8k+ 4± 1:$

1≡ xp−1 ≡ 2p−21≡ −1

Противоречие, поэтому такого $x$ не найдётся. Для выбранного Вадимом начального числа $a$ найдём достаточно большое $p$ вида $8k+ 4± 1,$ тогда изначально остаток по модулю $p$ у числа $a$ не $0,1$ и не $− 1.$ Значит, после наших операций никогда не получится числа, делящегося на $p.$

Ответ:

Не может

Предыдущая подтема

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