Что-то похожее на уравнение Пелля

[BanmaN]

Здравствуйте всем!

Подскажите, пожалуйста, имеет ли решение уравнение $Ax^2 - By^2=C$ (в $Z$, конечно) в общем виде (ну или там, скажем, при каких-то ограничениях на A,B,C)? Или хотя бы для c =1? Если да, то опишите технику нахождения.

Спасибо.

[maxal]

Если вкратце, то примерная идея такая:
1) Домножить на $A$, сведя к уравнению Пелля-Ферма: $t^2 - AB y^2 = AC$, где $t=Ax$.
2) Найти частное решение уравнения Пелля-Ферма $t^2 - AB y^2 = AC$.
3) Найти общее решение уравнения Пелля $t^2 - AB y^2 = 1$.
4) Скомпоновать 2, 3 для получения общего решения уравнения Пелля-Ферма $t^2 - AB y^2 = AC$.
5) Выделить из общего решения те подрешения, в которых $t$ делится на $A$.

Подробно это описано в главе 6.3 в книге
Henri Cohen "Number Theory: Volume I: Tools and Diophantine Equations"

Есть ява-апплет, решающий такие уравнения:
Quadratic two integer variable equation solver

[BanmaN]

Спасибо большое, maxal.

Впредь буду соблюдать правила форума)

[Руст]

maxal в сообщении #277235 писал(а):

Если вкратце, то примерная идея такая:
1) Домножить на $A$, сведя к уравнению Пелля-Ферма: $t^2 - AB y^2 = AC$, где $t=Ax$.
2) Найти частное решение уравнения Пелля-Ферма $t^2 - AB y^2 = AC$.
3) Найти общее решение уравнения Пелля $t^2 - AB y^2 = 1$.
4) Скомпоновать 2, 3 для получения общего решения уравнения Пелля-Ферма $t^2 - AB y^2 = AC$.
5) Выделить из общего решения те подрешения, в которых $t$ делится на $A$.

Подробно это описано в главе 6.3 в книге
Henri Cohen "Number Theory: Volume I: Tools and Diophantine Equations"

Есть ява-апплет, решающий такие уравнения:
Quadratic two integer variable equation solver

Когда $Z[\sqrt{AB}]$ не является кольцом главных идеалов (а это почти всегда) пункт 4 не дает общего решения. Например, $AB=5, AC=4$. Частные решения $(t,y)=(2,0), (3,1)$ не выражаются умножением на единицу $\pm(9+4\sqrt 5)^k,k\in Z$ друг через друга.

[maxal]

Руст в сообщении #277460 писал(а):

Когда $Z[\sqrt{AB}]$ не является кольцом главных идеалов (а это почти всегда) пункт 4 не дает общего решения. Например, $AB=5, AC=4$. Частные решения $(t,y)=(2,0), (3,1)$ не выражаются умножением на единицу $\pm(9+4\sqrt 5)^k,k\in Z$.

Я же сказал, что это краткая идея. В каждом пункте там есть подводные камни. Детали нужно смотреть в книге.

-- Mon Jan 04, 2010 11:02:34 --

Кроме того, фундаментальная единица в твоем примере равна $\frac{-1+\sqrt{5}}{2}$ и все прекрасно выражается:

$$3-\sqrt{5} = (2-0\sqrt{5}) \left(\frac{-1+\sqrt{5}}{2}\right)^2.$$

[yk2ru]

Уравнение Пелля это уравнение $x^ 2-Dy^2=N$ с заданными натуральными D и N.
А если будет такое уравнение $Dx^ 2-y^2=N$, то следует домножать на D (как выше советовали) или есть ещё какой-то способ? Почему D после минуса, а не вначале, проще решать?

[ex-math]

Это то же уравнение, домножьте на минус один.

[yk2ru]

Понятно. Сначала где-то по ссылке прочитал про натуральность N. Оказывается, что натуральность необязательна, допускаются и целые числа.

[Andrey A]

BanmaN в сообщении #277221 писал(а):

Подскажите, пожалуйста, имеет ли решение уравнение $Ax^2 - By^2=C$... Или хотя бы для c =1?

Добавлю кое-что. Решения этого уравнения следуют из последней подходящей дроби полупериода разложения $AB$ после нужных сокращений, о чем писал maxal. $\sqrt{77}=\dfrac{8}{1},\dfrac{9}{1},\dfrac{35}{4},...$ откуда $35^2-77\cdot 4^2=-7,\ 11\cdot 4^2-7\cdot 5^2=1.$
Точнее сказать так: для каждого $M\neq n^2$ существует ровно одна пара множителей $AB=M$, для которой разрешимы уравнения $Ax^2-By^2=1$ или $Ax^2-By^2=2$. Если бы нашлась еще одна такая пара $A'B'=M$, было бы верно $\left ( A'x^2+B'y^2 \right )^2-M\left ( 2xy \right )^2=1$ или $\left ( \dfrac{A'x^2+B'y^2}{2} \right )^2-M\left ( xy \right )^2=1.$ И получили бы второе решение Пелля, чего не бывает. А наименьшие $C$ для фиксированных вз. простых $A,B$ следуют из разложения $\sqrt{\dfrac{A}{B}}.$

