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

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

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

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

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

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

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

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

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

Задача 1#104744

Пусть $P$ — нечётное, большее единицы число и $P =p p ...p 1 2 n$ — его разложение на простые множители (среди $p ,p ,...,p 1 2 n$ могут быть равные). Тогда для произвольного целого числа $a$ символ Якоби определяется равенством:

(a) (a)( a) ( a) P- = p1 p2 ...pn ,

где $( ) api$ — символы Лежандра. По определению считаем $( ) a1 = 1$ для всех $a.$ Докажите, обобщённый квадратичный закон взаимности: если $P,Q$ — взаимно простые нечётные числа, то

( ) ( ) Q- =(−1)(P−1)4(Q−1)⋅ P- P Q

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

Сначала проверим случай, когда одно из чисел $1.$ Пусть $P =1.$ Тогда $( Q)= 1, (-1)= 1, (− 1)0 = 1. 1 Q$ То есть действительно всё сходится.

Теперь пусть $P =p1p2...pn$ и $Q= q1q2 ...qk.$ Из взаимной простоты следует, что $pi ⁄= qj.$ Мультипликативность символа Якоби следует из определения и мультипликативности символа Лежандра: $(a1a2) (a2)(a1) P = P P .$ Тогда

( )( ) ∏n ( ) ∏n ( ) ∏n ∏k( )( ) Q- P- = Q- ⋅ pi = qj pi P Q i=1 pi i=1 Q i=1j=1 pi qj

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

(Q )( P) ∑n ∑k pi−1 qj−1- -P Q- = (− 1) i=1 j=1 2 2

Значениие степени $− 1$ зависит от чётности показателя, то есть нам нужно доказать, что

∑n k∑ pi−-1qj −-1≡ P-− 1Q-−-1 (mod 2) i=1j=1 2 2 2 2

Для нечётных $a, b$ заметим, что $a−21+ b−21≡ ab−21(mod 2)$ (можно явно проверить, рассмотрев остатки по модулю $4:$ при равных остатках с обеих сторон получится $0,$ при различных остатках — $1).$ Тогда заметим, что в сумме можно вынести $pi2−1$ за второй индекс суммирования:

∑n k∑ p − 1q − 1 ∑n p− 1∑k q − 1 ∑n p − 1Q − 1 -i2---j2--= i2--- -j2--≡ -i2----2-- (mod 2) i=1 j=1 i=1 j=1 i=1

из нашего тождества. Теперь общий множитель $Q−1 2$ можно тоже вынести:

∑n pi− 1 Q− 1 Q − 1∑n pi− 1 Q− 1P − 1 --2---2--= --2-- -2---≡ -2----2-- (mod p) i=1 i=1

снова по тождеству. То есть у нас получилось в точности то, что и требовалось доказать:

( ) ( ) Q- P- = (−1)(P−1)(4Q−1) P Q

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

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

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

Задача 2#83961

Пусть $a =22n + 1.$ Докажите, что $a$ простое тогда и только тогда, когда $a$ делит $322n−1 +1.$

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

Докажем, что если $a$ — простое, то $322n−1 + 1$ делится на $a.$ Заметим, что $a ⁄≡±1 (mod 12),$ то есть $3$ не является квадратичным вычетом по модулю $a.$ Тогда $(a−1)∕2 3 ≡ −1 (mod m)$ из критерия Эйлера, что и требовалось.

Пусть $a$ — составное число, и выполнена делимость. Отметим, что $3$ и $a$ взаимно просты ( $2n 2 ≡ 1 (mod 3)$ ), поэтому определено понятие показателя $3$ по модулю $a.$ Рассмотрим показатель $d$ числа $3$ по модулю $a.$ Из $22n− 1 3 ≡ −1 (mod a)$ получаем $22n 3 ≡ 1 (mod a),$ откуда $2n 2$ делится на $d,$ то есть $d$ является степенью двойки. С другой стороны из первого сравнения получаем $2n−1 d >2 ,$ откуда $2n d =2 = a− 1.$

