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

[Whitaker]

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

Доказать, что число представлений $m>1$ в виде $m=x^2+y^2,$ где $\text{gcd}(x,y)=1, x>0, y>0$ равно числу решений сравнения $z^2+1\equiv 0 \pmod m$.

Указание дано следующее: Пусть $\tau=\sqrt{m}$. Воспользовать представлением $\alpha=\frac{z}{m}$ согласно теореме Дирихле и рассмотреть сравнение, получаемое умножением $z^2+1\equiv 0 \pmod m$ на $Q^2$.

По теореме Дирихле получаем, что: для $\alpha=\frac{z}{m}$ и $\tau=\sqrt{m}$ существуют числа $P$ и $Q$ такие, что $\text{gcd}(P,Q)=1$ и $0<Q\leqslant \tau$ причем выполняется равенство $\alpha=\dfrac{P}{Q}+\dfrac{\theta}{Q\tau},$ где $|\theta|<1$.

Киньте пожалуйста какую-нибудь подсказку т.к. пока все очень темно.

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

[ex-math]

Whitaker
Вы же еще с прошлой задачей до конца не разобрались.
А здесь попробуйте подставить представление для $z$ в сравнение.

[Whitaker]

ex-math
С прошлой задачей я проде разобрался. Полностью выложил решение. Можете посмотреть.

-- Сб авг 16, 2014 19:00:16 --

ex-math в сообщении #896649 писал(а):

Whitaker
А здесь попробуйте подставить представление для $z$ в сравнение.

Для $z$ мы имеем такое представление: $z=\dfrac{mP}{Q}+\dfrac{m\theta }{Q\tau},$ где $\tau=\sqrt{m}$ и подставляя его в сравнение $Q^2(z^2+1)\equiv 0 \pmod{m}$ мы получаем такое сравнение $\theta^2m+2m\sqrt{m}P\theta\equiv -Q^2\pmod{m}$

[Whitaker]

А последнее сравнение можно написать вроде так: $(\theta\sqrt{m}+mP)^2+Q^2\equiv 0 \pmod m$

[ex-math]

Как ни удивительно, $\theta\sqrt m$ -- целое число. Убедитесь в этом и попробуйте использовать.

[Whitaker]

ex-math
Да действительно число $\theta\sqrt{m}\in \mathbb{Z}$ так как $\theta\sqrt{m}=zQ-Pm$.
Убедился в этом вчера, но кроме того у меня два таких замечания: Вот берем сравнение $z^2Q^2+Q^2\equiv 0 \pmod m$ и подставляем $zQ=Pm+\theta\sqrt{m}$ и получаем вот что:

$$P^2m^2+2Pm\sqrt{m}\theta+\theta^2m+Q^2\equiv 0 \pmod m$$

Во-первых первые три члена уходят и мы получаем, что $Q^2\equiv 0 \pmod m$ но так $0<Q\leqslant \sqrt{m}$ и отсюда следует, что $Q^2=m$ и что дальше в этом случае? Понятно, что если $m$--бесквадратное число, то тогда беда да и в случае квадратного тоже. Просто этот случай меня немного беспокоит.

Во-вторых можно еще написать так

$$\theta^2m+Q^2\equiv 0 \pmod m,$$

но мы имеем еще такую оценку $0<Q^2+\theta^2m<2m$ и отсюда следует, что $m=Q^2+\theta^2m=Q^2+(\theta\sqrt{m})^2$

Вот так у меня вроде получается. Но меня случай немного смущает, а именно то, что $m\mid Q^2$
P.S. Там ведь еще другие случаи есть, когда другие члены, содержащие $m$ можно убрать?! Был бы признателен, если бы Вы прокомментировали бы эти моменты.

[ex-math]

Первый вариант неверен, так как $\theta^2m$ не делится на $m$.
А второй правильный. Надо еще убедиться, что $Q$ и $\theta\sqrt m$ взаимно просты.
Давайте это число какой-нибудь буквой обозначим.

[Whitaker]

