2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Решение в челых числах
Сообщение27.06.2010, 14:48 
Аватара пользователя
А $c$-это какое-то фиксированное число?

 
 
 
 Re: Решение в челых числах
Сообщение27.06.2010, 16:33 
Аватара пользователя
В общем случае нет...
В смысле с - это константа, но о природе числа никакой информации нет. А х и у - это неизвестные.

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 07:00 
Если $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$ чуть сложнее.
Общего вида решений я не знаю. Если найдете - напишите плиз.
См., напр., Айрленд, Роузен, Классическое введение в современную теорию чисел. Теория сравнений есть также в Бухштабе Теория чисел, хотя книжка древняя.

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 08:04 
А может мне кто объяснить, что такое $1(mod$ $c)$. знаю что операция mod - это остаток от деления, запись $(a$ $mod$ $c)$ знаю, а вот как в примере еще ни разу не видел.

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 08:38 
$a=b(\!\!\!\mod c)\quad\Longleftrightarrow\quad a\!\mod c=b$

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 08:40 
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$.

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 08:46 
Sonic86 в сообщении #335810 писал(а):
напр., $8 \equiv 5 \pmod 3$,

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

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

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 09:20 
Sonic86
ewert
Спасибо, понял!

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 13:46 
Аватара пользователя
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), то было бы неплохо найти какое-нибудь общее правило, что-то типа линейной комбинации, как при решении обычных диофантовых уравнений первой степени :))) Но, естественно, это только пожелание...

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

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 14:10 
Алекс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$ проделать, но не знаю - не рублю в этом)

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 14:36 
Аватара пользователя
Еще раз спасибо за направления :)))

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

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

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

 
 
 
 Re: Решение в челых числах
Сообщение28.06.2010, 22:29 
Аватара пользователя
Для простого $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 (прямая ссылка).

 
 
 
 Re: Решение в челых числах
Сообщение29.06.2010, 10:28 
Аватара пользователя
RIP - :appl: !
Спасибо! Хоть и не полностью, но очень помогло! :D
А за ссылку - еще раз отдельное спасибо :))

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group