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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 2#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$ решения.

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

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

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

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

Задача 4#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,$ что невозможно.

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

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

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

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

Курсы

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

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

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

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

Задача 8#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$ — противоречие.

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

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

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

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

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

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

Интенсивы

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

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

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

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

Подсказка 1

В уравнениях с целыми числами дроби выглядят не очень приятно. Избавьтесь от них и предположите противное.

Подсказка 2

Если сумма квадратов a, b, c, d делится на p=4k+3, то по модулю p можно выразить a через остальные переменные. Этот шаг сохраняет все условия, поэтому его следует сделать. Теперь у нас есть какое-то равенство и модуль p. Напишите вместо знака равно сравнение.

Подсказка 3

Тождество получилось 6 степени. Попробуйте разложить его на квадратные множители. Как их найти? В условии есть p=4k+3 и квадраты. Как их связать? На самом деле сумма квадратов не бывает равна нулю по модулю p. Докажите это и поймите из этого разложение на множители.

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

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

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

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

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

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

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

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

Задача 15#74881

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

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

Запишем уравнение в виде $x2+ 4=y3− 1.$ Из такой записи очевидно, что $y > 1.$ Докажем, что $y3 − 1$ всегда делится на некоторое простое $p ≡3 (mod 4).$ Будем пользоваться тем, что любое число, сравнимое с $3$ по модулю $4,$ имеет простой делитель вида $4k +3,$ так как произведение любого набора таких чисел вида $4k+1$ само имеет остаток $1$ по модулю $4.$

(a) $y$ – четное число. В таком случае $y3− 1≡ 3 (mod 4).$ Остается применить утверждение.

(b) $y ≡1 (mod 4).$ В таком случае $2 y +y +1≡ 3 (mod 4).$ Применим утверждение. Так как $3 .. 2 y − 1 . y +y +1,$ оно тоже имеет простой делитель вида $4k+3.$

Итак, $x2+ 4 ... p$ для некоторого $p= 4k +3.$ Значит, $− 4$ является квадратичным вычетом по модулю $p.$ Число $4$ является квадратичным вычетом по любому простому модулю, и из мультипликативности символа Лежандра тогда следует, что $− 1$ является вычетом по модулю $p= 4k+3.$ Однако из общей теории мы знаем, что $− 1$ является вычетом по простому модулю $p$ тогда и только тогда, когда $p= 4k +1.$ Поскольку мы пришли к противоречию, уравнение из условия задачи решений не имеет.

Ответ:

Решений нет

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

Задача 16#74882

Докажите, что для любого натурального $n$ любой простой делитель числа $n4− n2+ 1$

(a) сравним с 1 по модулю $4;$

(b) сравним с 1 по модулю $12.$

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

Подсказка 1, пункт а

Как доказывать, что все простые делители числа вида 4k+1? Например, можно сказать, что -1 является квадратичным вычетом. Откуда это взять? Вспомните, в какой формуле сокращенного умножения есть что-то похожее на n^4-n^2+1.

Подсказка 1, пункт б

Как такое можно доказывать? Можно найти показатель числа n по модулю 12. Поймите, что показатель может быть лишь 4 или 12. Но 4 нас не устраивает. Как отсеять этот вариант?

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

(a) Ясно, что $2$ не является делителем $n4− n2+ 1.$ Любой простой нечетный делитель числа $n4− n2+ 1$ является делителем и $n6+ 1,$ так как $n6+1 =(n2+ 1)(n4− n2 +1).$ Итак, если $. n6 +1= (n3)2+ 1.. p,$ то $− 1$ является квадратичным вычетом по модулю $p.$ Как мы уже ни раз отмечали, $− 1$ является квадратичным вычетом по модулю $p$ тогда и только тогда, когда $p =4k+ 1.$

(b) Найдем показатель $T$ числа $n$ по модулю $p.$ Поскольку $6 n ≡− 1 (mod p),$ то $12 n ≡ 1 (mod p),$ значит $.. 12. T.$ Так как $. n6 ≡ −1 (mod p),6 ⁄.. T,$ значит либо $T = 4,$ либо $T = 12.$ Если $T =4,$ то $. n4− 1= (n2+1)(n2 − 1).. p,$ откуда $n2 ≡ ±1 (mod p).$ Тогда $n4− n2+ 1≡ 2± 1⁄≡0 (mod p)$ – противоречие.

Итак, $T = 12.$ Согласно малой теореме Ферма, $p−1 n ≡ 1 (mod p),$ откуда $.. p− 1 . 12$ или $p≡ 1 (mod p)$ – что и требовалось доказать.

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

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

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

Задача 17#74883

