2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение21.08.2014, 09:50 
Заслуженный участник
Аватара пользователя


24/02/12
1842
Москва
Ну как же. Вы каждому представлению $m=x^2+y^2$ с $(x, y)=1$ ставите в соответствие решение сравнения $s$ так, чтобы $xs\equiv y(\mod m) $. Надо показать, что это инъекция, то есть разным представлениям отвечают разные $s$. А также, что это сюръекция, то есть для каждого решения сравнения $s$ найдется соответствующее представление. Выше Вы строили такое представление, но будет ли $ts\equiv Q(\mod m) $ или $Qs\equiv t(\mod m) $?

 Профиль  
                  
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение21.08.2014, 14:39 
Аватара пользователя


12/01/11
1315
Москва
Уважажемый ex-math не кажется ли Вам, что мы немного сошли с пути решения? Просто я сильно запутался во всем этом.
Вот у меня есть такой план доказательства. Сейчас я его напишу и я был бы Вам очень признателен если бы Вы его прочитали и указали бы на недостатки, если они есть.

У нас есть два множества $$r_2(m)=\{(x,y)=1, x>0, y>0 \mid x^2+y^2=m\}$$ $$S(m)=\{z\pmod{m}\mid z^2+1\equiv 0 \pmod{m}\}$$
Нам надо показать, что $|r_2(m)|=|S(m)|$
Замечание: здесь как я понимаю пользуются следующим фактом из теории множеств: Если у Вас есть два конечных множества $A$ и $B$ и отображение $f:A\rightarrow B$ -- биективное, то $|A|=|B|$.
Доказательство: Пусть у нас имеется некоторое представление числа $m=x^2+y^2,$ где $x>0, y>0, (x,y)=1$. Тогда $x^2\equiv -y^2\pmod{m}$ да еще $(x,m)=1$. Понятно, что существует единственно $s$ такое, что $xs\equiv y \pmod{m}$ и возводя это в квадрат и учитывая, что $(x,m)=1$ получаем, что $s^2+1\equiv 0 \pmod{m}$.

Таким образом, я каждому представлению $m$ суммой квадратов поставил в соответствие решение сравнения, т.е. рассмотрел отображение $f:r_2(m)\rightarrow S(m)$. Теперь следует показать, что это отображение биективное, т.е. оно сюръективное и инъективное.

Сюръекция: Надо показать, что каждый элемент множества $S(m)$ обладает прообразом из $r_2(m)$.

Пусть $z_0$ - решение сравнения $z^2+1\equiv 0 \pmod{m}$. Тогда мы показали(не буду все заново переписывать), что $m=Q^2+|\theta\sqrt{m}|^2,$ причем $(Q,\theta\sqrt{m})=1$. Сюръекция доказана.

Инъекция: Следует показать, что разным элементам из $r_2(m)$ соответствуют разные элементы из $S(m)$.
Пусть это не так, т.е. разные элементы из $r_2(m)$ переходят в один и тот же элемент из $S(m)$.
Тогда $s_1\equiv s_2\pmod{m}$ но так как $x_is_i\equiv y_i\pmod{m}$ для $i=1,2$, то после несложных модулярных преобразований получаем, что $y_1x_2\equiv y_2x_1\pmod{m}$. Нетрудно проверить, что $-(m-1)<y_1x_2-y_2x_1<m-1$ но из условия делимости получаем, что $y_1x_2=y_2x_1$ и используя то, что $(x_1, y_1)=(x_2, y_2)=1$ получаем, что $x_1=x_2$ и $y_1=y_2$. Противоречие.
Инъекция доказана.

Таким образом, отображение $f:r_2(m)\rightarrow S(m)$ является биективным и отсюда получаем, что $|r_2(m)|=|S(m)|$.

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


24/02/12
1842
Москва
Проблема только с сюръекцией. Вы пока нашли по данному $z_0$ какую-то пару $(Q,\theta\sqrt m) $. А надо именно прообраз, то есть проверить, что $f(Q,\theta\sqrt m)=z_0$.

 Профиль  
                  
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение22.08.2014, 16:08 
Аватара пользователя


