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

[mathematician123]

Натуральное число $d$, не являющееся точным квадратом, даёт остаток 1 или 2 при делении на 4. Докажите, что уравнение $x^2 - dy^2 = -1$ тогда и только тогда имеет решения, когда при любых натуральных $m, n > 1$, таких что $mn = d$, уравнение $mx^2 - ny^2 = 1$ неразрешимо.

[Andrey A]

Иксы и игреки в выражениях $x^2 - dy^2 = -1$ и $mx^2 - ny^2 = 1$ — одни и те же числа?

[Andrey A]

Ну, я понял Ваше молчание, хотя ответить было бы вежливо с Вашей стороны. Решение уравнения $mx^2 - ny^2 = 1$ следует из предпоследней подходящей дроби полупериода четного периода разложения $\sqrt{d}.$ Об этом было здесь. Четверку $m,n,x,y$ получаем после сокращения слагаемых на остаток вида $p^2-dq^2=r.$ Если полупериодом является нечетный период, имеем случай $r=-1$ и решение ур-я $x^2 - dy^2 = -1.$ Оба решения следуют из одной и той же дроби, поэтому либо - либо. Ничего чудесного тут не вижу.

[mathematician123]

Andrey A
К сожалению, плохо знаком с подходящими дробями. Пока только сообразил, что из $mx^2 - ny^2 = 1$ следует $(mx)^2 - dy^2 = m$ и $(ny)^2 - mnx^2 = -n$. А так как $m < \sqrt{d}$ либо $n < \sqrt{d}$, то одно из этих представлений получается из разложения $\sqrt{d}$. А дальше, видимо, нужно как-то применить теорию подходящих дробей. Можно ли где-то почитать об этом более подробно?

[Andrey A]

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

$(mx)^2 - dy^2 = m$

Здесь выписана в общем виде дробь $\dfrac{mx}{y}$ — предпоследняя подходящая дробь полупериода четного периода разложения $\sqrt{d}$. Она характерна тем, что остаток $m$ (у меня было $r$) является делителем или удвоенным делителем $d$ и, соответственно, числителя дроби. После сокращения на $m$ получаем решение второго Вашего уравнения, коего первое уравнение является частным случаем $m=-1.$ Это бывает, когда $d$ — сумма двух взаимно простых простых квадратов, но последнее условие не является достаточным, и это действительно интересный вопрос. Достаточное условие — нечетный период разложения $\sqrt{d}$. Просто примите к сведенью. А подходящие дроби суть рациональная аппроксимация, об этом есть в любой литературе о цепных дробях, хотя бы у Хинчина: $a_1,a_2,...,a_n,...=\dfrac{a_1}{1},\dfrac{a_1a_2+1}{a_2},...,\dfrac{p_{n+1}=a_{n+1}p_n+p_{n-1}}{q_{n+1}=a_{n+1}q_n+q_{n-1}},...$ Основное свойство $p_nq_{n-1}-p_{n-1}q_n=(-1)^n,$ на чем основано решение ур-я $ax-by=\pm1.$ Можете еще тут посмотреть.

[mathematician123]

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

Решение уравнения $mx^2 - ny^2 = 1$ следует из предпоследней подходящей дроби полупериода четного периода разложения $\sqrt{d}.$

Вроде почти разобрался. Остался один вопрос. Каждому решению уравнения $mx^2 - ny^2 = 1$ соответствует некоторое решение уравнения $X^2 - mnY^2 = m$ (просто берём $X = mx$, $Y = y$). Но верно ли это утверждение в обратную сторону? Пусть $X^2 - mnY^2 = m$. Тогда $m \mid X^2$. Если $m$ свободно от квадратов, то как и требуется получаем $m \mid X$, откуда после сокращения на $m$ получим решение уравнения $mx^2 - ny^2 = 1$. Но что делать, если $m$ делится на квадрат простого числа? Тогда делимость $m \mid X$ совсем не обязательна. Может ли получиться так, что для части решений уравнения $X^2 - mnY^2 = m$ есть делимость $m \mid X$, а для части нет?

[Andrey A]

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

