Квадратичное сравнение [Теория чисел]

[Whitaker]

Здравствуйте, друзья!

Пусть $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.

[nnosipov]

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}$. Вот этим и нужно воспользоваться.

[Whitaker]

Вроде догадался.
В этом случае по критерию Эйлера будет: $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$

[nnosipov]

Да, всё окей.

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

[Whitaker]

nnosipov
Кстати, я как раз думал об этом вопросе на днях и кое-какие частные случаи разобрал.

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

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

[Whitaker]

Может что нибудь посоветуете по этой задаче?

[nnosipov]

Whitaker в сообщении #890166 писал(а):

Может что нибудь посоветуете по этой задаче?

Записать $(p-1)/2=2^sl$, где $l$ нечётно. Если $s=0$ (двоек нет), то всё замечательно. Значит, в случае $s>0$ надо из показателя как-то двойки изгнать. Вот для этого квадратичный невычет $N$ и нужен, чтобы последовательно эти $s$ двоек убрать. (Для простого $p \equiv 5 \pmod{8}$ это пришлось делать один раз, при этом можно было взять $N=2$.)

[Whitaker]

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$.
Спасибо еще раз!

[marij]

Ну так ведь Вы сами сказали что оба сомножителя не смогут одновременно делиться на $p$.Один из них всегда делится на $p$,Вы даже привели пример.Так что второй просто не может и нечего рассматривать второй случай.