2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



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


12/01/11
1320
Москва
Здравствуйте, друзья!

Пусть $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 
Заслуженный участник


20/12/10
8858
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 
Аватара пользователя


12/01/11
1320
Москва
Вроде догадался.
В этом случае по критерию Эйлера будет: $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 
Заслуженный участник


20/12/10
8858
Да, всё окей.

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

 Профиль  
                  
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 11:45 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 12:52 
Аватара пользователя


12/01/11
1320
Москва
Может что нибудь посоветуете по этой задаче?

 Профиль  
                  
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение25.07.2014, 13:39 
Заслуженный участник


20/12/10
8858
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 
Аватара пользователя


12/01/11
1320
Москва
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 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group