Теперь воспользуемся теоремой Эйлера: согласно ей, $.. ϕ(a) . d.$ Поскольку $a$ – составное, то $ϕ(a) <a− 1.$ Получается, что $.. ϕ(a). a− 1,$ но $ϕ(a)< a− 1,$ причем $ϕ(a)$ – натуральное число. Это невозможно, поэтому мы достигли противоречия.

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

Задача 3#84254

Дано простое число $p.$ Найдите количество решений сравнения

2 2 x +y ≡ 1 (mod p)

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

Рассмотрим два случая:

1) $p=2.$ Тогда решений всего два $(1;0)$ и $(0;1).$

2) $p⁄=2.$

Для начала предположим, что $y ≡p 0$ и $2 x ≡p 1.$ Тогда $x≡p 1$ или $x≡p − 1.$ Заметим, что если $p⁄= 2,$ то верно $− 1 ⁄≡p 1,$ поэтому $(1;0)$ и $(−1;0)$ — различные решения.

Теперь будем считать, что $y ⁄≡p 0,$ то есть $y$ обратим.

Тогда умножим все сравнение на $−2 y .$ Получаем

(xy−1)2+ 1≡p y−2

По формуле разности квадратов:

(y− 1− xy−1)(y−1+ xy−1)≡p 1

Таким образом, $−1 −1 y − xy$ и $−1 −1 y + xy$ взаимно обратны по модулю $p,$ то есть удовлетворяют системе

