Интересное свойство уравнения Пелля

[Andrey A]

P.S. P.S.
Что ж. Тогда можно взять $v=0$ и получить $X=\dfrac{(2u+1)^2+1^2+(2u-1)^2+1^2}{4}=2u^2+1.$ Именно это и происходит, поскольку если $x^2 - dy^2 = -1$, то $(2x^2+1)^2-d(2xy)^2=1$
Но я не считаю такой опыт бесполезным )

[Andrey A]

P.S. P.S. P.S.

Andrey A в сообщении #1594579 писал(а):

Выше было показано, что каждый член указанной последовательности (OEIS A050795) может быть получен из четверки нечетных $ab-cd=-2:$

$$X=\dfrac{a^2+b^2+c^2+d^2}{4}.$$

Это верно. Но

Andrey A в сообщении #1594454 писал(а):

... имеем необходимое и достаточное условие нечетности периода разложения $M:$

$$\left ( \dfrac{p-c}{2} \right )^2+\left ( \dfrac{p-d}{2} \right )^2=\square.$$

неверно. Оно равносильно требованию $X=2u^2+1$, что является достаточным условием "нечетности" $X$, но необходимым не является. Sorry. Тестирование отменяется.

[mathematician123]

Про уравнение $x^2 - Ay^2 = -1$ можно ещё рассмотреть задачу определения разрешимости в зависимости от разложения $A$ на простые. Для простого $A$ разрешимость определяется остатком от деления на 4.

В случае $A = pq$ для простых $p, q$, которые не имеют вид $4k + 3$, разрешимо ровно одно из трёх уравнений

$$x^2 - Ay^2 = -1 \quad px^2 - qy^2 = 1 \quad qx^2 - py^2 = 1$$

В случае $p = 2$ первое уравнение разрешимо, если $q \equiv 5 \pmod{8}$. Если $q \equiv 1 \pmod{8}$, первое уравнение иногда разрешимо, а иногда нет. Есть ли простой способ это определить? Не знаю.

В случае $p \equiv q \equiv 1 \pmod{4}$ первое уравнение разрешимо, если $(\frac{p}{q}) = -1$. Применив квадратичный закон взаимности, можно усилить этот результат: если оба сравнения $x^4 \equiv q \pmod{p}$ и $x^4 \equiv p \pmod{q}$ неразрешимы, то уравнение $x^2 - pqy^2 = -1$ разрешимо. В одной статье я нашёл утверждение о том, что в случае, когда из этих двух сравнений разрешимо ровно одно, уравнение $x^2 - pqy^2 = -1$ не имеет решений. Если оба сравнения разрешимы, то решения иногда есть, а иногда нет. От чего это зависит? Опять же, вопрос трудный.

[Andrey A]

mathematician123 в сообщении #1594927 писал(а):

От чего это зависит? Опять же, вопрос трудный.

То-то и оно. Исходя из свойств $A$, трудно что-либо заключить с уверенностью, кроме того, что оно зеленое. Нечетный период разложения для простого $A$ — тоже, на сколько понимаю, гипотеза. Потому и переметнулся на свойства $x$, и, вроде бы, не напрасно. Тем более, что множество иксов для зеленого $A$ очень красиво следует из четверки нечетных $ab-cd=-2.$ Давайте всё же говорить об "иксах зеленого Пелля" $(X)$, как о членах последовательности OEIS A050795 и о разложении $A=\dfrac{X^2-1}{D^2},$ где $D$ — основание наибольшего квадратного делителя числителя. Предлагаю доказать или опровергнуть следующее утверждение:

Период разложения $\sqrt{A}$ в непрерывную дробь имеет нечетное количество знаков тогда и только тогда, когда из двух последовательных $\dfrac{X-1}{2},\dfrac{X+1}{2}$ одно является целым квадратом.

Отсюда, кстати, следовала бы и нечетность разложения для простого $A$, но уже для удвоенного простого — не обязательно.

[mathematician123]

Andrey A в сообщении #1594944 писал(а):

разложении $A=\dfrac{X^2-1}{D^2},$ где $D$ — основание наибольшего квадратного делителя числителя. Предлагаю доказать или опровергнуть следующее утверждение:
Период разложения $\sqrt{A}$ в непрерывную дробь имеет нечетное количество знаков тогда и только тогда, когда из двух последовательных $\dfrac{X-1}{2},\dfrac{X+1}{2}$ одно является целым квадратом.

Для простого $A \equiv 1 \pmod{4}$ решение несложное. Чётность числа $D$ следует из рассмотрения по модулю 4. Тогда можно написать

$$A\left(\frac{D}{2}\right)^2 = \frac{X+1}{2} \cdot \frac{X-1}{2}$$

