Диофантовы уравнения 2 степени, обобщения уравнений Пелля

[nnosipov]

ex-math в сообщении #842688 писал(а):

А более или менее простых условий разрешимости уравнения (безотносительно числа серий) тоже нет?

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

Для некоторых частных уравнений (типа $x^2-2y^2=c$) условия разрешимости есть --- в стиле условий разрешимости уравнения $x^2+y^2=n$. Можно ли предложить что-нибудь получше? Увы, не знаю.

ex-math в сообщении #842688 писал(а):

Если Вы выложите здесь свои материалы по уравнению Пелля, я с большим интересом почитаю.

Ловлю Вас на слове Будет два не очень многостраничных текста. Мне нужно некоторое время (за эти выходные справлюсь), чтобы их причесать. Буду благодарен за замечания и комментарии.

[ex-math]

Для $-1$ можно пользоваться тем, что наименьшее натуральное $y$, которое ему удовлетворяет, меньше наименьшего натурального $y$, удовлетворяющего уравнению с $+1$. На практике довольно удобно -- при переборе возрастающих $y$ либо натыкаетесь на решение для $-1$, либо для $+1$. В последнем случае решений нет.
А вот для других $c$ непонятно, насколько велико может быть первое натуральное решение. Можно, конечно, искать пары целых чисел, удовлетворяющие неравенствам, типа приведенных в "Кванте", но именно из-за возможности $x$ и $y$ иметь разные знаки поле перебора огромно.

[nnosipov]

ex-math в сообщении #842704 писал(а):

А вот для других $c$ непонятно, насколько велико может быть первое натуральное решение.

Да, это проблема. Если $c$ мало по сравнению а $A$ (меньше $\sqrt{A}$, кажется), то подходящие дроби к $\sqrt{A}$ работают и базовые решения быстро находятся. А вот что делать с большими $c$, непонятно.

[nnosipov]

Вот первый текст. Здесь обсуждается вопрос, как сразу получить все решения уравнения $x^2-Ay^2=B$ в целых неотрицательных числах, а также приводятся примеры решения уравнений 2-й степени общего вида (эти примеры затем вошли в статью из "Кванта", 2002, № 4, упр. 53 на стр. 11).

[nnosipov]

Вот второй текст. Здесь предлагается усовершенствованный подход к отысканию базисных решений уравнения $x^2-Ay^2=B$.

[ex-math]

Прошу прощения, что пропал надолго. Тексты просмотрел -- спасибо, очень интересно, особенно второй. В принципе можно сказать, что проблема поиска наименьшего решения или доказательства его отсутствия решена. Лаконичное условие $y\leqslant\sqrt{|B|}y_0$ более чем удобно для практических нужд. Попозже постараюсь посмотреть детальнее.

[nnosipov]

ex-math, спасибо. Мне хотелось предложить некий общий простой подход, с помощью которого можно было бы успешно бороться с олимпиадными задачами типа следующей: если $k>1$, $l>1$, то равенство $kx^2-klxy+ly^2=1$ невозможно в целых числах. (Обычно здесь применяют разные фокусы, а хочется чего-то алгоритмичного.) Во втором тексте было десятка три таких задач (разной степени сложности, в основном довольно сложных), которые я постепенно насобирал и частично сам придумал. Поскольку пока это существует в виде большой свалки, лучше пока не показывать. Как только разгребу, попрошу Вас почитать.

[ex-math]

nnosipov
Теорема 2 впечатляет: оценка точная (достигается, например для $x^2-2y^2=18$) и существенно снижает диапазон перебора по сравнению с оценкой внизу стр.6. Как и последняя, она годится не только для наименьшего решения, но и для всех базовых, если только позволить отрицательные значения неизвестных. С другой стороны, верхние оценки теоремы 1 в точности совпадают с последним неравенством в тексте. Но это неравенство (вместе с теоремой 2) доказывается гораздо короче и изящнее.

[nnosipov]

ex-math в сообщении #848776 писал(а):

С другой стороны, верхние оценки теоремы 1 в точности совпадают с последним неравенством в тексте.

Да, это мне надо было явно указать (теперь сделал). С теоремой 2 мне откровенно повезло --- просто наткнулся на удачную формулировку. В книге Barbeau E.J. Pell's equation. New-York: Springer-Verlag, 2003. более трудовой подход (см. серию упражнений на стр. 49-52).