{ y−1− xy− 1 ≡ a −1 − 1 p −1 y + xy ≡p a

для некоторого обратимого $a.$ Из этой системы следует, что $2y−1 ≡p a+ a−1,$ поэтому решения существуют тогда и только тогда, когда $a+ a−1$ обратим. Отметим, что если $a+ a−1$ все-таки обратим, то $y ≡p 2−1(a+ a−1)− 1,$ и вычет $x$ тоже восстанавливается однозначно. Таким образом, система имеет единственное решение, если $a+ a−1$ обратим.

Найдем такие $p,$ для которых существуют обратимые $a$ такие, что $a+ a−1$ необратим. Для этого рассмотрим сравнение $a+ a−1 ≡ 0. p$ Оно эквивалентно сравнению $a2 ≡ −1 p$ $⇔$ $− 1$ является квадратичным вычетом по модулю $p.$ По критерию Эйлера, $− 1$ — квадратичный вычет тогда и только тогда, когда

(−1)p−21≡p 1

Очевидно, это сравнение верно только если $p$ имеет вид $4k +1,$ а во всех остальных случаях $− 1$ является невычетом. Таким образом, задача разбивается на два случая.

1.: В случае $p= 4k+ 1$ имеется ровно два решения сравнения $a2 ≡p −1.$ Таким образом, в качестве $a$ в систему можно подставить $p− 2− 1= p− 3$ различных $a$ (все кроме решений указанного сравнения и $0$ ) и получится $p− 3$ различных решения. Вспомним, что еще имеется два решения из $y ≡p 0,$ поэтому общее число решений — $p− 1.$
2.: В случае $p= 4k− 1$ сравнение $a2 ≡p − 1$ не имеет решений, поэтому можно просто подставлять любое $a$ из $p− 1$ возможного. Учтем еще 2 решения из случая $y ≡p 0,$ тогда получится $p+ 1$ решение.

Ответ:

Если $p =4k+ 1,$ то $p− 1$ решений,

если $p =4k+ 3,$ то $p+ 1$ решений.

если $p =2,$ то $2$ решения.

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

Задача 4#89724

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

2 2 2 (x − 2)(x − 3)(x − 6)≡ 0 (mod 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

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

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

Задача 5#89726

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

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

Предположим, что уравнение разрешимо в натуральных числах. Домножим его на $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,$ что невозможно.

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

Задача 6#89728

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

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

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

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

(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$ имеем

p− 1 p− 1 p−-1 2 − 4 = 4

а в случае $p= 4k +3$

p− 1 p− 3 p+ 1 -2--− -4--= -4--

Ответ:

(a) Если $p= 4k +1,$ то $p−1- 4 ;$ если $p= 4k+ 3,$ то $p−3 4$

(b) Если $p= 4k+ 1,$ то $p−1 4 ;$ если $p= 4k +3,$ то $p+1 4$

Курсы

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

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

Задача 7#89729

Дано простое число $p.$ Оказалось, что $p$ не является делителем $n2+ 3n +11$ ни для какого натурального $n.$ Докажите, что найдется натуральное $a$ такое, что $4 3 2 2a + 9a − a + 9a+ 2$ делится на $p.$

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

Если сравнение $n2+ 3n+ 11= 0 (mod p)$ не имеет решений относительно $n,$ то и сравнение

2 (2n+ 3) =9 − 44= −35 (mod p)

не имеет решений относительно $n.$ Ясно, что любой остаток $r$ по модулю $p$ представим, как $2n +3$ для некоторого $n,$ но тогда не существует такого остатка $r,$ что $r2 = −35 (mod p),$ но тогда $− 35$ квадратичный невычет по модулю $p.$

Второе число можно представить как

4 3 2 ( 2 )( 2 ) 2a + 9a − a + 9a+2 = a + 5a+1 2a − a +2

Таким образом достаточно показать, что хотя бы одно из сравнений

2 (2a+ 5)≡ 21 (mod p),

(4a − 1)2 ≡ −15 (mod p)

имело решения. Предположим противное, но тогда

( ) ( )( ) −35⋅9 = 21 −-15 = (−1)(−1)= 1 p p p

С другой стороны, в силу того, что $− 35$ является квадратичным невычетом по модулю $p$ верно, что

(−-35-⋅9) = (−35) (9) = (−1)⋅1= −1 p p p

Также давайте отдельно рассмотрим $p= 2$ и $p= 3.$ В первом случае условие задачи выполняется, и мы можем просто взять $a =2$ (число для делимости нашлось). Во втором же случае, даже при $n =1$ условие не будет выполняться, так как $15$ делится на $3.$

Замечание. Разложение

( )( ) 2a4+ 9a3− a2+ 9a+2 = a2+ 5a+1 2a2− a +2

можно получить, введя замену $1 a+ a =x,$ тогда

a2(2x2+ 9x − 5)= a2(x− 5)(x+ 1∕2)

Осталось перейти к обратной замене и домножить содержимое каждой из скобок на $a.$

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

Задача 8#97050

Пусть $q ≡ 3 (mod 4)$ — простое число, большее $3.$ Оказалось, что $p =2q+ 1$ также является простым числом. Докажите, что число $q 2 − 1$ составное.

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

Покажем, что число $2q− 1= 2(p−1)∕2− 1$ кратно $p.$ Сравнение же $2(p−1)∕2 ≡ 1$ эквивалентно условию того, что $2$ является квадратичным вычетом по модулю $p.$ Поскольку $p =2q+ 1$ имеем $−-1 2≡ q ,$ следовательно достаточно показать, что оба числа $− 1$ и $q$ являются невычетами. Первое верно, поскольку $(− 1)(p−1)∕2 =(−1)q = −1.$ Осталось понять, почему $q$ — невычет. По квадратичному закону взаимности

( ) ( ) p ⋅ q = (−1)p−21⋅q−12-= −1 q p

поэтому достаточно понять, что $( ) pq = 1,$ что очевидно, так как

( ) ( ) ( ) p = 2q+1- = 1 = 1 q q q

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

Задача 9#97051

Докажите, что простых чисел вида $10k− 1$ бесконечно много.

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

Докажем, что простых чисел сравнимых с $− 1$ по модулю $5$ бесконечно много. Это будет равносильно задаче в силу того, что все простые кроме числа $2$ — нечетные. Пусть это не так, то есть таких чисел конечно, обозначим за $A$ удвоенное их произведение. Число $2 A − 5$ — больше $1$ и нечетно, тогда $2 A − 5≡ 0 (mod p).$ Тогда $5$ — квадратичный вычет по модулю $p,$ и по квадратичному закону взаимности имеем:

(5) (p) p−1⋅5−-1 (p) p ⋅ 5 = (−1)2 2 = 1⇒ 5 =1

то есть $p ≡±1 (mod 5).$ Но все простые делители не могут быть вида $5k+ 1$ ведь $A2− 5≡ 4 (mod 5).$ Значит существует еще одно простое число вида $5k− 1$ — противоречие.

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

Задача 10#97052

Найдите все натуральные числа $n,$ для которых $3n− 1$ делится на $2n − 1.$

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

Легко заметить, что $n= 1$ — подходит, далее $n> 1.$ Если $n$ — четно, то $2n − 1$ кратно трем, а $3n− 1$ не делится, поэтому $n$ — нечетное число. Предположим, что $n 3 − 1$ делится на $n 2 − 1,$ очевидно, что тогда любой простой делитель $n 2 − 1,$ назовем его $p,$ делит $n 3 − 1.$ Ясно, что $p$ не может быть ни $2,$ ни $3.$ В таком случае посмотрим на $p$ по модулю $4.$ Если $p$ сравнимо с $3$ по модулю $4.$ Так как $n$ нечетно, то $3$ является квадртатичным вычетом по модулю $p.$ Из квадратичного закона взаимности понимаем, $(p) 3 = −1,$ то есть $p≡− 1 (mod 3)⇒ p≡− 1 (mod 12).$ Если $p$ сравнимо с $1$ по модулю $4.$ Так как $n$ нечетно, то $3$ является квадртатичным вычетом по модулю $p.$ Из квадратичного закона взаимности понимаем, $(p) 3 = 1,$ то есть $p ≡1 (mod 3)⇒ p≡ 1 (mod 12).$ Тогда $n 2 − 1≡ ±1 (mod 12),$ чего быть не может.

Ответ:

$n =1$

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

Задача 11#97387

Дано простое число $p= 3k +2.$ Докажите, что сравнение $y2− x3 ≡1 (mod p)$ имеет не более $p$ решений по модулю $p.$

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

В тривиальном случае $p= 2$ имеем решения $x≡ 0 p$ и $y ≡ 1 p$ и наоборот.

Для начала покажем, что для каждого конкретного $c$ сравнение $3 x ≡ c (mod p)$ имеет единственное решение. Для $c≡p 0$ этим решением является $x≡p 0.$ Пусть теперь $c⁄≡p 0.$ Тогда заметим, что в силу малой теоремы Ферма при $3 x ≡p c$ выполняется следующая цепочка сравнений

c≡p cxp−1 ≡p cx3k+1 ≡p cx(x3)k ≡p ck+1x

Таким образом, $− k x≡p c .$ Теперь вернемся к исходному сравнению. Оно имеет вид $2 3 y ≡p x + 1.$ Это сравнение имеет решение в точности, когда $3 x +1$ является квадратичным вычетом по модулю $p.$ Всего ненулевых квадратичных вычетов имеется ровно $p−1 2 ,$ а также нулевой вычет. В каждом случае для ненулевого вычета имеем не более двух решений $y$ и $− y,$ а для нулевого вычета единственное решение $y ≡p 0,$ причем, для каждого вычета, как показано ранее, имеется единственный $x.$ Таким образом, пар вычетов-решений не более, чем $p−1- 2 ⋅ 2 +1 =p.$

Интенсивы

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

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

Задача 12#97453

Найдите все целые числа $x$ и $y,$ для которых число $x2+x+2 y6−2$ целое.

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

При $y = ±1,0$ очевидно, что $x$ может быть любым. Во всех остальных случаях $y6− 2> 0.$ По малой теореме Ферма $6 y − 2≡7 −1$ или $− 2.$ Оба этих числа являются невычетами по модулю $7,$ поэтому у $6 y − 2$ найдется простой делитель $p,$ являющийся невычетом по модулю $7$ (в частности, $p⁄= 2).$ Заметим, что $2 (2x+1) ≡p −7,$ то есть $(−7) p =1.$ По КЗВ имеем

(− 7) ( −1)( 7) (7) -p- = p-- p = (−1)(p−1)∕2⋅ p ⋅(−1)(p−1)(7−1)∕2 = −1

Таким образом, $x2+ x+2$ не делится на $p,$ и дробь целых значений не принимает.

Ответ:

$y =±1,0$ и $x$ — любое целое число

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

Задача 13#104583

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

(a) $(a) p−21 p ≡a (mod p);$

(b) $( )( ) ( ) ap bp = abp-.$

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

$a)$ Пусть $a$ — квадратичный вычет. Тогда $a≡ b2 (mod p).$ Возведём в степень $p−1, 2$ тогда по малой теореме Ферма получаем $p−1 a 2 ≡ 1 (mod p).$ Теперь рассмотрим над $ℤp$ многочлен $p−1 x 2 − 1.$ Мы показали, что он имеет хотя бы $p−1 2$ корней — квадратичные вычеты. При этом степень этого многочлена $p−1 2 .$ Значит, квадратичные невычеты не являются его корнем. При этом $p−1- p−1 xp−1− 1= (x 2 − 1)(x 2 + 1)≡ 0 (mod p)$ при всех ненулевых $x.$ Значит, для всех невычетов $p−1 x 2 + 1≡ 0 (mod p),$ тогда $p−1 a 2 ≡ −1 (mod p).$

$b)$ Теперь докажем мультипликативность символа Лежандра. По пункту $a)$ мы знаем, что левая часть сравнима с $p−1- (ab)2 ,$ а правая — с $p−1 p−1 a 2 b 2 ,$ так что это очевидно.

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