Может ли получиться так, что...

Может, конечно. Из $m \mid d$ следует только, что $m$ делит квадрат числителя, а не сам числитель. Я тут неточно выразился. Но сути дела это не меняет, поскольку знаменатель вз. прост с числителем (а значит и с $m$) по свойству подходящих дробей. Вопрос только в том, куда приткнуть квадрат, чтобы не нарушалось равенство $d=mn.$ Уравнение $mx^2-ny^2=1(2)$, вообще говоря, "первородное", Пелль берется из него как следствие. Вычислять большие дроби второго полупериода — лишняя работа.

[Andrey A]

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

знаменатель вз. прост с числителем (а значит и с $m$)...

Опять неточно выразился, ведь $m$ — либо делитель, либо удвоенный делитель $d$, и, кажется, возможен общий делитель $2$, но сути дела это всё равно не меняет. А вот вопрос когда уравнение $x^2 - dy^2 = -1$ не имеет решений не такой уж безнадежный. Постараюсь высказаться на сей счет.

[mathematician123]

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

Точнее сказать так: для каждого $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.$ И получили бы второе решение Пелля, чего не бывает.

Здесь важно отметить, что если уравнение $mx^2 - ny^2 = 1$ имеет решения, то для минимального решения этого уравнения верны неравенства $x < x_0$, $y < y_0$, где $(x_0, y_0)$ - фундаментальное решение уравнения $x^2 - dy^2 = 1$ (я буду пользоваться обозначениями $m, n, d$).

Докажем это. Рассмотрим случай $m < \sqrt{d}$ (случай $n < \sqrt{d}$ рассматривается аналогично). $(mx)^2 - dy^2 = m$. Рассмотрим уравнение $X^2 - dY^2 = m$. Уравнение $mx^2 - ny^2 = 1$ имеет решения тогда и только тогда, когда уравнение $X^2 - dY^2 = m$ имеет решение, для которого $m \mid X$. Все решения этого уравнения следуют из подходящих дробей, поэтому для них верна формула $X_k + \sqrt{d} Y_k = (X_0 + Y_0 \sqrt{d})(x_0 + y_0 \sqrt{d})^k$. Из этой формулы можно вывести, что $\gcd(X_i, m) = \gcd(X_0, m)$. Это значит, что минимальное решение уравнения $mx^2 - ny^2 = 1$, если оно существует, имеет вид $(\frac{X_0}{m}, Y_0)$. И неравенства $\frac{X_0}{m} < x_0$ и $Y_0 < y_0$ выполнены, так как решения уравнений $x^2 - dy^2 = 1$ и $X^2 - dY^2 = m$  получаются из подходящих дробей для $\sqrt{d}$.

Изначально меня смутила фраза "И получили бы второе решение Пелля, чего не бывает". Ведь уравнение Пелля имеет бесконечно много решений. А теперь понятно. После возведения в квадрат минимального решения $mx^2 - ny^2 = 1$: $(mx^2 + ny^2)^2 - d(2xy)^2 = 1$ получается именно фундаментальное решение уравнения Пелля, а не какое-то другое.

[Shadow]

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

А вот вопрос когда уравнение $x^2 - dy^2 = -1$ не имеет решений не такой уж безнадежный. Постараюсь высказаться на сей счет.

nnosipov в сообщении #842694 писал(а):

Смотря что считать простым условием. Вот с уравнением $x^2-Ay^2=-1$ уже проблемы --- вопрос о его разрешимости сводится к выяснению чётности длины периода цепной дроби для $\sqrt{A}$. А для каких $A$ она чётна, похоже, никто не знает.

[Andrey A]

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

Изначально меня смутила фраза "И получили бы второе решение Пелля, чего не бывает". Ведь уравнение Пелля имеет бесконечно много решений.