Числа справа отличаются на 1 и потому взаимнопросты. Значит, они имеют вид $v^2$ и $Au^2$. Откуда $v^2 - Au^2 = \pm 1$. Если справа знак плюс, то получили меньшее представление $A = \frac{v^2-1}{u^2}$. А если взять $D, X$ минимально возможными, то обязательно получим $v^2 - Au^2 = -1$.
Если применить эти рассуждения к случаю $A = pq$, то получим одно решение одного из уравнений

mathematician123 в сообщении #1594927 писал(а):

$$x^2 - Ay^2 = -1 \quad px^2 - qy^2 = 1 \quad qx^2 - py^2 = 1$$

Но какого именно, определить сложно.

[Andrey A]

mathematician123 в сообщении #1594995 писал(а):

Для простого $A \equiv 1 \pmod{4}$ решение несложное.

Да. Получается, что $A$ нечетного периода — своего рода квазипростые относительного данного алгоритма. Еще имеет значение следующее: если $v^2 - Au^2 = -1,$ то $v^2=Au^2-1$ и $Au^2=v^2+1,$ откуда $v^2 + Au^2 = 2Au^2-1=2v^2+1,$ а это иксы некоторых старших уравнений, для которых $(X-1)/2$ — квадрат. Их половина от общего, другая половина следует таким же образом из $v^2 - Au^2 = 1,$ для них $(X+1)/2$ — квадрат. Отсюда и утверждение справедливое в случае разрешимости уравнения $v^2 - Au^2 = -1.$ Но всё это голословно, и нужно доказать еще, что в случае четных периодов этого не происходит. Тут полезно выписать для наглядности последовательности решений для маленьких $A$ в виде дробей по типу подходящих; они ведь тоже подлежат рекурсии, а для $A=2,5$ подходящие и есть. Но почему-то этого никто не делает.

Ладно. В общем виде $X$ выражается формой $\dfrac{a^2+b^2+c^2+d^2}{4},$ тогда пара $\dfrac{X-1}{2},\dfrac{X+1}{2}=\dfrac{a^2+b^2+c^2+d^2-4}{8},\dfrac{a^2+b^2+c^2+d^2+4}{8}.$ И, помня, что $ab-cd=-2$, получаем $\dfrac{X-1}{2},\dfrac{X+1}{2}=\dfrac{(a+b)^2+(c-d)^2}{8},\dfrac{(a-b)^2+(c+d)^2}{8}$ — пара последовательных чисел, одно из которых целый квадрат. Отсюда можно выразить $X$ в явном виде из пифагоровой тройки. Но на сегодня хватит.

[Andrey A]

Andrey A в сообщении #1595030 писал(а):

... нужно доказать еще, что в случае четных периодов этого не происходит.

Доказать будет сложно, поскольку оно неверно.

Andrey A в сообщении #1594944 писал(а):

Период разложения $\sqrt{A}$ в непрерывную дробь имеет нечетное количество знаков тогда и только тогда, когда из двух последовательных $\dfrac{X-1}{2},\dfrac{X+1}{2}$ одно является целым квадратом.

Требование необходимое, но не достаточное. Если кто заморочился на сей счет, зря время всё же не потратил. Надеюсь ) Хорошее решение тут есть, скоро выложу.

[Andrey A]

Andrey A в сообщении #1594579 писал(а):

Выше было показано, что каждый член указанной последовательности может быть получен из четверки нечетных $ab-cd=-2:\ \ X=\dfrac{a^2+b^2+c^2+d^2}{4}.$

Имелось в виду зеленый $X$ вообще. И, кстати, поскольку все четыре переменные симметричны, минус перед двойкой не обязателен. Пронумеруем:

$$X=\dfrac{a^2+b^2+c^2+d^2}{4}\ \ (1)$$

Множество зеленых $X$ нечетного периода естественно должно входить в $(1),$ оно также выражается явно, но соответствующей последовательности $3,9,17,19,33,51,73,99,129,161,163,...$ в OEIS нет. Формула такая:

$$X=\dfrac{\left ( u+\sqrt{u^2+1} \right )^{2n}+\left ( u-\sqrt{u^2+1} \right )^{2n}}{2}\ (2)$$

Вообще, если для некоторого $A$ разрешимо уравнение $x^2-Ay^2=\mp 1,$ то серия решений выражается формулами

$$x_n=\dfrac{\left ( u+\sqrt{u^2+1} \right )^{n}+\left ( u-\sqrt{u^2+1} \right )^{n}}{2}$$

$$y_n=\dfrac{\left ( u+\sqrt{u^2+1} \right )^{n}-\left ( u-\sqrt{u^2+1} \right )^{n}}{2\sqrt{A}},$$

