2014 dxdy logo

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

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


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


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



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


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

Указать способ решения сравнения $x^2\equiv 1 \pmod m$, основанный на том обстоятельстве, что указанное сравнение равносильно такому: $(x-1)(x+1)\equiv 0 \pmod m$

Подскажите пожалуйста как тут действовать? Что-то сам не могу понять.

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

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


08/04/08
8504
Найдите $\gcd(x-1,x+1)$.
Вспомогательный вопрос: пусть $x,y$ неизвестны и взаимно просты и $m\mid x,y$ (другими словами, $xy\equiv 0\pmod m$), $m$ дано. Каковы все решения это делимости?
Можете также начать с рассмотрения решения сравнения $x^2\equiv 1\pmod p$.

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


12/01/11
1315
Москва
Уважаемый Sonic86
просто я не совсем понимаю то, что вы написали. А точнее связь написанного с исходной задачей.
Можете как-то пояснить

-- Ср авг 06, 2014 21:14:19 --

$\text{gcd}(x-1, x+1)$ равно 1 или 2, соответственно если $x$-нечетное или четное.

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


18/05/06
13319
с Территории
Ну если произведение двух чисел делится на $m$ (у Вас именно это и происходит), что это значит?

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


12/01/11
1315
Москва
Тогда один из них делится на какой-то делитель $d$, а другой на делитель $m/d$. Так да?

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


12/01/11
1315
Москва
Объясните пожалуйста смысл Вашего поста? Каким образом он относится к задаче?

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


12/01/11
1315
Москва
Пусть $m=2^{\alpha}p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Тогда число $m$ можно представить как $2^{\alpha}ab$, где $(a,b)=1$ ровно $2^k$ способами.
Пусть $\alpha=0$ тогда получается системы сравнений вида $x-1\equiv 0 \pmod a, \quad x+1\equiv 0 \pmod b$. Таких систем будет всего $2^k$. Как показать, что все их решения будут различными по модулю $ab$?

 Профиль  
                  
 
 Re: Квадратичное сравнение [Теория чисел]
Сообщение07.08.2014, 19:23 
Заслуженный участник
Аватара пользователя


18/05/06
13319
с Территории
Ну пусть $\alpha=0$. Пусть два решения одинаковы. В одном из них $x-1$ делится на одни простые, а $x+1$ - на все остальные. В другом (напоминаю, одинаковом с первым) то же самое, только наборы другие. В чём-то они совпадают, может быть, но в чём-то же должны и отличаться. Значит, какое-то простое $p$ входит и в $x-1$, и в $x+1$. Хорошо ли это?

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

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



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

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


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

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