Квадратичные вычеты
Ошибка.
Попробуйте повторить позже
Дано простое число 
Докажите, что сравнение 
имеет не более 
решений по модулю
Подсказка 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. Какой вывод можно сделать?
В тривиальном случае 
имеем решения 
и 
и наоборот.
Для начала покажем, что для каждого конкретного 
сравнение 
имеет единственное решение. Для 
этим
решением является 
Пусть теперь 
Тогда заметим, что в силу малой теоремы Ферма при 
выполняется следующая
цепочка сравнений
Таким образом, 
Теперь вернемся к исходному сравнению. Оно имеет вид 
Это сравнение имеет решение в
точности, когда 
является квадратичным вычетом по модулю 
Всего ненулевых квадратичных вычетов имеется ровно 
а
также нулевой вычет. В каждом случае для ненулевого вычета имеем не более двух решений 
и 
а для нулевого вычета единственное
решение 
причем, для каждого вычета, как показано ранее, имеется единственный 
Таким образом, пар вычетов-решений не
более, чем 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