где $u$ есть икс первого решения, т.е. $u^2-Ay_1^2=-1,$ и вся последовательность $x_n$ зависит только от него. Для $A=29$, к примеру, находим разложением $x_1=70,$ тогда в уравнении $x^2-29y^2=-1$ $x_{2n+1}=\dfrac{\left ( 70+\sqrt{4901} \right )^{2n+1}+\left (70-\sqrt{4901} \right )^{2n+1}}{2}.$ Но Вольфрам, похоже, этого не знает. Странно, ведь рекурсия в сериях решений Пелля определена только значением $x_1. $ Надо бы проверить, кстати, для четных периодов должна быть та же закономерность, только под радикалами $-1$ вместо $+1.$ Короче с иксами Пелля разобрались (если нигде не ошибся). Интересна сама структура первого решения, тут надо подумать.

[Andrey A]

Andrey A в сообщении #1595398 писал(а):

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

Так и есть. Общая закономерность: если $n$ — длина периода разложения $\sqrt{A}$ и $x_1-Ay_1=\pm 1$ — первое решение, то серия решений выражается формулами

$$x_k=\dfrac{\alpha^k+\beta^k}{2}, y_k=\dfrac{\alpha^k-\beta^k}{2\sqrt{A}}$$

где

$$\alpha=x_1+\sqrt{x_1^2-(-1)^n}, \beta=x_1-\sqrt{x_1^2-(-1)^n}.$$

Andrey A в сообщении #1595398 писал(а):

Интересна сама структура первого решения.

Имелось в виду первое решение уравнения $x^2-Ay^2=-1.$ Перепишем его так:

$$x^2+1=Ay^2 \ \ (3)$$

Вопрос нечетности периода разложения $\sqrt{A}$ равносилен вопросу разрешимости этого уравнения для фиксированного $A.$ Уже говорилось, что $A$ сумма двух вз. простых ненулевых квадратов (зеленое число), а $y$ — нечетное зеленое число, поскольку левая часть $(3)$ не делится на $4.$ Значит $A^2$ — старший элемент примитивной Пифагоровой тройки. Сделаем подстановки: $A=a^2+b^2, y=p^2+q^2,$ где пары $(a,b);(p,q)$ вз. просты, пара $(p,q)$ разной четности. Тогда:
$Ay^2=(a^2+b^2)(p^2+q^2)^2=(a^2+b^2)\left ( (2pq)^2+(p^2-q^2)^2 \right )=$ $\left ( 2apq+b(p^2-q^2) \right )^2+\left ( a(p^2-q^2)-2bpq \right )^2.$ Если основание последнего квадрата равно $\pm 1$, получаем решение $(3).$ Отображений в виде суммы двух квадратов тут может быть несколько, но нас интересует равенство с единицей, а оно выражается именно в таком виде, и вопрос четных/нечетных периодов сводится к разрешимости формы

$$ap^2-aq^2-2bpq=\pm 1\ \ (4)$$

Разложением $\dfrac{p^2-q^2}{2pq}$ в непрерывную дробь получаем бесконечную серию нужных пар $(a_i,b_i)$, поэтому множество значений $A$ нечетного периода можно считать функцией от множества Пифагоровых троек. Однако, взяв аргументом пару $a=5,b=3,$ получаем уравнение $5p^2-5q^2-6pq=\pm 1$ неразрешимое в целых числах. Если же взять неизвестным параметр $p$, имеем уравнение $ap^2-2bqp-(aq^2 \pm 1)=0$ и $p=\dfrac{bq \pm \sqrt{(bq)^2+(aq)^2 \pm a}}{a}.$ Уже легче:

$$(ap-bq)^2-Aq^2=\pm a\ \ (5)$$

Параметры $a,b$ симметричны, один из них $<\sqrt{A/2}$ и один из двух должен входить в последовательность остатков вида $P^2-AQ^2$, где $P/Q$ — подходящие дроби разложения $\sqrt{A}.$ Тут ключ и к другому уравнению:

$$A=z^2+t^2\ \ (6),$$

которое обсуждается в параллельной теме. Ну, а получив выражение $P^2-Aq^2=\pm a$, находим $b=\sqrt{A-a^2}$ и $p=\dfrac{P \pm bq}{a}$ (подобрав нужный знак). Отсюда $p^2+q^2=y$ и $\sqrt{Ay^2-1}=x.$
Возьмем пример.
$\sqrt{181}=13,2,4,1,8,6,1,1,1,\underline{1,2,2,1},...=\dfrac{13}{1},\dfrac{27}{2},\dfrac{121}{9},\dfrac{148}{11},\dfrac{1305}{97},\dfrac{7978}{593},$ $\dfrac{9283}{690},\dfrac{17261}{1283},\dfrac{26544}{1973},\dfrac{43805}{3256},...$