Да, под "решением Пелля" имелась в виду серия, конечно. Если бы для двух пар множителей $d$ оказалось разрешимо $mx^2-ny^2=1 $, получили бы две серии, что следует из тождества $4mnx^2y^2=(mx^2+ny^2)^2-(mx^2-ny^2)^2=mn(2xy)^2.$ А получилось непонятно, спасибо за уточнения.
Shadow
Об том и речь. Вы цитируете nnosipov, очень его не хватает, как и остальных. Он бы меня покритиковал (осиротели мы на ровном месте ;) Описать все $A=p^2+q^2$ c четным периодом разложения вряд ли возможно "росчерком пера". Но можно указать метод, которым каждое такое исключение может быть получено. Вот, к примеру, числа вида $(ab)^2 \pm a$ и $(ab)^2 \pm 2a.$ Среди них бесконечно много сумм двух квадратов, и все они имеют период $2-4$ знака. Благодаря малому периоду удается свести дело и к некоторому уравнению. $x^2-Ay^2=-1$ для них неразрешимо, но общим случаем это не является, поскольку дело не в длине периода. Дайте время разобраться.

[Andrey A]

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

$$x^2-Ay^2=-1$$

Да, серьезная задача. Это не жук на скатерть начхал (вольный перевод с английского); но ничего, кое-что выяснить удалось. Назовем "зелеными" для краткости суммы двух взаимно простых квадратов. Поскольку $x^2 \equiv -1 \pmod {y^2}$, $y^2$ — зеленое. Более того, $y^2$ — нечетное зеленое, так как $x^2+1$ не делится на $4.$ $A$ тоже зеленое. Выяснить, не является ли данное $A$ исключением (четный период) иного способа нет, кроме как посчитать количество знаков разложения $\sqrt{A}$ (чтобы узнать вкус пудинга... и т.д.) Но можно попробовать упорядочить зеленые, и начать лучше как раз с "правильных" (нечетный период). Наименьший $y=5.$ Найдем $x^2 \equiv -1 \pmod {5^2}=7^2,$ и перепишем наше уравнение так: $\dfrac{7^2+1}{5^2}=2.$ Теперь ничто не мешает взять $7 \pmod {5^2}$ и получить последовательность $A_n(5):$

$$\dfrac{(7+25n)^2+1}{5^2}=2,41,130,269,458,697,...$$

Нечетные периоды разложения членов такой последовательности содержат одинаковое количество знаков и отличаются друг от друга только последним знаком. Значит, можем брать зеленые игреки по возрастанию и строить от каждого подобные последовательности, перечислив таким способом на некотором участке числовой прямой все "правильные" $A.$ Которые сюда не вошли — суть исключения. Но на практике действовать по остаточному принципу — не очень хороший выход. Четный период разложения "неправильные" зеленые все же имеют. Значит, можем выбрать $y^2$ (уже не обязательно зеленый), найти для него квадрат сравнимый с единицей и завести подобную процедуру, выискивая в последовательности "зеленые члены". Но тут возникает масса тонкостей. Во-первых периоды из одного знака. Строго говоря, они нечетные, но маленькие периоды были описаны выше явной формулой, и во избежание путаницы лучше ей и ограничится. Во-вторых четность иксов. Честно сказать, до сих пор я был уверен, что квадрат без единицы (кроме $3^2-1=8$) содержит в каноническом разложении нечетное простое вида $4k+3$ в нечетной степени. Но это верно только для четных квадратов, иначе и проблемы не было бы. Значит $x$ нечетное, $y$ четное (поскольку двойку зеленое число может содержать только в $1$-й степени). Далее возникает ограничение $x \equiv 1,3 \pmod 8.$ И, если нужно совсем точно, предложу следующую формулировку. Выпишем по возрастанию числа, содержащие простые делители вида $4k+3$ только в четных степенях: $1,2,4,5,8,9,10,13,16,17,18,...$ OEIS A001481. Суммы соседних членов в ней, отличных на $1$ возвращают последовательность иксов пригодных для нашей задачи: $1+2=3,4+5=9,8+9=17,9+10=19,...$ и т.д. Она тоже есть в OEIS A050795. Остальные можно сразу откидывать, но я выпишу пример $x_0=199,y_0=30$ уж как есть. Да, и важная деталь: в случае четного $y$ иксы берутся не по $\mod {y^2},$ а по $\mod {y^2/2}.$

