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

Остатки и сравнения по модулю → .07 Квадратичные вычеты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть $a ,a,...,a 1 2 p−21$ — все квадратичные вычеты по модулю $p.$ Для $k= 1,$ $2,$ $3,$ …, $p−1 2$ найдите

σk(a1,a2,...,ap−12 ) (mod p)

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

Квадратичными вычетами по модулю $p$ являются те и только те числа, которые удовлетворяют сравнению $a p−21-≡1 (mod p).$ Давайте рассмотрим многочлен $p−21- x − 1.$ Его корни $a1,a2,...,ap−21.$ Если вспомнить теорему Виета, становится ясно, что $σk(a1,a2,...,ap−21) (mod p)$ — модуль коэффициента при $p−1 x 2 −k$ у рассмотренного многочлена, умноженный на $(−1)k.$ Все коэффициенты, кроме свободного члена, равны $0,$ значит, соответствующие сигмы сравнимы с $0,$ а $σp−1≡ (−1)p−21-(mod p). 2$

Ответ:

$σ ≡ 0 (mod p) k$ при $k < p−1- 2$ и $σ ≡(−1)p−21(mod p) p−21-$

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

Задача 3#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)$ – натуральное число. Это невозможно, поэтому мы достигли противоречия.

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

Задача 4#84254

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

2 2 x +y ≡ 1 (mod p)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Можно умножить исходное равенство на (1/y)² - квадрат остатка, обратного к y, при ненулевом y. Сделайте необходимые преобразования и примените формулу разности квадратов.

Подсказка 4

Пара (x, y) при ненулевом y является решением тогда и только тогда, когда когда 1/y-x/y сравнимо с a и 1/y+x/y сравнимо с 1/a для некоторого данного остатка a. Таким образом, необходимо найти количество решений полученной системы.

Подсказка 5

Если a+1/a обратим, то x и y восстанавливается однозначно. Докажите, что все полученные пары различны. Что можно сказать об a, если a+1/a необратим?

Подсказка 6

Тогда -1 является квадратичным вычетом. Как известно, это возможно только при p, которые имеют вид 4k+1. Закончите разбор этого случая, не забудьте учесть решения при y = 0.

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

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

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$ решения.

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

Задача 5#89724

Докажите, что для любого простого $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

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

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

Задача 6#89726

Докажите, что уравнение $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,$ что невозможно.

Курсы

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

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

Задача 7#89728

Сколько существует вычетов $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$ имеем

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$

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

Задача 8#89729

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

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

Подсказка 1

Что в терминах квадратичных остатков дает условие о том, что p не является делителем n²+3n+11 ни для какого натурального n?

Подсказка 2

Покажите, что сравнение ax²+bx+c≡0 (mod p) имеет решения тогда и только тогда, когда дискриминант квадратного уравнения является квадратичным вычетом по модулю p. Так, -35 является квадратичным невычетом по рассматриваемому модулю. Как можно перейти от уравнения 2a⁴+9a³−a²+9a+2 к квадратному?

Подсказка 3

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

Подсказка 4

Можно ввести замену x=a+1/a. Полученное уравнение будет является квадратным относительно x и иметь корни -5 и 1/2. Так, число a такое, что 2a⁴+9a³−a²+9a+2 кратно p, существует тогда и только тогда, когда существует a для которого выполнено сравнение a²+5a+1≡0 (mod p) или 2a²-a+2≡0 (mod p). Вспомните критерий, который помогает переформулировать данную делимость в терминах квадратичных вычетов.

Подсказка 5

Хотя бы одно из сравнений верно только в том случае, если хотя бы одно из чисел 21 и -15, которые являются дискриминантами соответствующий квадратных уравнений, является квадратичным вычетом по модулю p. Как это можно доказать, используя то, что -35 не является квадратичным вычетом по указанному модулю.

Подсказка 6

Каждое из чисел 21 и -15 не взаимнопросто с -35. Этим можно воспользоваться, если выразить если переписать условие на то, что каждое из чисел является квадратичным невычетом по модулю 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.$

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

Задача 9#97050

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

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

Подсказка 1

Как доказать, что число составное? Нужно найти у него делитель! Покажите, что 2^q-1 кратно p.

Подсказка 2

Достаточно показать, что 2^((p-1)/2) - 1 кратно p, то есть, что 2 - квадратичный вычет. Нужно проверить что -1/q - квадратичный вычет. Как это сделать?

Подсказка 3

Нужно проверить, что -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

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

Задача 10#97051

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

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

Подсказка 1

На деле речь идет про простые числа вида 5k-1. Как вообще доказывать, что простых чисел какого-то вида бесконечно много? Можно найти число, которое не кратно всем числам такого вида и понять, что оно должно быть кратно. Как можно искать такое число?

Подсказка 2

Если перемножить квадраты всех простых чисел вида 5k-1, домножить на 4 и вычесть 5, то получится число нужного вида. Почему у него есть делитель вида 5k-1?

Подсказка 3

Поймите, воспользовавшись квадратичным законом взаимности, что у построенного числа все делители вида 5k+1 и 5k-1. Почему не могут все быть вида 5k+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$ — противоречие.

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

Задача 11#97052

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

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

Подсказка 1

Как удобно воспринимать делимость? Делимость в первую очередь означает, что если 2^n-1 делится на p, то 3^n-1 делится на p. Как этим пользоваться?

Подсказка 2

С чем может быть сравним простой делитель по модулю 12? Как это понять? Разберите 2 случая по модулю 4, а из квадратичного закона взаимности получите сравнение по модулю 3.

Подсказка 3

Поймите, что делители 2^n-1 по модулю 12 бывают только 1 или -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$

Интенсивы

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

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

Задача 12#97387

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

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

Подсказка 1