Из последней дроби получаем $43805^2-181 \cdot 3256^2=9=a.\ \ \sqrt{181-9^2}=$ $10=b.\ \ \dfrac{43805+10 \cdot 3256}{9}=8485=p.\ \ 8485^2+3256^2=82596761=y$ и $\sqrt{181 \cdot 82596761^2-1}=1111225770=x.$ Таким образом из дроби в конце первого полупериода получены решения уравнений $(3),(6).$ Осталось непонятно почему взята именно эта дробь, проверять все остатки подряд что-то скучновато. Тут гипотеза, постараюсь кратко.

Раскладывая квадратный радикал, нельзя не заметить, что с некоторого момента знаки повторяются в обратном направлении. Центр симметрии — подпоследовательность вида $u,v,v,u$ (нечетный период) или $u,v,u$ (четный период). Подходящая дробь, соответствующая первому знаку такого мини-палиндрома как раз и есть интересующая нас (интересная) дробь. Но в длинных дробях подобные мини-палиндромы могут возникать и ранее (локальная симметрия). Чтобы не перепутать: "интересная" дробь находится также в центре симметрии остатков вида $P^2-AQ^2.$ Соотв. ей остаток в четных периодах возвращает делитель или удвоенный делитель $A,$ в нечетных периодах — параметр $a$ уравнения $(5).$ Яснее выразиться не знаю как.

Что ж. В итоге всё равно нужно добраться в разложении до центра симметрии, иначе прояснить вопрос четности/нечетности периода не удается. Не знаю. Мало ли вдруг какими-то иными способами получится сделать вывод о разрешимости формы $(4)$, тогда порадуюсь. Но пока этот пудинг приходится доесть до конца (будь он параллелепипед, будь он...)

[Andrey A]

P.S.
Если $a,b$ разной четности, при анализе формы $(4)$ надо брать, конечно, $b$ четное. Иначе противоречие по $\mod 2.$

Andrey A в сообщении #1595871 писал(а):

Разложением $\dfrac{p^2-q^2}{2pq}$ в непрерывную дробь получаем бесконечную серию нужных пар $(a_i,b_i)...$

Сложны для тестирования первые члены таких серий, в остальных случаях достаточно иметь представление $A_i$ суммой двух квадратов. Возьмем $A=230753=457^2+148^2$ (одно из представлений, проверять к сожалению приходится все). Разложим в неприведённую дробь $457/148=3,11,2,1,1,1,1=\dfrac{3}{1},\dfrac{34}{11},\dfrac{71}{23},\dfrac{105}{34},\dfrac{176}{57},\dfrac{281}{91},...$ Первая из двух последних дробей дает Пифагорову тройку: $176^2+57^2=185^2$, это $ Пелля; вторую можно было и не проверять — два нечетных квадрата. Отсюда $\sqrt{230753 \cdot 185^2-1}=88868$ и $88868^2-230753 \cdot 185^2=-1.$

[Andrey A]

P.S. P.S.

Andrey A в сообщении #1595871 писал(а):

Из последней дроби получаем $43805^2-181 \cdot 3256^2=9=a.\ \ \sqrt{181-9^2}=$ $10=b.\ \ \dfrac{43805+10 \cdot 3256}{9}=8485=p.\ \ 8485^2+3256^2=82596761=y$

Эти ухищрения излишни, всё проще. Дело в том что дробь, следующая за "интересной дробью" обладает теми же свойствами. В нечетном периоде их две. Из первой получаем пару $(q,\pm a),$ из второй — пару $(p,\mp a).$ Иными словами, сумма квадратов знаменателей равна искомому $y.$ В мире цепных дробей есть своя справедливость, как на небесах: $8485$ — просто знаменатель следующей подходящей дроби. А сумма произведений числителя и знаменателя равна искомому $x.$ Об этом было здесь:

Andrey A в сообщении #1077031 писал(а):

Верно и обратное: каждый палиндром обладает свойством $B^2\equiv \pm 1 \mod A.$ Здесь укажу только на тождественную связь между элементами трех подх. дробей $\dfrac{p_{k-2}}{q_{k-2}};\dfrac{p_{k-1}}{q_{k-1}};\dfrac{p_k}{q_k}$ и последних пар подх. дробей соответствующих им четных и нечетных палиндромов:

$$\dfrac{B=p_kq_k+p_{k-1}q_{k-1}}{C=q_k^2+q_{k-1}^2};\dfrac{A=p_k^2+p_{k-1}^2}{B=p_kq_k+p_{k-1}q_{k-1}} \qquad (11)$$

$$\dfrac{B=p_kq_{k-1}+p_{k-1}q_{k-2}}{C=q_{k-1}(q_k+q_{k-2})};\dfrac{A=p_{k-1}(p_k+p_{k-2})}{B=p_kq_{k-1}+p_{k-1}q_{k-2}} \qquad (12)$$