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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подсказка 1

Для начала стоит переписать условие в виде сравнений по модулю. А что получится, если все получившиеся сравнения перемножить?

Подсказка 2

Тогда получится, что (abc)² ≡ -27. Но из условия мы знаем, что (abc)² ≡ 121. Что тогда можно сказать о p?

Подсказка 3

Действительно, тогда p — простой делитель 121 - (-27) = 138. Осталось разложить на множители и найти примеры!

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

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

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$

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

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

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

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

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

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

Задача 63#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,$ что и требовалось.

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

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

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

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

Подсказка 1

С числом из условия работать трудно, попробуйте его записать в более удобном виде.

Подсказка 2

Чем число меньше, тем проще искать его остаток. Попробуйте как-нибудь разложить изначальное число на множители и найти остатки этих множителей при делении на 9999.

Подсказка 3

Если внимательно посмотреть, то можно заметить, что это число делится на 1001. Подумайте, каким будет второй множитель и какой у него остаток при делении на 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$

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

Задача 65#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$ — составное.

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

Задача 66#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)$ конечное количество делителей.

Курсы

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

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

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

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

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

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

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

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

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

Известно, что $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.$

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

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

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

Интенсивы

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

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

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

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

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

Подсказка 1

Проводить сравнения в этой задаче будем по модулю ab-b+1. Тогда по условию abc+1 ≡ 0(mod ab-b+1). Доказать же хотим, что bc-c+1≡ 0(mod ab-b+1) и что ac-a+1≡ 0(mod ab-b+1).

Подсказка 2

Одного условия мало, и пока непонятно, что делать с выражением abc+1. Но мы знаем, что число всегда делится на себя само(ноль, конечно, не учитывается). Тогда ab-b+1≡ 0(mod ab-b+1). Как можно использовать полученное сравнение?

Подсказка 3

ab-b+1≡ 0(mod ab-b+1) тоже самое, что ab≡ b - 1(mod ab-b+1).
А вот ab мы уже встречали в abc+1. Тогда можно сделать замену ab на b-1 по модулю ab-b+1 в выражении abc+1≡ 0(mod ab-b+1). Раскройте скобки и получите одну из искомых делимостей!

Подсказка 4

