решить уравнение в целых числах

[dmd]

И, следовательно,

$x_{1,2}^2\equiv 1\pmod d$

[dmd]

dmd в сообщении #508837 писал(а):

И, следовательно,

$x_{1,2}^2\equiv 1\pmod d$

, самому смешно, вывел тривиальность.


Еще одно соотношение

$x_1x_2+1=d(x_{1,2}-y_{1,2})$

[Sonic86]

(Оффтоп)

у меня такое ощущение, что если Вы клоните к алгоритму факторизации $d$, то не все так просто...

[dmd]

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

у меня такое ощущение, что если Вы клоните к алгоритму факторизации $d$, то не все так просто...

Понимаю, что не просто. Главное - интересно.

Например, в этой задаче наблюдаются своеобразные "спуск" и "подъем" по подобным уравнениям и их нетривиальным решениям. При спуске новый нижний $x$ это бывшие верхние $x\% y$, новый $d$ это верхний $y$. При этом не важно от $x_1$ или $x_2$ начинается спуск, заканчивается он внизу одинаково.

[dmd]

dmd в сообщении #508995 писал(а):

Еще одно соотношение

$x_1x_2+1=d(x_{1,2}-y_{1,2})$

Если обозначить

$x_{1,2}-y_{1,2}=s$

то

$x_1x_2+1=ds$

$y_1y_2+1=s^2$

[dmd]

Удивительно, но заменой $Y=d(y+2)+1$ исходное уравнение преобразуется в эллиптическое:

$Z^2=Y^3-3d^2Y-2d^3$

Примеры:

$d=527,y_{1,2}=\{45,264\},Y_{1,2}=\{24770,140183\},Z_{1,2}=\{3895738,52484830\}$

$d=893,y_{1,2}=\{40, 555\},Y_{1,2}=\{37507, 497402\},Z_{1,2}=\{7257600, 350799680\}$

[dmd]

dmd в сообщении #511186 писал(а):

$Z^2=Y^3-3d^2Y-2d^3$

Две целых точки $\{Y,Z\}$ на этой кривой очевидны: $\{-d,0\}$ и $\{2d,0\}$.

Третья точка $\{2d+64,8(3d+64)\}$.

[dmd]

Понял свою ошибку, правая часть раскладывается

$Y^3-3d^2Y-2d^3=(Y-2d)(Y+d)^2$

[dmd]

В этой задаче действует Малая теорема Ферма. Только для нетривиальных иксов справедливо соотношение:

$x_{1,2}^{d-1}\equiv 1\pmod d$

Т.е. $d$ псевдопростое по основанию $x_{1,2}$

[dmd]

Впрочем, это тоже тривиальность. Для любого четного $n$ выполняется $x_{1,2}^n\equiv 1\pmod d$.

[dmd]

Параметризация делителями.


Пусть $x^2-dy=1$ - уравнение в рациональных числах, где $d$ - заданное натуральное. И пусть даны произвольные целые $a,b$. Выделим из числа $4abd$ делители $p$ и $q$: $4abd=pq$. Причём $p,q$ не обязательно целые. Тогда справедлива параметризация

$x= \frac{ap+bq}{ap-bq},\qquad y=\frac{16a^2b^2}{(ap-bq)^2}$

[Andrey A]

dmd в сообщении #1032660 писал(а):

Пусть $x^2-dy=1$

Перепишем: $d=\frac{x^2-1}{y}$ или $\sqrt{d}\approx \frac{x}{\sqrt{y}}$.
Подходящие дроби разложения $\sqrt{d}$ дают приближения в рациональных числах, и решение ур. Пелля. Если бы существовал алгоритм аппроксимации дробями вида $\frac{p}{\sqrt{q}}$, это был бы ответ на Ваш вопрос, который лучше сформулировать так: найти наименьшее натуральное $x\neq 1$ такое, что $x^2\equiv 1\mod d$. Решение $x=d-1$ верно не только для простого $d$. Так же и для степеней нечетных простых и для удвоенных степеней нечетных простых. Строго говоря, задача не эквивалентна факторизации. Из ее решения получаем только одну пару делителей $d$, среди которых может оказаться и единица. Если же $d$ имеет много пар вз. простых делителей, то нахождение всех квадратов $\equiv1$ с последующей сортировкой может оказаться не самым экономным способом. Даже если делители известны.

[bot]

Переформулировка: Найти все $x$, для которых $x^2-1\equiv 0\pmod {d}$
Эта стандартная задача изложена везде - в Бухштабе, скажем. Начинается она с отыскания решений по модулям простых делителей $d$. Это самая сложная часть - перебор потому что. Поскольку степень сравнения два, то и перебора нет - решений не может быть больше двух, а два есть - это 1 и -1. Далее следует их поднять по показателю степени, с которым простое входит в каноническое разложение $d$ и, наконец, собрать по китайской теореме об остатках.

-- Ср июл 08, 2015 14:02:06 --

PS. Так как $(x^2-1)'=2x\equiv 0\pmod {2}$, то подъём по модулю 2 будет произвольным, а по остальным $p$ однозначным, то количество несравнимых решений (по модулю $d$) будет равно показателю степени, с которым двойка входит в каноническое разложение $d.$

ЗЫ.

bot в сообщении #1034592 писал(а):

будет равно показателю степени, с которым двойка входит в каноническое разложение

Ерунду написал - поторопился потому что. Для $d=2^{k_0}p_1^k^1\ldots p_s^{k_s}$ количество решений будет $m2^s, \ \ 1\leqslant m\leqslant 2^{k_0-1}$ - по нечётному простому решений ведь два и каждое поднимается однозначно, а по модулю 2 некоторые ветки могут раздваиваться, а другие отваливаться.

[bot]

А нет ли в OEIS числа решений сравнения $x^2\equiv 1\pmod{2^k}$?
Это надо взять бинарное представление икса, возвести в квадрат и посмотреть, чтоб ненужных степеней не не было ... хм, не так-то просто, кажется.

[Andrey A]

По поводу количества решений у Бухштаба есть теорема на стр. 169, но нужно ли знать все чтобы найти наименьшее?

(Оффтоп)

— Г-голубчики, — сказал Фёдор Симеонович озадаченно, разобравшись в почерках. — Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал, что она н-не имеет р-решения.
— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетиниваясь. — Мы хотим знать, как её решать.
— К-как-то ты странно рассуждаешь, К-кристо… К-как же искать решение, к-когда его нет? Б-бессмыслица какая-то…
— Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица — искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен...