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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1#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)

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

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

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

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

Задача 2#89212

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

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

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

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

Задача 3#89217

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

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

Задача 4#89222

Докажите, что существует лишь конечное число натуральных $n,$ для которых $10n10+ 9n9+...+2n2+ n+ 1$ делится на $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)$ конечное количество делителей.

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

Задача 5#89225

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

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

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

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

Задача 6#89227

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

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

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

Курсы

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

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

Задача 7#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.$

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

Домножим выражение из условия на $(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.$

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

Задача 8#89721

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

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

Рассмотрим $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.$

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

Задача 9#89722

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

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

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

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

Задача 10#89723

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

2022 b c a + 2015 = 2022 − 2

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

⌊ −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.$ Т.е. решений данное уравнение в натуральных числах не имеет.

Ответ:

нет решений

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

Задача 11#90453

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

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

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

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

Интенсивы

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

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

Задача 12#90454

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

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

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


$x$	$x2$

$0$	$0$

$1$	$1$

$2$	$0$

$3$	$1$

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

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

Задача 13#91135

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

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

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

Ответ: нет

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

Задача 14#97687

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

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

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

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

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

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

Задача 15#97692

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

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

Далее все сравнения по модулю $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.$

Ответ:

Не может

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

Задача 16#104576

Дана последовательность целых чисел $a ,a,.... 1 2$ Оказалось, что для каждого натурального $n$ можно указать такое натуральное $m,$ что члены $ai$ и $aj$ дают одинаковые остатки при делении на $n$ тогда и только тогда, когда $i$ и $j$ дают одинаковые остатки при делении на $m.$ Докажите, что последовательность $a1,a2, ...$ периодична или является арифметической прогрессией.

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

Обозначим число $m$ из условия через $f(n).$ Предположим, что существуют такие натуральные числа $x > y,$ что $a =a . x y$ Тогда поскольку $.. (ax− ay).n$ для любого $n,$ разность $x− y$ делится на $f(n).$ При всех $n$ числа $i+ x− y$ и $i$ дают одинаковые остатки при делении на $f(n),$ следовательно, при всех $n$ числа $ai+x−y$ и $ai$ дают одинаковые остатки при делении на $n.$ Значит, $ai = ai+x−y$ при всех $i,$ т.е. последовательность $(ai)$ периодическая с периодом $x− y.$

Теперь предположим, что последовательность $(ai)$ состоит из различных чисел. Так как $.. (a2− a1).1,$ то $.. (2− 1).f(1),$ т.е. $f(1) =1.$ Далее, при $n> a2− a1$ получаем, что $(a2 − a1)$ не кратно $n,$ следовательно, $(2− 1)$ не кратно $f(n).$ В частности, $f(n)⁄= 1$ при $n> a2− a1.$ Пусть $t1 > t2 > ⋅⋅⋅>tℓ = 1$ — это все решения уравнения $f(x)= 1.$ Так как $.. (i− j).f(ts) =1,$ то $.. (ai− aj).ti.$ Значит, все числа в последовательности $(ai)$ дают одинаковый остаток при делении на $ti,$ а значит, и при делении на $НОК (t1,t2,...,tℓ).$ Следовательно, $f(НОК (t1,t2,...,tℓ))= 1.$ То есть $t1 = НОК (t1,t2,...,tℓ)$ и $.. t1.ti$ для любого $i.$

Предположим, что $|az+1− az|⁄=t1$ для некоторого $z.$ Так как все $ai$ дают одинаковый остаток при делении на $t1,$ выполняется равенство $|az+1− az|=ht1,$ где $h > 1,h∈ ℕ.$ Но тогда $. ((z+1)− z)..f(ht1),$ то есть $f(ht1)=1.$ Но $ht1 >t1,$ противоречие. Значит, $|ai+1− ai|= t1$ при всех $i.$ Тогда или $(ai)$ — это арифметическая последовательность с разностью $t1,$ или найдётся такое $i,$ что $ai = ai+2.$ Во втором случае мы уже доказали в начале решения, что последовательность получится периодическая. Что и требовалось доказать.

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

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

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

Задача 17#106000

Сумма цифр числа $n$ равна сумме цифр числа $2n +1.$ Может ли и у числа $7n+ 3$ быть такая же сумма цифр?

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

Если суммы цифр двух чисел равны, то равны и их остатки при делении на $9,$ откуда $2n+ 1− n = n+ 1$ делится на $9.$ Поэтому $n$ дает остаток $8$ при делении на $9,$ но тогда число $7n+ 3$ дает остаток $5$ при делении на $9$ — противоречие.

Ответ:

Не может

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

Задача 18#61462

Миша выписал все остатки от деления некоторого числа $N$ на $120,121,...,160$ . При этом оказались выписаны в каком-то порядке все числа от $43$ до $83$ . Докажите, что число $N$ составное.

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

Рассмотрим остатки при делении на $120,160$ . Заметим, что они сами должны давать одинаковый остаток при делении $40$ , поскольку

N = 120n +p =160m +q =⇒ N =40⋅3n+ p= 40⋅4m + q

То есть числа $p,q$ дают тот же остаток при делении на $40$ , что и само число $N$ . Отсюда делаем вывод, что это обязательно числа $43$ и $83$ в каком-то порядке (все остальные остатки при делении на $40$ встречаются в единственном экземпляре). Теперь рассмотрим остаток при делении на $140$ . Заметим, что

N = 140k+t =40⋅3n+ 43 или 40⋅3n+ 83

из доказанного выше. В каждом из случаев первое слагаемое кратно $20$ , как и $140k$ , то есть числа $t$ и $43$ (или, что то же самое, $83$ ) дают один и тот же остаток при делении на $20$ . Получили, что $t$ даёт остаток $3$ при делении на $20$ .

Отсюда $t= 63$ , то есть остаток $N$ при делении на $140$ может быть равен только $63$ (другие остатки, дающие $3$ при делении на $20$ , уже закончились). Итак, $N = 140k+ 63$ и кратно $7$ . Поскольку оно, очевидно, больше $7$ , то является составным.

Замечание. Про заключительную делимость $7$ можно было догадаться, если придумать несложный пример $N = 203= 7⋅29$ , откуда становится понятно, что мы хотим думать именно про $7$ .

Ответ:

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

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

Задача 19#73169

Натуральное число $m$ разбили на сумму нескольких натуральных слагаемых $m= a + a +...+a 1 2 n$ (не обязательно различных). Оказалось, что $3 3 3 a1+ a2+...+an = 6m$ . При каких $m$ такое могло произойти?

Источники: 61 УТЮМ

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

Легко проверить, что $a3 ≡ a (mod 6)$ , поэтому если сумма кубов чисел делится на 6, то и просто сумма делится. Для $m = 6k$ подойдет пример из $k$ единиц, $k$ двоек и $k$ троек.

Ответ:

при $m = 6k$ , где $k∈ ℕ$

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

Задача 20#75307

Докажите, что число $A= 2n+ 3n+ 5n +6n$ не является точным кубом ни при каком натуральном $n.$

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

Предположим противное. Пусть $n$ четно. Несложно видеть, что $A$ кратно $2,$ а значит кратно $8.$ С другой стороны при $n >2$ верно, что

n n n n n n n (2 + 6 )+3 +5 ≡ 0+ (−5) +5 ≡ 2⋅5 ⁄= 0(mod8)

при $n= 1$ имеем $A = 16,$ что не является кубом натурального числа.

Пусть $n$ нечетно. Заметим, что ${−1,1,0}$ — множество остатков кубов по модулю $7,{3,5,6}$ — множество остатков, которые дают нечетные степени 3 при делении на $7.$ Осталось заметить, что

n n n n n n n n n 2 +3 + 5 + 6 ≡ 2 +3 − 2 − 1 ≡ 3 − 1= {2,4,5}(mod7)

тем самым получили противоречие.

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

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