Делимость

[neo66]

Доказать, что если $m$ нечетное или удвоенное нечетное, то существуют такие целые $x$ и $y$, что $x^2+y^2+1\equiv0\mod(m)$.

(Оффтоп)

Я знаю доказательство для простых $m$.

[Sonic86]

Если $x^2+y^2 \equiv 1 \pmod m$ для нечетного $m$, то либо $x^2+y^2 \equiv 1 \pmod{2m}$, либо $x^2+(y+m)^2 \equiv 1 \pmod{2m}$
С помощью китайской теоремы об остатках случай нечетного $m$ сводится к случаю $p^k$.
Для $k=1$ доказательство Вы знаете. Для $k>1$ построим решения по индукции. Пусть $x_k^2+y_k^2 \equiv -1 \pmod {p^k}$ для некоторого $k \geq 1$, тогда $x_{k+1}^2+y_{k+1}^2 \equiv -1 \pmod {p^{k+1}}$ $\Leftrightarrow$
$(x_k+p^kq_k)^2+(y_k+p^kr_k)^2 \equiv -1 \pmod {p^{k+1}}$ $\Leftrightarrow$
$(x_k^2+y_k^2+1)+2p^k(q_kx_k+r_ky_k) \equiv 0 \pmod {p^{k+1}}$$\Leftrightarrow$
$R_k+2(q_kx_k+r_ky_k) \equiv 0 \pmod{p}$
Уравнение имеет решение, поскольку одновременно не может быть $x_k,y_k \equiv 0 \pmod p$
Проще говоря, $x^2+y^2 +1 = 0$ разрешимо в $p$-адических числах... (есть в Боревиче, Шафаревиче, 1 глава)
Правильно?

[Руст]

Можно воспользоваться тем, что любое число $N\not =4^k(8k-1)$ представляется в виде суммы трех квадратов и обобщить задачу.

[neo66]

Sonic86 в сообщении #422050 писал(а):

С помощью китайской теоремы об остатках случай нечетного $m$ сводится к случаю $p^k$.

Пока не понимаю как сводится?

[Sonic86]

neo66 писал(а):

Sonic86 писал(а):

С помощью китайской теоремы об остатках случай нечетного $m$ сводится к случаю $p^k$.

Пока не понимаю как сводится?

Ну пусть $m = p_1^{a_1}...p_s^{a_s}$. Для модуля $p_j^{a_j}$ у нас есть решение $x_j \equiv u_j \pmod{p^j}, y_j \equiv v_j \pmod{p^j}$. Тогда по теореме мы можем построить такие $x, y$, что $(\forall j) x \equiv u_j \pmod{p^j}, y \equiv v_j \pmod{p^j}$ (могу формулу написать в "явном" виде). Рассмотрим выражение $x^2+y^2+1$ по модулю $m$. $x^2+y^2+1 \equiv 0 \pmod m \Leftrightarrow (\forall j ) x^2+y^2+1 \equiv 0 \pmod {p^j}$. Но $(\forall j) x \equiv u_j \pmod{p^j}, y \equiv v_j \pmod{p^j}$, значит $x^2+y^2+1 \equiv u_j^2+v_j^2+1 \equiv 0 \pmod {p^j}$, т.е. действительно $x^2+y^2+1 \equiv 0 \pmod m$.
Я думал, что это достаточно общая конструкция, т.е. $x^2+y^2+1$ можно заменить на любую $F(x_1,...,x_n)$, которая переводит классы вычетов по модулю $m$ в классы вычетов по модулю $m$

[neo66]

Да, кажется, все правильно.