12/01/11
1315
Москва
ex-math
Я вот подумал и есть такой эскиз доказательства сюръективности.
Пусть $z_0\in S(m)$ тогда $z_0^2+1\equiv 0 \pmod{m}$. Можно написать, что $z_0Q=Pm+t,$ где $t=\theta\sqrt{m}$.
Получаем, что $m=|t|^2+Q^2$, причем $(t,Q)=1$.
Покажем, что $f(t,Q)=z_0$.
Нетрудно понять, что $(t,m)=1$ тогда существует единственное $s$ такое, что $ts\equiv Q\pmod m$ и отсюда получаем, что
$Q^2\equiv t^2s^2\equiv -t^2 \pmod m$ и отсюда получаем, что $s^2\equiv -1\pmod{m}$
Так как $t=z_0Q-Pm,$ то получаем, что $(z_0Q-Pm)s\equiv Q\pmod m$ и отсюда получаем $z_0Qs\equiv Q\pmod{m}$ и получаем, что
$z_0s\equiv 1\pmod{m}$ и возводя это в квадрат и используя то, что $s^2\equiv -1\pmod{m}$ получаем, что $z_0^2+1\equiv 0 \pmod m$
Что скажете?

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


24/02/12
1842
Москва
Whitaker в сообщении #898393 писал(а):
Пусть $z_0\in S(m)$ тогда $z_0^2+1\equiv 0 \pmod{m}$. Можно написать, что $z_0Q=Pm+t,$ где $t=\theta\sqrt{m}$.
Получаем, что $m=|t|^2+Q^2$, причем $(t,Q)=1$.
Все гораздо проще. Если $t> 0$, то $Qz_0\equiv t\pmod{m} $ и искомый прообраз $m=Q^2+t^2$. Если $t<0$, то $|t|z_0\equiv -Qz_0^2\equiv Q\pmod{m} $ и искомый прообраз $m=|t|^2+Q^2$.

 Профиль  
                  
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение23.08.2014, 07:41 
Аватара пользователя


12/01/11
1315
Москва
ex-math разрешите задать такой вопрос?
Вы говорили, что $\theta^2m$ не делится на $m$? Можно ли провести нижеуказанное рассуждение?
Whitaker в сообщении #897089 писал(а):
Хотя у меня есть предположение, что $\theta\neq 0$. Почему?
Ну пусть $\theta=0,$ тогда $\dfrac{z}{m}=\dfrac{P}{Q}$, но из условия $z^2+1\equiv 0 \pmod{m}$ следует, что $\text{gcd}(z,m)=1$. Кроме того, $\text{gcd}(P,Q)=1$ и $0<Q\leqslant \sqrt{m}$. Получаем явное противоречие.
Вы согласны?

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


24/02/12
1842
Москва
Да, все верно.

 Профиль  
                  
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение23.08.2014, 17:50 
Аватара пользователя


12/01/11
1315
Москва
ex-math
Все заново прочитал и разобрал. Теперь действительно все понятно и все стало на свои места. Большое Вам спасибо за помощь! Благодарю! :-)

P.S. Есть еще такая задача: Пусть $a$ одно из чисел $2$ и $3$. Доказать, что число представлений простого $p$ в виде $p=x^2+ay^2, x>0, y>0$ равно половине числа решений сравнения $z^2+a\equiv 0\pmod{p}$
Я полагаю, что для решения этой задачи наверное применимы аналогичные рассуждения. Верно?

P.P.S. Хотя вряд ли такой подход пройдет. Здесь ключевое слово половина числа решений

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


24/02/12
1842
Москва
Если $-a$ -- квадратичный невычет, то никаких представлений нет, здесь все ясно. Если вычет, то надо показать существование и единственность представления. Давайте опять попробуем через теорему Дирихле.

 Профиль  
                  
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение28.08.2014, 10:51 
Аватара пользователя