ex-math
1)Извиняюсь за глупый вопрос, но почему $\theta^2m$ не делится на $m$? Ведь $\theta^2m\in \mathbb{Z}$ и $0\leqslant\theta^2m<m$ и будет делиться при $\theta=0$
2) Не могу показать, что $Q$ и $\theta\sqrt{m}$ взаимно-простые. Пусть у них есть общий делитель $d>1$. Так как $m=Q^2+(\theta\sqrt{m})^2$, то получаем, что $d\mid m$. А дальше пока непонятно

[Whitaker]

ex-math
Подумав пару часов все-таки понял как доказать взаимную простоту чисел $\theta\sqrt{m}$ и $Q$
Так как $m=t^2+Q^2,$ где $t=\theta\sqrt{m}$ то тогда мы получаем вот что:

$$1=\dfrac{t^2+Q^2}{m}=\dfrac{(zQ-Pm)t+Q^2}{m}=\dfrac{zQt-Pmt+Q^2}{m}=\dfrac{zQ(zQ-Pm)-Pmt+Q^2}{m}=$$$$=\dfrac{Q^2(z^2+1)}{m}-zQP-Pt\equiv -Pt\pmod Q$$

Отсюда следует, что $\text{GCD}(Q,t)=1$

Здесь я воспользовался следующим фактом: Пусть $a$ и $b$ - натуральные числа. Если существуют целые числа $u$ и $v$ такие, что $au+bv=1$ тогда $\text{gcd}(a,b)=1.$ Доказывается от противного. Пусть все-таки $\text{gcd}(a,b)=d>1$ тогда не существует целых $u$ и $v$ таких, что $au+bv=1$ так как $\text{gcd}(a,b)=d>1$ и $d\notmid 1$

[ex-math]

Не делится, потому что $\theta^2$ не целое.

Итак, Вы каждому решению сравнения поставили в соответствие представление $m$ суммой квадратов. Осталось убедиться, что это соответствие биективно.

[Whitaker]

ex-math в сообщении #897026 писал(а):

Итак, Вы каждому решению сравнения поставили в соответствие представление $m$ суммой квадратов. Осталось убедиться, что это соответствие биективно.

Надо ведь еще обратное доказать ведь, т.е. каждому представлению $m=x^2+y^2,$ где $\text{gcd}(x,y)=1, x>0, y>0$ надо сопоставить сравнение $z^2+1\equiv 0 \pmod{m}$. Верно?

P.S. Хотя у меня есть предположение, что $\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]

Действительно, биективность проще доказать, рассматривая обратное отображение, когда представлению суммой квадратов сопоставляется решение сравнения.

-- 18.08.2014, 22:29 --

Как выразить $z$ через $x$ и $y$?

[Whitaker]

ex-math
Вот подумал и есть такая идея: Пусть $m=x^2+y^2,$ где $x>0, y>0, \text{gcd}(x,y)=1$.
Понятно, что $\text{gcd}(x,m)=1$ тогда существует единственно $s$ такое, что $xs\equiv y \pmod{m}$.
Но $x^2+y^2\equiv 0 \pmod{m},$ а отсюда вытекает, что $x^2\equiv -y^2\pmod{m}$.
Так как $y\equiv xs \pmod{m}$, то $y^2\equiv x^2s^2\pmod{m}$ и получаем, что $x^2s^2\equiv -x^2\pmod{m}$ и отсюда $x^2(s^2+1)\equiv 0 \pmod{m}$ т.к. $\text{gcd}(x,m)=1$, то имеем $s^2+1\equiv 0 \pmod{m}$
Вы согласны?
P.S. Также следует показать, что двум различным представлениям соответствуют различные (не сравнимые по модулю $m$) решения сравнения. Верно?

[ex-math]

Верно. И еще надо показать, что Ваши $t$ и $Q$ дадут в результате то самое $z$, из которого они получились.

[Whitaker]

ex-math в сообщении #897809 писал(а):

И еще надо показать, что Ваши $t$ и $Q$ дадут в результате то самое $z$, из которого они получились.

Извиняюсь, но тут я Вас что-то не понял. Зачем это нужно вообще? К какому случаю это относится?