Последовательность натуральных чисел $a,a ,... 1 2$ задана рекуррентно: $a = 3 1$ , $a = a2 i+1 i$ при всех натуральных $i$ . Пусть $2n m = 2 +1.$

(a) Докажите, что $a2n +1$ делится на $m,$ если $m$ — простое;

(b) Докажите, что $a2n + 1$ не делится на $m,$ если $m$ — составное.

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

Подсказка 1, пункт а

В этой задаче можно явно написать формулу a_i. Что делать дальше? Примените критерий Эйлера и воспользуйтесь тем, что 3 не является квадратичным вычетом.

Подсказка 1, пункт б

Вспомните про существование показателя. По какому модулю и какому основанию стоит его рассмотреть?

Подсказка 2, пункт б

Рассмотрите показатель числа 3 по модулю m. Поймите, что он должен быть равен m-1. Почему это плохо? Воспользуйтесь теоремой Эйлера и придите к противоречию.

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

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

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

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

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

Задача 18#74910

Решите уравнение в целых числах $x3 − x= 9(5y2− 1).$

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

Перепишем уравнение в виде $(x− 1)x(x+ 1)= 9(5y2− 1).$ Отметим, что правая часть не кратна $27,$ так как $5y2 ≡ 0 (mod 3)$ либо $2 5y ≡ 2 (mod 3).$ Пусть $p$ – простой делитель левой части, не равный $2$ или $3.$ Ясно, что $p⁄= 5,$ так как правая часть уравнения не делится на $5.$ Тогда $2 5y ≡1 (mod p),$ откуда $2 5y ,$ разумеется, является квадратичным вычетом. Из мультипликативности символа Лежандра, $(5y2) (5) (y2) p = p ⋅ p =1.$ Ясно, что $(y2) p = 1,$ поэтому $5$ является квадратичным вычетом по модулю $p.$ Запишем квадратичный закон взаимности:

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

откуда $p$ является квадратичным вычетом по модулю $5.$ Согласно критерию Эйлера, $5−1 p-2-= p2 ≡ 1 (mod 5).$ Таким образом мы получили, что любой простой делитель $(x − 1)x(x+ 1),$ отличный от $2$ и $3,$ сравним с $± 1$ по модулю $5.$

Среди чисел $x − 1, x, x +1$ ровно одно кратно $3,$ поэтому оно же и кратно $9 ≡−1 (mod 5).$ Если какое-то из этих трех чисел является нечетным, то оно сравнимо с $±1$ по модулю $5,$ поскольку оно делится на $3$ в четной степени, а все остальные его простые делители сравнимы с $± 1$ по модулю $5.$ Если $x − 1, x +1$ нечетные, то обязательно $x− 1≡ −1 (mod 5),x +1≡ 1 (mod 5),$ но тогда $.. x . 5,$ хотя правая часть не кратна $5$ – противоречие. Получается, что $x$ – нечетное. По замечанию, $x ≡±1 (mod 5).$ Но тогда либо $x − 1,$ либо $x+ 1$ делится на $5,$ хотя правая часть не кратна $5$ – противоречие.

Выходит, что у $(x− 1)x(x+ 1)$ нет других простых делителей кроме $2$ и $3.$ Так как одно из трех чисел кратно $9,x+ 1≥ 9.$ Два других числа могут быть кратны только двум, поэтому оба должны быть степенью $2$ (причем, из-за неравенства, ненулевой). Ясно, что этими числами обязаны быть $x− 1$ и $x+ 1.$ Две степени двойки отличаются на $2$ только если одна из них равна $2,$ а другая $4.$ В таком случае $x +1= 4,$ что противоречит неравенству выше. Таким образом, у уравнения решений нет.

Ответ:

Нет решений

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

Задача 19#75629

Пусть $a ,a,...,a 1 2 p−21$ — все квадратичные вычеты по простому модулю $p> 7.$ Докажите, что $a3+ a3+ ...+ a3 ≡ 0 (mod p). 1 2 p−12-$

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

Подсказка 1

Работая с квадратичными вычетами, полезно написать многочлен x^((p-1)/2)-1. Откуда можно взять тут сумму кубов? Причем тут p>7?

Подсказка 2

Воспользовавшись теоремой Виета, выразите сумму кубов по модулю p. Поймите причем тут p > 7.

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

Рассмотрим многочлен $x(p−1)∕2− 1≡ 0 (mod p)$ над $ℤ . p$ Заметим, что $a$ будет корнем этого многочлена тогда и только тогда, когда $a$ квадратичный вычет по модулю $p.$ Тогда числа $a1,a2,...,ap−21$ и будут корнями этого многочлена.