12/01/11
1315
Москва
ex-math
Я подумал про эту задачу пару дней, но особо никаких продвижений нет. Напишу то, что у меня есть. Буду рассматривать случай $a=2$ для удобства.
Понятно, что если $-2$ -- кв. невычет, то таких представлений не существует.
Предположим, что $-2$ -- кв. вычет, тогда число решений сравнения $z^2+2\equiv 0 \pmod{p}$ равно двум. В таком случае надо показать, что число представлений простого $p$ существует и единственно!
Пусть $z_0$ -- решение сравнения и тогда $\dfrac{z_0}{p}=\dfrac{P}{Q}+\dfrac{\theta}{Q\sqrt{p}}$ и отсюда получаем: $z_0Q=Pp+\theta\sqrt{p}$. Подставляя все это "хозяйство" в сравнение получаем, что $t^2+2Q^2\equiv 0 \pmod{p}$, но так как $0<t^2+2Q^2<3p$. Значит, $t^2+2Q^2=p$ либо $t^2+2Q^2=2p$.
В первом случае все отлично.
Во втором случае $2\mid t^2$ и следовательно $2\mid t$, т.е. $t=2t_1$ и тогда получаем: $p=Q^2+2t_1^2$.
Но как показать, что такое представление единственно у меня не получается.

 Профиль  
                  
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение28.08.2014, 22:15 
Аватара пользователя


12/01/11
1315
Москва
ex-math
Я вроде придумал как это сделать завтра напишу так как сейчас под рукой увы нет компьютера :-(

 Профиль  
                  
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение29.08.2014, 10:34 
Аватара пользователя


12/01/11
1315
Москва
Напишу для случая $a=2$ т.к. для $a=3$ аналогичное рассуждение.
Пусть простое $p>2$ имеет два представления. Скажем, $p=x^2+2y^2$ и $p=z^2+2t^2$, где $x,y,z,t>0$ и $(x,y)\neq (z,t)$. Будем считать, что $\text{gcd}(x,y)=\text{gcd}(z,t)=1$, иначе получается противоречие.

Отсюда получаем, что: $p^2=(x^2+2y^2)(z^2+2t^2)=(xz+2yt)^2+2(xt-yz)^2=(xz-2yt)^2+2(xt+yz)^2$.

Рассмотрим следующее: $(xt+yz)(xz+2yt)=tz(x^2+2y^2)+xy(z^2+2t^2)=p(xy+tz)$. Значит, $p\mid (xt+yz)(xz+2yt)$ и отсюда получаем, что: $p\mid xt+yz$ либо $p\mid xz+2yt$
Первый случай: Пусть $p\mid xt+yz$ и отсюда получаем, что $p\mid p^2-(xz-2yt)^2$ и значит, $p\mid xz-2yt$. Следовательно, $xt+yz=pk, xz-2yt=pj,$ где $k,j\in\mathbb{Z}$. Тогда $(pj)^2+2(pk)^2=p^2$, но сокращая обе части имеем $j^2+2k^2=1$. Но так как $x,y,z,t>0$, то $k>0$ и получаем сразу противоречие.

Второй случай: Пусть $p\mid xz+2yt$ и отсюда $p\mid p^2-2(xt-yz)^2$. Значит, $p\mid 2(xt-yz)^2$, но так $\text{gcd}(p,2)=1$ имеем, что $p\mid xt-yz$. Таким образом, получаем, что $xz+2yt=pk$ и $xt-yz=pj$. Тогда, $(pk)^2+2(pj)^2=p^2$ и т.к. $x,y,z,t>0$, то $k>0$ и еще $k^2+2j^2=1$. Значит, $k=1$ и $j=0$. В силу того, что $j=0$ мы имеем $xt=yz$, используя то, что $\text{gcd}(x,y)=\text{gcd}(z,t)=1$ мы получаем, что $x=z, y=t$. Снова противоречие.

Корректно ли такое доказательство?
P.S. Что-нибудь по-легче придумать мне не удалось.

 Профиль  
                  
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение29.08.2014, 11:09 
Заслуженный участник


20/12/10
6564
Whitaker в сообщении #901585 писал(а):
Напишу для случая $a=2$ т.к. для $a=3$ аналогичное рассуждение.
Ср. с доказательством теоремы 18 в книге Серпинского "Что мы знаем и чего не знаем о простых числах", стр. 53.

 Профиль  
                  
 
 Re: Сумма двух квадратов и квадратичное сравнение [Теория чисел]
Сообщение29.08.2014, 16:42 
Аватара пользователя


12/01/11
1315
Москва
nnosipov
Да сравнил доказательства у него как-то "концовка" сразу получается. Прекрасно :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу Пред.  1, 2

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



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

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


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

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