Задача 14#104585

Докажите, что $− 1$ является квадратичным вычетом по модулю $p$ тогда и только тогда, когда $p= 4k+ 1.$

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

Рассмотрим выражение $(−1)p−21.$ Это $1$ тогда и только тогда, когда $p−1 2$ — чётное число. Это достигается при $p= 4k+ 1.$

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

Задача 15#104586

Пусть $n$ — натуральное число такое, что $4n+ 1$ — простое. Докажите, что $n2n − 1$ делится на $4n+ 1.$

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

Пусть $p =4n+ 1.$ Мы хотим доказать, что $np−21− 1$ делится на $p,$ то есть что $n$ — квадратичный вычет по модулю $p.$ $4$ — квадратичный вычет для любого $p,$ поскольку $2 2 =4.$ Вспомним, что $− 1$ — квадратичный вычет для $p= 4n +1,$ и по мультипликативности символа Лежандра получим требуемое: $p− 1= 4n,$ значит, раз

(4 )(n ) (− 1) p p = -p-

то и $( n) p =1.$

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

Задача 16#104587

Решите в целых числах уравнение $x2 =y3+ 7.$

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

Прибавим к обеим частям по $1$ и разложим на множители правую часть:

2 2 x + 1= (y +2)(y − 2y+4)

Пусть $y$ чётно. Тогда $x$ нечётно, значит, левая часть не делится на $4,$ а правая делится. Значит, если и есть решения, то $y$ нечётно. Тогда заметим, что правая часть обязательно имеет простой делитель вида $4k+ 3.$ Действительно, поскольку если $y ≡ 1 (mod 4),$ то $y+ 2$ имеет такой делитель, а если $y ≡ 3 (mod 4),$ то $y2− 2y+4 ≡3 (mod p)$ и имеет такой делитель. Но если $x2+ 1$ делится на $p =4k+ 3,$ то $− 1$ — квадратичный вычет по модулю $p= 4k+3,$ чего не бывает. Ясно, что левая часть всегда положительна, так что наши рассуждения корректны.