Случай p = 2 тривиален. В остальных случаях легко видеть, что каждое сравнение y² ≡ x³ + 1 (mod p) имеет два решения относительно y, кроме случая, когда правая часть нулевая, если разрешимо. А сколько есть таких c, что при x³ + 1 ≡ c (mod p) это сравнение разрешимо?

Подсказка 2

Верно! Это число квадратичных вычетов по модулю p, то есть (p-1)/2 ненулевых и 1 нулевой. Тогда решений относительно y точно не более p-1 + 1 = p. Осталось доказать, что у каждого y может быть только один x. Как это сделать?

Подсказка 3

Попробуем доказать, что сравнение x³ + 1 ≡ c (mod p) имеет ровно одно решение для каждого c. Для этого достаточно доказать это утверждение для сравнения x³ ≡ t (mod p). Как это сделать?

Подсказка 4

Верно! Заметим, что по малой теореме Ферма можно t сравнить с остатком t, умноженным на (p-1)-ю степень числа x. Вспомним, что p = 3k + 2. Какой вывод можно сделать?

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

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

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

Задача 13#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$ — любое целое число

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

Задача 14#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 ,$ так что это очевидно.

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

Задача 15#104585

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

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

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

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

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

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

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

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

Задача 17#104587

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

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

Подсказка 1

Правая часть похожа на сумму кубов. Чего не хватает?

Подсказка 2

Единицы. Прибавим 1 к обеим частям и разложим правую по формуле суммы кубов. Что можно сказать о четности чисел x, y?

Подсказка 3

Если y чётно, то x нечётно, значит, левая часть не делится на 4, а правая делится. Если правая часть делится на некоторое просто p, то делится и левая, а значит, -1 квадратичный вычет по данному модулю. При всех ли p это возможно?

Подсказка 4

Нет, это неверно, например, если p сравнимо с 3 по модулю 4. Для того, чтобы показать, что исходное уравнение не имеет решений осталось доказать, что правая часть делится на простое число вида 4k+3.

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

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

Ответ:

Решений нет

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

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

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

Задача 19#122189

Поймем для каких простых $p$ число $r⁄≡ 0 (mod p)$ является квадратичным вычетом.

(a) Рассмотрим множество вычетов $p−1 S ={r⋅1,r⋅2,r⋅3,...,r⋅ 2 }.$ Докажите, что для каждого ненулевого $a∈𝔽p$ ровно один из вычетов $a,p − a$ содержится в $S;$

(b) Отождествим каждый элемент $S$ с целым числом из множества ${1,2,3,...,p − 1}.$ Докажите, что $(r) ν(r) p =(−1) ,$ где $ν(r)$ — количество элементов в $S,$ больших $p−12 .$

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

(a) Так как $r⁄≡p 0,$ умножение на $r$ в поле $𝔽p$ является биекцией. Следовательно, множество $S$ содержит $p−-1 2$ различных ненулевых вычетов.

Для любого $a⁄≡p 0:$

Если $a ∈S,$ утверждение доказано.
Если $a ∕∈S,$ то $a≡p r⋅k$ для некоторого $p−1 k> 2 .$ Заметим, что:
$r⋅k≡ −r⋅(p− k) (mod p).$
Поскольку $p− k≤ p−21,$ то $p− a≡ r⋅(p− k) (mod p)$ принадлежит $S.$

Если бы $a$ и $p− a$ одновременно принадлежали $S,$ то пусть $a≡p r⋅k, p− a≡p r ⋅m,$ причем $p−1 m,k≤ 2 ⇒ m + k≤ p− 1$ тогда

0≡p a +(p− a) ≡p r⋅(m+ k)⁄≡p 0

(b) Рассмотрим произведение $∏ s∈Ss.$ Каждый вычет $s ∈S$ можно представить в диапазоне $p−-1 1≤ s≤ 2 .$ Если $p−1 s> 2 ,$ заменим его на $p− s,$ что изменяет знак произведения на $− 1.$ Тогда $ν(r)$ — количество таких замен.

∏ ( ) s≡p (−1)ν(r)⋅ p−-1! , s∈S 2

∏ ( ) s≡p rp−21-⋅ p−-1! . s∈S 2

Приравнивая их, получаем:

p−1- ν(r) r 2 ≡ (−1) (mod p).

По критерию Эйлера:

(r) p−1- p ≡ r 2 (mod p),

откуда:

( ) rp = (−1)ν(r).

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

Задача 20#122202

Докажите, что $2$ является квадратичным вычетом по модулю $p$ тогда и только тогда, когда $p≡ ±1 (mod 8).$

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

Рассмотрим множество вычетов $S = {2⋅1,2⋅2,2⋅3,...,2⋅ p−1}. 2$ Обозначим через $ν(2)$ количество элементов $s∈ S,$ больших $p−1. 2$ Тогда:

( 2) ν(2) p = (−1) .

Значит $2$ — вычет $⇐ ⇒ ν(2)≡2 0.$ Разберем случаи:

Случай $p ≡1 (mod 4):$ Тогда для всех $k ≤ p−14-$ вычеты $2k≤ p−21,$ а оставшиеся больше, то есть
$ν(2)= p−-1. 4$
Тогда:
$2-квадратичный вычет, при условии p ≡4 1 ⇐⇒ p−-1≡2 0 ⇐ ⇒ p≡8 1. 4$
Случай $p ≡− 1 (mod 4):$ Тогда для $k≥ p+1, 4$ вычеты $2k≥ p+1, 4$ отсюда аналогично:
$p+-1 ν(2)= 4 .$

$2 -квадратичный вычет, при условии p≡ −1 ⇐⇒ p+-1≡ 0 ⇐ ⇒ p≡ −1. 4 4 2 8$

Объединяя оба случая, получаем требуемое.

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

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