Решить сравнение: x^2+y^2=1 (mod p^2)

[RgWhite]

помогите решить такую задачку
решить сравнение $x^2+y^2 \equiv 1(\mod p^2)$, p-простое

[Sonic86]

Вам что надо?
Все решения записать? Или для конкретного р найти? Или оценить?
Пробовали искать решения для небольших р перебором?

[RgWhite]

оказывается надо найти число решений))
просто задача не моя, попросили написать поэтому такая неувязочка получилась

[VAL]

RgWhite писал(а):

оказывается надо найти число решений))

По-видимому, $p(p-1)$ при $p \equiv 1 (mod 4)$, $p(p+1)$ при $p \equiv 3 (mod 4)$, ну и $8$ при $p=2$.

[Sonic86]

Для каждого данного р есть алгоритм, позволяющий найти все решения. Я попробовал решить, у меня получилось так:
1. Рассмотрите случай $p=2$ отдельно.
2. Выразите каждое решение сравнения $x^2+y^2 \equiv 1 (p^2)$ через решение сравнения $x^2+y^2 \equiv 1 (p)$ (функция).
3. Расмотрите случай $p=4k+1$.
4. Расмотрите случай $p=4k+3$. (этот случай у меня до конца разобрать не получилось )

VAL! Откуда берется число решений для $p=4k+3$?

[maxal]

Для нечетного $p$ задача сводится к вычислению суммы символов Лежандра:

$$\sum_{x=0}^{p^2-1} \left(\frac{1-x^2}{p^2}\right) = \sum_{x=0}^{p^2-1} \left(\frac{1-x^2}p\right) = p \sum_{x=0}^{p-1} \left(\frac{1-x^2}{p}\right) =$$

$$= p \sum_{x=0}^{p-1} ((1-x^2)^{(p-1)/2} \bmod p) = p (p + (-1)^{(p-1)/2}(p-1))$$

[RgWhite]

чет я ничего не понял) р же простое число, 4k+1 и 4k+3 не подходят..
ответ может быть $p$ или $p^2$, не уверен

[Sonic86]

В книжке Айрленда, Роузена "Классическое введение в современную теорию чисел" в главе 8 есть метод вычисления числа решений уравнений $x^2 + y^2 \equiv 1 (p)$ и $x^3 + y^3 \equiv 1 (p)$ с помощью сумм Гаусса и Якоби на основе характеров - вполне интересная теория. Вполне обобщается и на уравнения $x^2 + y^2 \equiv a (p)$ и $x^3 + y^3 \equiv a (p)$.

Хотя следуя способу доказательства $J(\chi; \chi^{-1}) = - \chi (-1)$ можно построить простое доказательство для этих уравнений (это на тот случай если препод относится к классу утверждающих вещи типа: "Мы это не проходили, значит использовать нельзя")
$N(x^2+y^2 \equiv 1 (p)) = N(x^2 \equiv (1-y)(1+y) (p), 1+y=z) = $
$2+ 2N(z(2-z) - res(p), z \neq 0) = 2 + 2N(z^{-1}(2-z)-res(p), z \neq 0)$.
Запись $t - rez(p)$ означает "t - квадратичный вычет по модулю р". Теперь сделаем замену $u=2z^{-1}-1$ -биекция . $z \neq 0 \Leftrightarrow u \neq 0$. Тогда
$2 + 2N(z^{-1}(2-z)-res(p), z \neq 0) = 2 + 2N(u-res(p), u \neq -1) = 2 + 2N(u-res(p)) - N((-1) - res (p))$.
Так как $N(u-res(p)) = \frac{p-1}{2}, p \neq 2$ - (число квадратичных вычетов равно половине числа всех обратимых вычетов), а $N((-1) - res (p)) = 2 \Leftrightarrow p=4k+1$ и $N((-1) - res (p)) = 0 \Leftrightarrow p=4k+3$, то получим искомую формулу для числа решений (можно по рассуждениям находить и сами решения):
$p=4k+1 \Rightarrow N(x^2+y^2 \equiv 1 (p)) = p-1$
$p=4k+3 \Rightarrow N(x^2+y^2 \equiv 1 (p)) = p+1$