[yk2ru]

Есть термин число Пелля, которым обозначают "целое число, входящее в качестве знаменателя в бесконечную последовательность подходящих дробей для квадратного корня из 2. ... Числители той же последовательности приближений являются половинами сопутствующих чисел Пелля или числами Пелля — Люка — бесконечной последовательностью, начинающейся с 2, 6, 14, 34 и 82." (Из Вики).
То же самое верно для подходящих дробей для квадратных корней других чисел, не являющихся квадратами целых чисел. Числители и знаменатели этих дробей также являются последовательностями Люка. Для двойки соответствующие $(P, Q)$ равны $(6, 1)$, для тройки $(4, 1)$ , для пятерки $(18, 1)$ ... Q всегда равно единице. Числители подходящих дробей являются половинами соответствующих чисел последовательности Люка $V_n$, а знаменатели получатся, если числа $U_n$ домножить на $y_1$, первое ненулевое значение $y$ решения уравнения Пелля.
Первые значения решения уравнения $x^2 - 5y^2 = 1$ .

n x y
0 1 0
1 9 4
2 161 72
3 2889 1292
4 51841 23184

Последовательности Люка с ${P, Q}$ равными ${18, 1}$ .

n U V
0 0 2
1 1 18
2 18 322
3 323 5778
4 5796 103682

То есть, чтобы найти следующие значения решений уравнения Пелля из первого ненулевого решения, необязательно помнить матрицу из четырех чисел, а достаточно знать лишь число $P = 2x_1$.
Второе ненулевое решение находится по формулам (вычисления значений с удвоенным n $(2{x_n}^2-1, 2x_n{y_n})$

$$x_2 = 2x_1^2 - 1$$

$$y_2 = 2x_1y_1$$

или $(Px_1-1, Py_1)$ . А далее соответстенно использовать аналогичные рекуррентные формулы с $(P,Q)$ .

$$x_{n+1} = 18x_n - x_{n-1}$$

$$y_{n+1} = 18y_n - y_{n-1}$$

В Википедии почему-то этого нет, хотя так вроде бы проще находить решения из предыдущих, нужно помнить лишь одно число равное $2x_1$ вместо трех-четырех.

[yk2ru]

Как ещё можно получить минимальное нетривиальное решение для уравнения Пелля

$$x^2 - Dy^2 = 1$$

с $D=61$, которое имеет решение $(x=1766319049,y=13795392780)$.
Замечено, что для уравнения Пелля с простым числом $D = 4n + 1$ одно из значений имеет вид $x = 2Dk^2 - 1$ для минимального нетривиального решения. Подставив такое $x$ в уравнение Пелля получим, что $Dk^2 + 1$ должно быть квадратом, т.е. $k$ должно быть решением уравнения

$$x^2 - Dy^2 = -1$$

Значение $y$ минимального решения даёт значение для $k$, через которое можно получить значение $x = 2Dk^2 - 1$ начального уравнения Пелля. В англинской википедии можно прочесть следующее

Цитата:

For the following transformations,[11] if fundamental {u,v} are both odd, then it leads to fundamental {x,y}.
1. If u^2 − dv^2 = −4, and {x,y} = {(u^2 + 3)u/2, (u^2 + 1)v/2}, then x^2 − dy^2 = −1.

Получив минимальное решение уравнения $x^2 - Dy^2 = -4$, и если оба значения нечетные, то из него уже можно посчитать значение $x$ уравнения $x^2 - Dy^2 = 1$, затем же получить $y$ , подставив $x$ в начальное уравнение. Так как минимальное решение уравнения $x^2 - Dy^2 = -4$ равно $(x=39,y=5)$, из него уже вычислить значение $k=3805$, и далее получить решение $(x=1766319049,y=13795392780)$ для начального уравнения Пелля.
Также возможно сразу посчитать по следующим формулам из википедии

Цитата:

3. If u^2 − dv^2 = −4, and {x,y} = {(u^4 + 4u^2 + 1)(u^2 + 2)/2, (u^2 + 3)(u^2 + 1)uv/2}, then x^2 − dy^2 = 1.

[yk2ru]

Закралась ошибка: Решение для начального уравнения Пелля $(x=1766319049,y= 226153980)$ . Было же скопировано вместо $y$ число $Dy$ .

[Andrey A]

yk2ru
Всё это немножко не в тему. Вопрос был

BanmaN в сообщении #277221 писал(а):

... имеет ли решение уравнение $Ax^2 - By^2=C$

(на всякий случай)

Общее решение уравнения $x^2-my^2=1$ выражается последовательностью $\dfrac{1}{0};\dfrac{x_1}{y_1};... ;\dfrac{x_{n+1}=2x_1x_n-x_{n-1}}{y_{n+1}=2x_1y_n-y_{n-1}};...$ факт общеизвестный.

[Andrey A]

BanmaN в сообщении #277221 писал(а):

$Ax^2 - By^2=C$

Можно еще тут посмотреть https://dxdy.ru/post1405749.html#p1405749