Ответ:

Решений нет

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

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

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

Задача 17#104588

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

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

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

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

(a) Пусть

({ 2 x≡ a (mod p) ( x+ 1≡ b2 (mod p)

Тогда $a2+ 1≡ b2 (mod p)$ или $(b− a)(b+ a)≡1 (mod p).$ То есть имеем систему

( {b− a≡ r (mod p) (b+ a≡ 1r (mod p)

Ясно, что она имеет различные решения для каждого $r,$ которых $p − 1.$ Некоторым решениям на $x$ соответствуют разные $a, b.$ Выдать одинаковые квадраты могут пары $(a,b), (−a,b), (a,−b), (− a,− b).$ Посмотрим, в каких ситуациях эти пары совпадают между собой. Если $a ≡0 (mod p),$ то могут совпасть $1$ и $2,3$ и $4.$ То есть $2$ пары склеиваются. Теперь рассмотрим $b≡ 0 (mod p).$ Тогда получим, что $− 1$ должна быть квадратичным вычетом (для решения, в котором $b= 0).$ Значит, если $p= 4k +1,$ то появятся ещё $2$ совпавшие пары, иначе их не появится. Тогда для $p= 4k +1$ ответ $p−1−42−2= p−45,$ а для $p= 4k +3$ — $p−3. 4$

(b) Пусть $a1,...,ap−1 2$ — квадратичные вычеты. Тогда из мультипликативности символа Лежандра, домножив на $e$ — квадратичный невычет, мы получим все квадратичные невычеты $ea1,...,eap−1. 2$ Значит, по сравнению с предудыщим пунктом наша система превращается в следующую:

({ x≡ a2 (mod p) ( 2 x+1 ≡eb (mod p)

Тогда нас интересует число решений сравнения $a2+ 1≡ eb2 (mod p).$ Пусть $p= 4k +1.$ Тогда найдётся $c$ такое, что $c2 ≡ −1 (mod p),$ что преобразует сравнение в $2 2 2 a − c ≡eb (mod p).$ Если $b≡ 0 (mod p),$ то решения два: $a= ±c.$ Иначе поделим на $2 b$ и будем решать сравнение $2 2 u − v ≡ e (mod p).$ Теперь выражениие раскладывается на множители: $(u− v)(u+ v)≡e (mod p),$ где $a c u ≡ b, v ≡ b (mod p).$ У него $p− 1$ решение.

Тогда

c b≡ v (mod p), a≡ ub (mod p)

то есть они восстанавливаются однозначно. Значит, аналогично прошлому пункту для $p= 4k +1,$ решениия разбиваются на четвёрки во всех случаях, кроме $b≡ 0 (mod p),$ но эти решения мы и так уже отбросили. $a$ нулём быть не может, поскольку $1$ всегда квадратичный вычет. Значит, все $p − 1$ решений разбиваются на четверки и ответ $p−41.$ Теперь пусть $p= 4k+ 3.$ Здесь воспользуемся соображениями о том, что мы знаем число пар всех оставшихся видов: вычет-вычет, которых $p−43,$ невычет-вычет, их $p−34 ,$ и невычет-невычет, их $p−43.$ Всего пар чисел (не считая $0)$ $p− 2,$ так что на интересующие нас остаётся $p− 2− 3 ⋅ p−34-= p+41.$ Тогда для $p= 4k +1$ ответ $p−41,$ а для $p =4k+ 3$ — $p+14 .$

Ответ:

(a) Для $p= 4k+ 1$ — $p−5 4 ,$ а для $p= 4k +3$ — $p−-3 4 ;$

(b) для $p= 4k+ 1$ — $p−1 4 ,$ а для $p= 4k +3$ — $p+1 4$

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

Задача 18#68536

Ненулевые взаимно простые в совокупности числа $a,b,c,d$ удовлетворяют равенству

( 1 1 1 1)2 abcd a + b +c + d = (a +b+ c+ d)2

Докажите, что все нечетные простые делители числа $a2+ b2+ c2+d2$ дают остаток $1$ при делении на $4.$

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

После раскрытия скобок и сокращения, а также избавления от знаменателей получаем равенство

22 2 2 22 22 2 22 2 2 2 2 2 (ab c +a b d +a cd + bc d) =abcd(a + b+ c + d)

Предположим, что $a2+ b2 +c2+ d2$ имеет некоторый простой делитель $p$ вида $4k+ 3.$ Тогда $a2 ≡− b2− c2− d2 (mod p).$ При этом

22 2 2 22 22 2 22 2 2 22 2 2 2 2 2 2 2 2 2 ab c +a b d+ a cd + bc d ≡ bc d − (b +c + d)(bc + cd + bd )≡

≡ −(b2+c2)(c2+ d2)(b2+ d2)≡0 (mod p)

Тогда одна из скобок делится на $p.$ Пусть, не умаляя общности, $b2+ c2$ делится на $p,$ но тогда $b$ и $c$ делятся на $p$ (иначе $− 1≡ (b∕c)2$ было бы квадратичным вычетом по модулю $p =4k+ 3,$ что невозможно). Тогда $a2+ d2$ также делится на $p,$ откуда $a$ и $d$ делятся на $p$ — противоречие с взаимной простотой $a,b,c,d.$

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

Задача 19#74879

Докажите, что простое число $p$ является делителем числа вида $x2− x+ 3$ тогда и только тогда, когда оно является делителем числа вида $2 y − y+ 25.$

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

Как известно, решение $.. ax2+bx+ c. p$ существует тогда и только тогда, когда дискриминант $ax2+bx+ c$ является квадратичным вычетом по модулю $p.$ Поэтому, условие задачи равносильно следующему утверждению: дискриминант $x2− x+ 3$ является квадратичным вычетом по модулю $p$ тогда и только тогда, когда дискриминант $y2− y +25$ является квадратичным вычетом по тому же модулю.

Вычислим указанные дискриминанты. Первый равен $1− 12 =− 11,$ а второй $1− 100 =− 99.$ Фактически, требуется проверить, что для любого простого $p$ выполнено $( ) ( ) −1p1 = −9p9 ,$ где $( ) ap$ – символ Лежандра. Отдельно отметим, что случай $p= 2$ очевиден – для него не определено понятие символа Лежандра. Согласно свойству мультипликативности, $( ) ( ) ( ) −9p9 = −1p1 ⋅ 9p .$ При этом, очевидно, $(9) 2 p = 1:3 ≡ 9 (mod p)$ для всех $p.$

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

Задача 20#74880

Пусть $p >2$ — простое число. Назовем вычет $a∈ ℤ p$ биквадратичным по модулю $p,$ если существует вычет $b$ такой, что $4 a ≡b (mod p).$ Докажите, что $p= 4k+ 3$ тогда и только тогда, когда его множества квадратичных и биквадратичных вычетов совпадают.

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

Из общей теории известно, что количество квадратичных вычетов по любому простому $p >2$ равно $p−-1. 2$ Отметим, что любой биквадратичный вычет является и квадратичным ( $4 22 a≡ b =(b) (mod p)$ ), поэтому их количество не превосходит $p−1- 2 .$ Тем самым, задача равносильна проверке того, что только для простых вида $p= 4k +3$ количество биквадратичных вычетов равно $p−1 2 .$

Рассмотрим биквадратичные вычеты $( )4 14, 24,..., p−21 .$ Покажем, что никаких других биквадратичных вычетов нет. Рассмотрим произвольную четвертую степень натурального числа $b4.$ Ее основание, $b,$ поделим на $p$ с остатком: $b= kp+ l,l< p.$ Справедливо, что $b4 ≡ l4 ≡(p− l)4 (mod p),$ причем либо $l≤ p−21,$ либо $p− l≤ p−21.$ Поскольку множество биквадратичных вычетов определяется как множество остатков, которые дают четвертые степени натуральных чисел по модулю $p,$ утверждение доказано. Покажем теперь, что среди $( )4 14, 24,..., p−21$ есть одинаковые вычеты по модулю $p$ тогда и только тогда, когда $p= 4k+1$ для некоторого натурального $k.$ Ясно, что это утверждение равносильно нашей задаче.

Проведем рассуждение, являющееся цепочкой равносильных переходов. Среди

( ) 14, 24,..., p−-1 4 2

есть два равных остатка по модулю $p$ тогда и только тогда, когда существуют $p−1 k,l≤-2-,k⁄= l$ и $.. k4 − l4. p.$

k4− l4 =(k2+ l2)(k− l)(k+ l)

Ясно, что ни $k− l$ , ни $k+ l$ не делится на $p,$ поэтому $2 2 k ≡ −l (mod p).$ Следовательно, для $a,$ такого что $a< p$ и $2 k ≡a (mod p),$ справедливо, что и $a,$ и $− a$ являются квадратичными вычетами по модулю $p.$ Из мультипликативности символа Лежандра это означает, что $− 1$ является квадратичным вычетом по модулю $p,$ что верно для простых вида $4k+ 1$ и только для них (следует, например, из критерия Эйлера). Итак, мы доказали, что среди $( )4 14, 24,..., p−21$ есть два равных остатка по модулю $p$ тогда и только тогда, когда $p≡ 1 (mod 4),$ что и требовалось.