2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Интересное свойство уравнения Пелля
Сообщение08.05.2023, 16:31 


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

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение08.05.2023, 18:39 
Заслуженный участник
Аватара пользователя


21/11/12
1897
Санкт-Петербург
Иксы и игреки в выражениях $x^2 - dy^2 = -1$ и $mx^2 - ny^2 = 1$ — одни и те же числа?

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение08.05.2023, 21:19 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение08.05.2023, 23:49 


21/04/22
339
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}$. А дальше, видимо, нужно как-то применить теорию подходящих дробей. Можно ли где-то почитать об этом более подробно?

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение09.05.2023, 02:46 
Заслуженный участник
Аватара пользователя


21/11/12
1897
Санкт-Петербург
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.$ Можете еще тут посмотреть.

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение09.05.2023, 14:20 


21/04/22
339
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$, а для части нет?

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение09.05.2023, 18:40 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение10.05.2023, 08:49 
Заслуженный участник
Аватара пользователя


21/11/12
1897
Санкт-Петербург
Andrey A в сообщении #1593199 писал(а):
знаменатель вз. прост с числителем (а значит и с $m$)...
Опять неточно выразился, ведь $m$ — либо делитель, либо удвоенный делитель $d$, и, кажется, возможен общий делитель $2$, но сути дела это всё равно не меняет. А вот вопрос когда уравнение $x^2 - dy^2 = -1$ не имеет решений не такой уж безнадежный. Постараюсь высказаться на сей счет.

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение10.05.2023, 11:10 


21/04/22
339
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$ получается именно фундаментальное решение уравнения Пелля, а не какое-то другое.

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение10.05.2023, 14:57 


26/08/11
2082
Andrey A в сообщении #1593252 писал(а):
А вот вопрос когда уравнение $x^2 - dy^2 = -1$ не имеет решений не такой уж безнадежный. Постараюсь высказаться на сей счет.
nnosipov в сообщении #842694 писал(а):
Смотря что считать простым условием. Вот с уравнением $x^2-Ay^2=-1$ уже проблемы --- вопрос о его разрешимости сводится к выяснению чётности длины периода цепной дроби для $\sqrt{A}$. А для каких $A$ она чётна, похоже, никто не знает.

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение10.05.2023, 17:30 
Заслуженный участник
Аватара пользователя


21/11/12
1897
Санкт-Петербург
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$ для них неразрешимо, но общим случаем это не является, поскольку дело не в длине периода. Дайте время разобраться.

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение11.05.2023, 12:05 
Заслуженный участник
Аватара пользователя


21/11/12
1897
Санкт-Петербург
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$ знаков. Утверждать, что их бесконечно много и любой длины — не возьмусь, это требует доказательства. Но похоже на то.

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение11.05.2023, 19:19 


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

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение19.05.2023, 16:14 
Заслуженный участник
Аватара пользователя


21/11/12
1897
Санкт-Петербург
Тут возможен иной подход, совсем простой. Пусть нечетные $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$ знаков, дальше уж не считал. Странно. С ростом величин вероятность получить квадрат при тестировании уменьшается, и в роли "исключения" оказываются нечетные периоды. Однако же четных и нечетных палиндромов в некотором смысле равное количество. Целых радикалов среди последних видимо меньше, но не на порядок же. Очень странно.

 Профиль  
                  
 
 Re: Интересное свойство уравнения Пелля
Сообщение21.05.2023, 08:02 
Заслуженный участник
Аватара пользователя


21/11/12
1897
Санкт-Петербург
Кое-что еще. Последовательность $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$ свободную от квадратов, получаем зеленые с нечетным периодом, что и не удивительно ) Но вразбивку.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 28 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group