Решить сравнение

[alex]

Как найти все целочисленные решения для
$x^2 \equiv y^2\ (\textrm{\mod}\ p)$
где p - простое число?

Подставив некоторый х, можно получить все решения по Диофанту, но как перебрать все х?

[venco]

Для любого $x$
$x^2=(p-x)^2 \mod p$
Причём это все возможные решения, кроме тривиальных.

[alex]

venco в сообщении #796381 писал(а):

Для любого $x$
$x^2=(p-x)^2 \mod p$
Причём это все возможные решения, кроме тривиальных.

Ну а чем докажете своё решение?

[venco]

А попробуйте сами - там не сложно.

[alex]

Раскладывали в Диоф-во уравнение? Или выходить из того, что р делит разницу квадратов х и у.. Честно, не понимаю как вы получили этот результат.

[venco]

Формулу разности квадратов, надеюсь, знаете?

[provincialka]

venco, ваше утверждение легко проверить в одну сторону, т.е. что $y=p-x$ будет решением. Но есть же и другие! И почему их вы считаете тривиальными? Не хуже и не лучше этого.

[Батороев]

(Оффтоп)

Непрофессиональное объяснение (потому и оффтоп)

alex в сообщении #796365 писал(а):

Как найти все целочисленные решения для
$x^2 \equiv y^2\ (\textrm{\mod}\ p)$
где p - простое число?

Остатки по основанию $p$ квадратов чисел, взаимно простых с $p$, представляют те числа, которые в степени $\frac {p-1}{2}$ будут иметь остаток $+1\pmod p$.
Т.к. таких чисел половина (остальные имеют остаток $-1\pmod p$), то остатки квадратов чисел разделены на пары, не совпадающие с другими. Т.е. других решений, кроме $x^2\equiv (p-x)^2\pmod p$, не существует.

[alex]

venco в сообщении #796481 писал(а):

Формулу разности квадратов, надеюсь, знаете?

Если разложить, то р делит разность или сумму х и у. Выходит у = р-х, у = -(р-х).

[provincialka]

А почему нельзя взять, скажем, $x-y= kp$ для некоторого целого $k$?

[Deggial]

alex в сообщении #796538 писал(а):

х и у. Выходит у = р-х, у = -(р-х).

alex, замечание за неоформление формул $\TeX$ом.

[venco]

provincialka в сообщении #796550 писал(а):

А почему нельзя взять, скажем, $x-y= kp$ для некоторого целого $k$?

Дык, по модулю же. Это одно и то же решение.

[provincialka]

Хм.. Это уравнение по модулю. А решение - нет. Например, возьмем $x = 6, p = 5$, тогда решениями будут $y= ...,-9, -4,1,6,...$ и $y=...-6,-1, 4, 9,...$. Какие из решений считать "главными", а какие - "тривиальными"? Здесь $p-x=-1$.

[venco]

provincialka в сообщении #796749 писал(а):

Хм.. Это уравнение по модулю. А решение - нет. Например, возьмем $x = 6, p = 5$, тогда решениями будут $y= ...,-9, -4,1,6,...$ и $y=...-6,-1, 4, 9,...$. Какие из решений считать "главными", а какие - "тривиальными"? Здесь $p-x=-1$.

Любое из одной группы (они эквивалентны), и любое из другой.
Предпочтительно взять значение из классического диапазона $0\le x<p$, в вашем примере это 1 и 4.

[provincialka]

Именно.