Решение в челых числах

[Алекс77]

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

$x^2 + y^2 =1(mod\,c)$

Заранее спасибо за содействие.

[maxmatem]

А $c$-это какое-то фиксированное число?

[Алекс77]

В общем случае нет...
В смысле с - это константа, но о природе числа никакой информации нет. А х и у - это неизвестные.

[Sonic86]

Если $c=p_1^{a_1}...p_s^{a_s}$ - нечетно, то сравнение $x^2+y^2 \equiv 1 \pmod c$ разрешимо тогда и только тогда, когда разрешимы сравнения $x^2+y^2 \equiv 1 \pmod {p_j}$. В случае $p_j=4k+1$ есть $p-1$ решений, а в случае $p_j=4k-1$ есть $p+1$ решений.
Случай с четным $c$ чуть сложнее.
Общего вида решений я не знаю. Если найдете - напишите плиз.
См., напр., Айрленд, Роузен, Классическое введение в современную теорию чисел. Теория сравнений есть также в Бухштабе Теория чисел, хотя книжка древняя.

[Shtirlic]

А может мне кто объяснить, что такое $1(mod$ $c)$. знаю что операция mod - это остаток от деления, запись $(a$ $mod$ $c)$ знаю, а вот как в примере еще ни разу не видел.

[ewert]

$a=b(\!\!\!\mod c)\quad\Longleftrightarrow\quad a\!\mod c=b$

[Sonic86]

Shtirlic писал(а):

А может мне кто объяснить, что такое $1(mod$ $c)$. знаю что операция mod - это остаток от деления, запись $(a$ $mod$ $c)$ знаю, а вот как в примере еще ни разу не видел.

В TeX пишется \pmod{модуль}.
Обратитесь к книжкам, это стандартное обозначение, погуглите. Самая простая книжка - Бухштаб Теория чисел, есть и другие, получше.
$1 \pmod c$ - строго говоря не термин, так не пишут, но можно истолковать как класс вычетов $1$ по модулю $c$, т.е. $\{ ..., 1-c, 1, 1+c, 1+2c,...\}$.
Следует также отличать операцию нахождения остатка от деления $a \mod b$ и отношение $a \equiv b \pmod m$, последнее означает, что $a-b$ делится на $m$.

-- Пн июн 28, 2010 09:42:11 --

ewert писал(а):

$a=b(\!\!\!\mod c)\quad\Longleftrightarrow\quad a\!\mod c=b$

Строго говоря, неверно, напр., $8 \equiv 5 \pmod 3$, но $8 \mod 3 \neq 5$.

[ewert]

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

напр., $8 \equiv 5 \pmod 3$,

да, и впрямь, прошу прощения. Правильно так:

$a=b(\!\!\!\mod c)\quad\Longleftrightarrow\quad a\!\mod c=b\!\mod c$

[Shtirlic]

Sonic86
ewert
Спасибо, понял!

[Алекс77]

Sonic86 - спасибо за подсказку, нашел Бухштаб, перечитываю :)

На счет уравнения...
Если
$x^2-1=-y^2\pmod{c}$
и
$-y^2=z\pmod{c}$, то искомая задача становится равносильной
$(x-1)(x+1)+y^2=0\pmod{c}$ или $(x-1)(x+1)=z\pmod{c}$

Так как всегда существуют решения (1,0),(0,1),(-1,0),(0,-1), то было бы неплохо найти какое-нибудь общее правило, что-то типа линейной комбинации, как при решении обычных диофантовых уравнений первой степени :))) Но, естественно, это только пожелание...

Буду благодарен за дальнейшие подсказки.

[Sonic86]

Алекс77
Ну если у Вас $- y^2 \equiv z \pmod c$ и $z$ дано, то надо сразу найти все $y$ (их будет 0 или 1 или 2) и подставить в исходное сравнение и найти $x$. Если же $z$ - произвольная переменная, то условие $- y^2 \equiv z \pmod c$ для решения исходного сравнения само по себе ничего не даст.

Насчет общего решения надо подумать... Ну если в этой литературе нету, то вряд ли оно есть, но все-таки надо подумать...

(Оффтоп)

(Для точек окружности есть какой-то закон сложения, аналогичный сложению точек на эллиптической кривой, соответствующий параметризации $x = R \cos \alpha, y = R \sin \alpha$ и сложению аргумента $\alpha$ при сложении точек. Забыл в какой книжке, то ли Коблиц, то ли Прасолов Соловьев. Можно попытаться что-то аналогичное в $\mathbb{Z}_p$ проделать, но не знаю - не рублю в этом)

[Алекс77]

Еще раз спасибо за направления :)))

z - просто замена одной неизвестной переменной на другую :))))

В продолжение предыдущей идеи, частичным решением может являться также случай, когда одна из переменных равна нулю, т.е. задача принимает вид:
$x^2=1\pmod{c}$

На счет связи с окружностями... я тоже об этом думал, но видимо моих познаний маловато в плане применения к целым числам.

[RIP]

Для простого $c=p>2$ есть стандартный способ нахождения всех решений. Он вообще годится для любого поля. Пусть $x\ne0$. Положим $t=\frac{y+1}x$. Непосредственной проверкой убеждаемся, что $t^2+1=2t/x$, в частности, $t^2+1\ne0$, поэтому $x=\frac{2t}{t^2+1}$, $y=\frac{t^2-1}{t^2+1}$. Итак, любое решение с $x\ne0$ имеет вид $x=\frac{2t}{t^2+1}$, $y=\frac{t^2-1}{t^2+1}$, где $t^2+1\ne0$. Более того, при $t=0$ получается одно из "потерянных" решений $(0,-1)$. Второе получается "при $t=\infty$".

Это формально. "Геометрический" смысл всех этих махинаций можно глянуть, например, в книжке: В.В. Острик, М.А. Цфасман, "Алгебраическая геометрия и теория чисел: рациональные и эллиптические кривые", МЦНМО, 2001 (прямая ссылка).

[Алекс77]

RIP - !
Спасибо! Хоть и не полностью, но очень помогло!
А за ссылку - еще раз отдельное спасибо :))