$$\dfrac{(199+450n)^2-1}{30^2}=44,468,1342,...,182016,195040,208514(n=30),...$$

$208514=2\cdot 137\cdot 761.$

$\sqrt{208514}=456,\overline{1,1,1,2,1,1,1,912},...$ Получили зеленое число с четным периодом в $8$ знаков. Утверждать, что их бесконечно много и любой длины — не возьмусь, это требует доказательства. Но похоже на то.

[mathematician123]

Оказывается, исходная задача, но в другой формулировке, уже дважды обсуждалась на форуме: https://dxdy.ru/topic140306.html, https://dxdy.ru/topic37895.html.

[Andrey A]

Тут возможен иной подход, совсем простой. Пусть нечетные $a,b,c,d$ таковы, что $ab-cd=-2$. Для них определено $p=\dfrac{a+b+c+d}{2}$.

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

Генерировать такие четверки удобно непрерывной дробью: если $a/c=u_1,u_2,...,u_{n-2},u_{n-1},u_{n},$ то наименьшие $d/b$ определены дробью $u_1,u_2,...,u_{n-2},u_{n-1},u_{n}-2$ (без двух) или, если $u_{n}=2,$ — дробью $u_1,u_2,...,u_{n-2}$ (без двух последних знаков).

Перепишем это так: $\left ( \dfrac{a+b}{2} \right )^2-\left ( \dfrac{a-b}{2} \right )^2-\left ( \dfrac{c+d}{2} \right )^2+\left ( \dfrac{c-d}{2} \right )^2=-2$ и так:

$$\left [ \left ( \dfrac{a+b}{2} \right )^2+\left ( \dfrac{c-d}{2} \right )^2 \right ]-\left [ \left ( \dfrac{a-b}{2} \right )^2+\left ( \dfrac{c+d}{2} \right )^2 \right ]=-2\ \ \ (3).$$

Вынося за квадратные скобки общие делители слагаемых, получаем выражение вида $mx^2-ny^2=-2$, и тут прямое отношение к теме. Если числа в квадратных скобках нечетные — уже знаем, что Пелль на основании такого равенства может быть построен только с четным периодом. Если же значения в квадратных скобках суть четные числа, почленным делением на $2$ после некоторых преобразований получаем

$$\left [ \left ( \dfrac{p-d}{2} \right )^2+\left ( \dfrac{p-c}{2} \right )^2 \right ]-\left [ \left ( \dfrac{p-b}{2} \right )^2+\left ( \dfrac{p-a}{2} \right )^2 \right ]=-1.$$

Чтобы предполагаемый Пелль имел нечетный период, необходимо и достаточно чтобы сумма в левых квадратных скобках равнялась целому квадрату. Икс Пелля равен полусумме квадратных скобок выражения $(3):$ $X=\dfrac{a^2+b^2+c^2+d^2}{4}.$ И далее (чтобы не усложнять) будем считать исследуемую величину $M$ свободной от квадратов: $M=\dfrac{X^2-1}{D^2},$ где $D$ — максимально возможный квадратный делитель числителя. Таким образом, строя из некоторых $ab-cd=-2$ пеллеобразное равенство

$$\left ( \dfrac{a^2+b^2+c^2+d^2}{4} \right )^2-MD^2=1,$$

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

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

При том, что само $M=\left [ \left ( \dfrac{p-a}{2} \right )^2+\left ( \dfrac{p-b}{2} \right )^2 \right ]\left [ \left ( \dfrac{p-c}{2} \right )^2+\left ( \dfrac{p-d}{2} \right )^2 \right ]$ "освобожденное" от квадратов.

Возьмем пример $a=599,c=379.\ \ \ 599/379=1,1,1,2,1,1,1,1,5,2.$
$1,1,1,2,1,1,1,1=49/31=d/b.\ \ \ 599 \cdot 31-379 \cdot 49=-2.$
$p=(599+31+379+49)/2=529.\ \ \ X=(599^2+31^2+379^2+49^2)/4=126451.$ Пелль:$126451^2-17766506 \cdot 30^2=1.$
Тест на нечетность: $\left ( (529-379)/2 \right )^2+\left ( (529-49)/2 \right )^2=$ $75^2+240^2=63225=281 \cdot 15^2$ не является целым квадратом. Следовательно, период разложения $M=17766506=2 \cdot 101 \cdot 281 \cdot 313$ четный.
Проверка: $\sqrt{17766506}=4215,\overline{30,8430},...$

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

