Сумма двух квадратов и квадратичное сравнение [Теория чисел]

[ex-math]

Ну как же. Вы каждому представлению $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) $?

[Whitaker]

Уважажемый 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)|$.

[ex-math]

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

[Whitaker]

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$
Что скажете?

[ex-math]

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$.

[Whitaker]

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}$. Получаем явное противоречие.
Вы согласны?

[ex-math]

Да, все верно.

[Whitaker]

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. Хотя вряд ли такой подход пройдет. Здесь ключевое слово половина числа решений

[ex-math]

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

[Whitaker]

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$.
Но как показать, что такое представление единственно у меня не получается.

[Whitaker]

ex-math
Я вроде придумал как это сделать завтра напишу так как сейчас под рукой увы нет компьютера

[Whitaker]

Напишу для случая $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. Что-нибудь по-легче придумать мне не удалось.

[nnosipov]

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

Напишу для случая $a=2$ т.к. для $a=3$ аналогичное рассуждение.

Ср. с доказательством теоремы 18 в книге Серпинского "Что мы знаем и чего не знаем о простых числах", стр. 53.

[Whitaker]

nnosipov
Да сравнил доказательства у него как-то "концовка" сразу получается. Прекрасно