В предыдущей подсказке получили, что bc-c+1≡ 0(mod ab-b+1), а это тоже самое, что bс≡ с-1(mod ab-b+1). Тогда аналогично предыдущей подсказке подставьте полученное сравнение в abc+1≡ 0(mod ab-b+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.$

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

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

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

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

Подсказка 1

Рассмотрите 12² и 11² по модулю 133. Может получиться что-то красивое?

Подсказка 2

12² ≡ 11(mod 133), а 11² ≡ -12(mod 133)! Подумайте, как это можно использовать в исходном выражении 11ⁿ⁺² + 12²ⁿ⁺¹.

Подсказка 3

11ⁿ⁺² — это же 11ⁿ⋅11², а 12²ⁿ⁺¹ — это (12²)ⁿ⋅12.

Подсказка 4

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

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

Заметим, что

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.

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

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

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

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

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

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

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

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

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

Ответ:

нет решений

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

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

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

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

Докажите, что для любого простого $p$ существует решение сравнения

2 2 2 (x − 2)(x − 3)(x − 6)≡ 0 (mod p)

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

Подсказка 1

Как можно переформулировать задачу в терминах квадратичных вычетов?

Подсказка 2

Если хотя бы одно из чисел 2, 3, 6 является квадратичными вычетами по модулю p, то искомое число x существует. Как связаны данные числа и почему все одновременно не могут является квадратичными невычетами?

Подсказка 3

Рассмотрите символы Лежандра соответствующиx чисел и p. Какое свойство данной функции помогает в решении задачи?

Подсказка 4

Она мультипликативная! Тогда (2/p)(3/p)=(6/p). Как прийти к противоречию, используя это равенство?

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

Если $p ∈{2,3},$ то $x =0$ является решением исходного уравнения. Далее считаем, что $(6,p)= 1.$

Предположим, что не существует такого целого числа $a,$ что верно исходное сравнение, но тогда для любого числа $a∈ {2,3,6}$ верно, что не существует числа $b$ такого, что $2 b ≡ a (mod p).$ Таким образом, каждое из чисел $2,3,6$ является квадратным невычетом по модулю $p,$ то есть $( a) p =− 1$ для числа $a∈ {2,3,6}.$ Так, равенство

(2)( 3) ( 6) 1= (− 1)(−1)= p p = p = −1

не является верным, что влечет противоречие.

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

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

Докажите, что уравнение $4mn− m − n= x2$ не имеет решений в натуральных числах.

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

Подсказка 1

Левая часть равенства выглядит странно, хочется ее немного изменить и разложить на множители. Как это сделать?

Подсказка 2

Домножим на 4 и прибавим 1. Имеем (4m-1)(4n-1)=4x^2+1 очень много четверок. Какие простые могут быть в разложении частей на простые множители?

Подсказка 3

Равенство не будет выполнено, если левая часть имеет простые множители вида 4k+3, а правая - нет. Попробуйте найти такие простые слева и доказать, что справа их быть не может.

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

Предположим, что уравнение разрешимо в натуральных числах. Домножим его на $4,$ имеем

2 16mn − 4m − 4n +1 =4x + 1

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

(4m − 1)(4n − 1)= 4x2+1

Покажем, что любое число вида $4m − 1,$ для некоторого натурального $m,$ имеет простой делитель вида $p =4t− 1,$ для натурального числа $t.$ Пусть $4m − 1= n∏ pαi i i$ — разложение числа $4m− 1$ на простые множители. Предположим, что это не так, тогда $p ≡ 1 (mod 4) i$ для $i∈ {1,2,...,n}.$ Таким образом,

n 4m − 1= ∏ pαi≡1 (mod 4) i i

что влечет противоречие.

Наконец, $4x2+1$ кратно $p,$ следовательно существует число $2x,$ квадрат которого сравним с $− 1$ по модулю $p.$ Иными словами, $− 1$ является квадратичным вычетом по модулю $p= 4t+ 3,$ что невозможно.

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

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

Пусть $p =4k+ 1$ — простое число. Сколько существует перестановок $a,a ,...,a 1 2 p−1$ чисел $1,2,3,...,p− 1$ таких, что числа $a1 a2 ap−1 1 ,2 ,...,(p− 1)$ дают различные остатки по модулю $p?$

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

Подсказка 1

Покажем, что таких перестановок не существует (иначе их количество считать сложно, потому что мы не понимаем как устроены остатки произвольных чисел, по произвольному модулю). Остается надеяться, что мы сможем найти какое-либо противоречие, смотря на те степени, с которыми мы умеем работать.

Подсказка 2

Одним из таких является модуль p-1. Ясно, что существует число r такое, что a_r=p-1. Чему равно r^{a_r}?

Подсказка 3

По малой теореме Ферма r^{a_r}=r^{p-1} дает остаток 1 по модулю p. Чему может быть равно r?

Подсказка 4

Назовем S множество остатков чисел i^{a_i} для всех i от 1 до n-1. Предположим, что r не равно 1, но тогда 1^{a_1} сравнимо 1 и тогда в S нашлось сразу 2 единички. Теперь давайте посмотрим на то, чему может быть равен остаток числа (p-1)^{p-1}.

Подсказка 5

(p-1)^{a_{p-1}} сравнимо с (-1)^{a_{p-1}}, следовательно остаток равен числу 1 или -1. Первое из них уже занято, следовательно, остаток равен -1. Что это говорит о числе a_{p-1}?

Подсказка 6

Оно нечетное. Теперь мы поняли, что остатки 1 и -1 соответствуют числам 1 и p-1 в S. Если бы нам удалось найти четную степень, по которому все числа давали остатки равные 1 или -1, то мы бы нашли противоречие. Что это за остаток?

Подсказка 7

Это (p-1)/2. Докажите, что для любого a, не кратного p, число a^{(p-1)/2} сравнимо с 1 или -1.

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

Покажем, что таких перестановок не существует. Предположим противное. Тогда множество $S = {1a1,...,(p − 1)ap−1}$ образуют приведённую систему вычетов по модулю $p.$

$1.$ Найдем индекс $l$ такой, что $al = p− 1.$ Тогда, по малой теореме Ферма, для любого $a$ верно, что

a l l ≡1 (mod p)

Если $l⁄=1,$ то, поскольку $1a1 ≡ 1 (mod p),$ в $S$ встретится две $1,$ что невозможно, следовательно, $a = p− 1. 1$

$2.$ Как следствие, $(p− 1)ap−1$ не может быть сравнимо с $1,$ а поскольку

ap−1 ap−1 (p− 1) ≡ (− 1) (mod p)

верно, что $(p − 1)ap−1 ≡ −1 (mod p)$ и $ap−1$ нечетно.

$3.$ Найдем индекс $r$ такой, что $ar = p−1. 2$ Во-первых, заметим, что $rar$ не может быть сравнимо с $− 1,$ поскольку $ar$ четно и не совпадает c $ap−1.$ Во-вторых, $r$ не может быть сравнимо с $1,$ поскольку $a1 = p− 1.$ Наконец, как известно, $rar ≡ ±1 (mod p),$ тем самым получено противоречие.

Ответ:

таких перестановок не существует

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

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

Сколько существует вычетов $x∈ℤ p$ таких, что

(a) $x$ и $x+ 1$ оба являются квадратичными невычетами по модулю $p?$

(b) $x$ является квадратичным невычетом, а $x+ 1$ — квадратичным вычетом по модулю $p?$

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

Подсказка 1

Как написать условие, что число невычет? Нужно зафиксировать какой-то невычет k. Тогда все невычеты это произведение k и вычета.

Подсказка 2

Условие удобно воспринимать так: разность двух невычетов равна 1. Тогда вы получаете сравнение 1 = k(b^2-a^2). Разложите второй множитель на скобки. Чему он может быть равен? Как по нему понять второй множитель?

Подсказка 3

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

Подсказка 4

Невычетов всего (p-1)/2. Пар соседних невычет-невычет вы умеете считать из первого пункта. Как тогда понять число пар невычет-вычет?

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

(a) Пусть $d$ — квадратичный невычет по модулю $p,{a }p−21- ii=1$ — множество всех квадратичных вычетов по данному модулю. В силу мултипликативности символа Лежандра, для любого $------ i=1,...,n$ имеет место равенство

(dai) ( ai) (d) -p- = p- p = 1⋅(−1)= −1

следовательно, $dai$ — квадратичный невычет по модулю $p.$ Таким образом, мы показали, что $p−1 {dai}i2=1$ — множество всех квадратичных невычетов по модулю $p.$

Так, если каждое из чисел $x$ и $x+ 1$ являюся квадратичными невычетами, то они равны соотвественно числам $da2i$ и $da2j$ для некоторых натуральных $i,j ∈ {1,...,n}.$ Таким образом, имеет место сравнение, которое назовем важным,

1≡ d(a2j − a2i)≡d(aj − ai)(aj + ai) (mod p)

Пусть $aj − ai = m,$ тогда $aj +ai = d1m$ — обратный остаток существует, поскольку каждое из чисел $d,m$ не кратно $p.$ Составим систему линейных уравнений, решив ее, получим решения

aj = d1m-+-m,ai = d1m-− m 2 2

Число $d$ является фиксированным. Таким образом, каждой паре соответствует единственное $m,$ в свою очередь, каждое число $m$ однозначно определяет пару $(x,x +1)$ квадратичных невычетов. Таким образом, важное сравнение $1≡ d(a2− a2) (mod p) j i$ имеет ровно $p− 1$ решение.

Заметим, что каждому решению $(x,x+1)$ исходного уравнения соответствует ровно 4 решения (возможно совпадающих) уравнения важного сравнения — $(±a,±a ). i j$

В случае, если $|a |,|a |> 0, i j$ то все четыре решения $(±a,±a ) i j$ являются различными. Если $a = 0, i$ то $da2 =1, j$ что невозможно, поскольку $1$ является квадратичным вычетом по данному модулю. Если $aj = 0,$ то $dai = −1$ и имеет место только при $p =4k+ 3,$ когда $− 1$ является невычетом по модулю $p.$

Наконец, мы показали, что в случае $p= 4k+ 1$ среди пар $(±ai,±aj)$ решений важного сравнения все различны, следовательно, решений исходного уравнения ровно в 4 раза меньше и равно $p−1 4 .$

Если $p= 4k +3,$ то количество пар уменьшится на $2,$ то есть станет $(p − 1)− 2.$ А значит количество решений исходного уравнения равно $p−3 4 .$

(b) Заметим, что общее количество пар $(x,x+ 1),$ в которых $x$ является квадратичным невычетом по модулю $p$ совпадает с количеством всевозможных квадратичных невычетов. Таким образом, в случае $p =4k+ 1$ имеем