2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Квадратичное сравнение [Теория чисел]
Сообщение24.07.2014, 20:15 
Аватара пользователя
Здравствуйте, друзья!

Пусть $p$--простое число, большее чем 2. Используя критерий Эйлера, т.е. $a^{\frac{p-1}{2}}\equiv \left ( \frac{a}{p} \right ) \pmod p$ и то, что $\left ( \frac{2}{p} \right )=(-1)^{\frac{p^2-1}{8}}$ указать способ разыскания решений сравнения $$x^2\equiv a \pmod p; \quad p=8m+5$$

Моя попытка доказательства: Чтобы сравнение было разрешимо нужно, чтобы $a^{\frac{p-1}{2}}=a^{4m+2}\equiv 1 \pmod p$, а отсюда следует, что $(a^{2m+1}-1)(a^{2m+1}+1)\equiv 0 \pmod p$. Очевидно, что только один из сомножителей может делиться на $p$ (оба не могут, иначе их разность, т.е. $2$ делилось бы на $p>2$)
Первый случай: Если $a^{2m+1}\equiv 1 \pmod p$, то тогда $a^{2m+2}\equiv a \pmod p$ и в качестве решений можно взять $x\equiv\pm a^{m+1} \pmod p$

А как быть со случаем когда $a^{2m+1}+1\equiv 0 \pmod p$? И как(где) тут использовать то, что $\left ( \frac{2}{p} \right )=(-1)^{\frac{p^2-1}{8}}$?

С уважением, Whitaker.

 
 
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 10:24 
Whitaker в сообщении #889967 писал(а):
И как(где) тут использовать то, что $\left ( \frac{2}{p} \right )=(-1)^{\frac{p^2-1}{8}}$?
Тут такое дело: при $p \equiv 5 \pmod{8}$ двойка есть квадратичный невычет, т.е. $2^{(p-1)/2} \equiv -1 \pmod{p}$. Вот этим и нужно воспользоваться.

 
 
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 10:31 
Аватара пользователя
Вроде догадался.
В этом случае по критерию Эйлера будет: $2^{4m+2}\equiv -1 \pmod p$ и тога мы получаем $(a^{m+1}2^{2m+1})^2\equiv a \pmod p$ и решениями сравнения в этом случае будут $x\equiv \pm a^{m+1}2^{2m+1} \pmod p$

 
 
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 11:07 
Да, всё окей.

Кстати, можете подумать об алгоритме решения сравнения $x^2 \equiv a \pmod{p}$ в случае произвольного простого $p$. Основные идеи этого алгоритма в разобранном частном случае уже присутствуют.

 
 
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 11:45 
Аватара пользователя
nnosipov
Кстати, я как раз думал об этом вопросе на днях и кое-какие частные случаи разобрал.

P.S. Сейчас я думаю над такой задачей.
Указать возможно более простой способ разыскания решений сравнений вида $x^2\equiv a \pmod p; \quad p=8m+1$ в случае, когда известен некоторый квадратичный невычет $N$ по модулю $p$

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

 
 
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 12:52 
Аватара пользователя
Может что нибудь посоветуете по этой задаче?

 
 
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 13:39 
Whitaker в сообщении #890166 писал(а):
Может что нибудь посоветуете по этой задаче?
Записать $(p-1)/2=2^sl$, где $l$ нечётно. Если $s=0$ (двоек нет), то всё замечательно. Значит, в случае $s>0$ надо из показателя как-то двойки изгнать. Вот для этого квадратичный невычет $N$ и нужен, чтобы последовательно эти $s$ двоек убрать. (Для простого $p \equiv 5 \pmod{8}$ это пришлось делать один раз, при этом можно было взять $N=2$.)

 
 
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 15:07 
Аватара пользователя
nnosipov в сообщении #890187 писал(а):
Записать $(p-1)/2=2^sl$, где $l$ нечётно. Если $s=0$ (двоек нет), то всё замечательно. Значит, в случае $s>0$ надо из показателя как-то двойки изгнать. Вот для этого квадратичный невычет $N$ и нужен, чтобы последовательно эти $s$ двоек убрать. (Для простого $p \equiv 5 \pmod{8}$ это пришлось делать один раз, при этом можно было взять $N=2$.)
Спасибо большое Вам за ценную подсказку! Вроде все получилось правильно.
Оказывается я сделал тоже самое на бумаге, но не смог понять где именно нужно использовать то, что $\left(\frac{N}{p}\right)=-1$.
Спасибо еще раз! :-)

 
 
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение26.07.2014, 11:34 
Ну так ведь Вы сами сказали что оба сомножителя не смогут одновременно делиться на $p$.Один из них всегда делится на $p$,Вы даже привели пример.Так что второй просто не может и нечего рассматривать второй случай.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group