Выяснить, не является ли данное $A$ исключением (четный период) иного способа нет, кроме как посчитать количество знаков разложения $\sqrt{A}$

Вроде бы так. Но. Если в вышеприведенном примере убрать из $M=17766506$ множитель $2,$ разложение займет не менее $800$ знаков, дальше уж не считал. Странно. С ростом величин вероятность получить квадрат при тестировании уменьшается, и в роли "исключения" оказываются нечетные периоды. Однако же четных и нечетных палиндромов в некотором смысле равное количество. Целых радикалов среди последних видимо меньше, но не на порядок же. Очень странно.

[Andrey A]

Кое-что еще. Последовательность $3,9,17,19,33,35,... $ OEIS A050795 является по сути последовательностью иксов уравнения Пелля для зеленых $M.$ Если считать $M$ свободным от квадратов, то посредством факторизации можем получить из нее все пеллеобразные равенства:

$3^2-2 \cdot 2^2=1,$

$9^2-5 \cdot 4^2=1,$

$17^2-2 \cdot 12^2=1,$

$19^2-10 \cdot 6^2=1,$

$33^2-17 \cdot 8^2=1,$

$35^2-34 \cdot 6^2=1,...$ и т.д. Выше было показано, что каждый член указанной последовательности может быть получен из четверки нечетных $ab-cd=-2:$

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

И поскольку каждое $M$ имеет строго либо четный либо нечетный период разложения, можем перенести это свойство на иксы: четные и нечетные — две непересекающиеся подпоследовательности. Вначале идут нечетные (первый четный — $35$), но по мере роста величин шансы получить нечетное $X$ из произвольной четверки $a,b,c,d$ падают, и с большой вероятностью получаем четное. "Тест на нечетность" описан выше. Но есть и прямой способ получить четверки $a,b,c,d$, соответствующие нечетным $X.$ Источником является, конечно, пифагорова тройка $u^2+v^2=t^2$ (необязательно примитивная) и пара переменных $p,q$ таких, что $t^2+1=p^2+q^2$ (в том числе и $p=t,q=1$). Если эти равенства верны, то

$$\left | u+v+p+q \right |=a$$

$$\left | u+v-p-q \right |=b$$

$$\left | u-v+p-q \right |=c$$

$$\left |u-v-p+q \right | =d$$

и снова

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

Доказательство пока опускаю, возьмем пример $56^2+42^2=70^2;\ \ \ 70^2+1=50^2+49^2.$

$\left | 56+42+50+49 \right |=197$

$\left | 56+42-50-49 \right |=1$

$\left | 56-42+50-49 \right |=15$

$\left | 56-42-50+49 \right |=13$

Отсюда $\dfrac{197^2+1^2+15^2+13^2}{4}=9801$ и $9801^2-29 \cdot 1820^2=1.$

Но можно и так:

$\left | 56+42+70+1 \right |=169$

$\left | 56+42-70-1 \right |=27$

$\left | 56-42+70-1 \right |=83$

$\left | 56-42-70+1 \right |=55$

$\dfrac{169^2+27^2+83^2+55^2}{4}=9801$ и т.д. Есть еще вариант $70^2+1=65^2+26^2$ и с тем же результатом. Никак не пойму, могут ли привнести варианты параметры $p,q$ ? Ведь $70$ в данном случае — икс уравнения $70^2-29 \cdot 13^2=-1$, для $M=29$ оно имеет единственное решение, а детали нас не интересуют. Если так, обходимся элементами пифагоровой тройки: $u+v+t+1=a, u+v-t-1=b,...$ и ситуация упрощается до предела.

P.S. То есть, выписывая последовательность $n^2+1$ свободную от квадратов, получаем зеленые с нечетным периодом, что и не удивительно ) Но вразбивку.