Семейство диофантовых уравнений (обобщение).

[TR63]

Задача.
Найти алгоритм решения в натуральных числах семейства диофантовых уравнений:

$$xy^2-Hy-mx^3=0$$

при $x>1$, $m\ge1$, $H\ge1$.
(Это обобщение задачи из "Олимпиадного раздела". Там она решена пока только для $m=1$.)
Прошу проверить мою попытку решения этой задачи. (Получается очень просто. Может, ошиблась.)
Решение.
$y^2>mx^2$ $\to$ $y>\sqrt m\cdot x$

$y(xy-H)-mx^3=0$

$\sqrt m\cdot x(xy-H)-mx^3<0$

$y<\frac{H+\sqrt m\cdot x^2}{x}<H+\sqrt m$

$H+\sqrt m\cdot x^2<Hx+\sqrt m\cdot x$

$\sqrt m\cdot x(x-1)<H(x-1)$

1). Т.е. получили, что при $\sqrt m\cdot x<H$ $\to$ $y<H+\sqrt m$.

2). Остаётся рассмотреть $x>\frac{H}{\sqrt m}$.
Покажем, что тогда $y\le\sqrt m(x+1)$.

$\sqrt m\cdot Hy=\sqrt m\cdot x(y^2-mx^2)$

Т.к. $\sqrt m\cdot x>H$, то

$\sqrt m\cdot y>y^2-mx^2$ $\to$ $x^2>\frac{y^2-\sqrt m\cdot y}{m}$

$x\cdot x>\frac{y}{\sqrt m}\cdot\frac{y-\sqrt m}{\sqrt m}$

Т.к. $x<\frac{y}{\sqrt m}$, то $x>\frac{y-\sqrt m}{\sqrt m}$

$\frac{y-\sqrt m}{\sqrt m}<x<\frac{y}{\sqrt m}$

Замечание.
При $m=1$ получим $(y-1)<x<y$. Т.е. в итоге $y<H+1$. Оценка немного хуже, чем в источнике, но для алгоритма перебора это не столь важно. Главное, что метод обобщается для любого натурального $(m)$.

Получили, что $y<\sqrt m\cdot x+\sqrt m$ или $y<\sqrt m(x+1)$.

Далее, из делимости следует, что должно быть $Hy=kx$. Тогда получим, что

$H\cdot\sqrt m(x+1)>kx$

$k<\frac{H\cdot\sqrt m(x+1)}{x}$

Получили, что

$k<mH$ при $x\ge3$

$x=\frac{Hy}{k}$ подставляем в исходное уравнение. Получим $y^2=\frac{k^3}{k^2-mH^2}$ при $H\le k\le mH$. Здесь имеем простой ограниченный перебор при конкретных значениях $(m)$ и $(H)$. Плюс остаётся рассмотреть отдельно случай $x\le2$ и учесть перебор при $y\le H+\sqrt m$.
Получили, что всё решается ограниченным перебором?

[nnosipov]

TR63 в сообщении #1402010 писал(а):

Получается очень просто.

Это если не задумываться о сложности (количестве "элементарных" действий) предлагаемого алгоритма решения. Под "элементарным" действием в данном случае следует понимать решение обычного (с одним неизвестным) уравнения в целых числах. Например, предлагаемый Вами перебор по $y$ подразумевает решение некоторого количества кубических уравнений относительно $x$. Это количество у Вас оценено как $H+\sqrt{m}$ и, таким образом, зависит как от $H$, так и от $m$. Между тем, можно предложить такой алгоритм решения семейства диофантовых уравнений $x(y^2-mx^2)-Hy=0$ (где $m$ и $H$ --- натуральные числа), при котором потребуется решить всего лишь $O(H^{2/3})$ обычных уравнений, причем только квадратных. Более того, константа в $O$-большом не зависит от $m$, т.е. количество решаемых уравнений будет зависеть только от $H$.

[TR63]

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

Например, предлагаемый Вами перебор по $y$ подразумевает решение некоторого количества кубических уравнений относительно $x$.

Нет. Решать кубическое уравнение не надо. В равенство

TR63 в сообщении #1402010 писал(а):

$y^2=\frac{k^3}{k^2-mH^2}$ при $H\le k\le mH$

, которое должно выполняться при конкретных наперёд заданных $(H;m)$, подставляем перебором значения (k) из указанного диапазона, полученного логическим путём (количество значений ограниченно; оно не может быть произвольным, это доказано, если что-то непонятно изложено, спрашивайте, что именно; если бы это не было доказано, тогда надо решать кубические уравнения; здесь у нас с Вами расхождение, плюс Ваше количество кубических уравнений $y<H+\sqrt m$, у меня это относится к первому случаю, не понимаю, какое отношение первый случай имеет ко второму ; тогда, пожалуйста, укажите ошибку; я её пока не вижу; может, т.к. $(k)$ зависит от $(x)$, то кубические уравнения решать надо, но это, если переменная принимает неограниченное количество значений или я ошибаюсь? ). Если равенство выполняется, значит есть решение и его можно вычислить. Равенство может не выполняться вообще; далее делаем перебор ($(H;m)$ у нас заданны) при $y\le H+\sqrt m$(это уже относится к первому случаю).
И, хотя бы для $m=1$ доказательство верно?

[nnosipov]

TR63
У Вас, как обычно, довольно мутный текст, который можно понять по-разному. Сформулируйте более конкретно, по пунктам, Ваш алгоритм решения, чтобы можно было понять, какие операции в нем производятся.

[TR63]

Хорошо, распишу более подробно.
Задача.
Найти алгоритм решения в натуральных числах семейства диофантовых уравнений:

$$xy^2-Hy-mx^3=0$$

при $x>1$, $m\ge1$, $H\ge1$.
Будет рассмотрено два случая:
1). $\sqrt m\cdot x<H$
Будет показано, что для существования решений необходимо выполнение условия:
$y\le H+\sqrt m$.
2). $x\ge\frac{H}{\sqrt m}$.
Будет показано, что для существования решения в этом случае необходимо выполнение равенства
$y^2=\frac{k^3}{k^2-mH^2}$ при $H\le k\le mH$.
(Здесь просто подставляем ограниченным перебором $(k)$ в равенство и смотрим, выполняется оно или нет; если выполняется, то обратной процедурой находим $(x;y)$ и делаем дополнительно проверку.)
Вывод: алгоритм решения (перебора) состоит из двух частей. Имеется верхняя граница для перебора $y\le H+\sqrt m$ (здесь $\sqrt m\cdot x<H$, но фактически перебирается большее количество $(x)$, $x\le y$;думаю, это не криминал)
и перебор в выполнении равенства $y^2=\frac{k^3}{k^2-mH^2}$ при $H\le k\le mH$. (Здесь $x\ge\frac{H}{\sqrt m}$.)

Если замечаний по схеме не будет, то распишу промежуточные выкладки подробнее (при необходимости).

[nnosipov]

TR63
Как я понял, в п. 1) предполагается перебор пар $(x,y)$ при условиях $x<H/\sqrt{m}$, $y<H+\sqrt{m}$ и проверка выполнения равенства $x(y^2-mx^2)-Hy=0$. Так? А что делается в п. 2)? Сформулируйте точно, я так и не понял (что перебираем, что при этом проверяем/делаем).

[TR63]

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

в п. 1) предполагается перебор пар $(x,y)$ при условиях $x<H/\sqrt{m}$, $y<H+\sqrt{m}$ и проверка выполнения равенства $x(y^2-mx^2)-Hy=0$. Так?

Да, так.

TR63 в сообщении #1402010 писал(а):

2). Остаётся рассмотреть $x>\frac{H}{\sqrt m}$.
Покажем, что тогда $y\le\sqrt m(x+1)$.

Здесь, в случае знака равенства в неравенстве, будем иметь уравнение от одной переменной (простой случай; я его не рассматриваю).

TR63 в сообщении #1402010 писал(а):

При $m=1$ получим $(y-1)<x<y$. Т.е. в итоге $y<H+1$

TR63 в сообщении #1402060 писал(а):

для $m=1$ доказательство верно?

Далее, по второму пункту будем считать, что доказана необходимость неравенства (знак равенства в нём пока не рассматриваем, т.к. это просто)
$y<\sqrt m(x+1)$ при $x\ge\frac{H}{\sqrt m}$.
Для существования решения необходимо выполнение условия $Hy=kx$. Тогда, с учётом необходимости неравенства, доказанного выше, необходимо выполнение неравенства

TR63 в сообщении #1402010 писал(а):

$H\cdot\sqrt m(x+1)>kx$

$k<\frac{H\cdot\sqrt m(x+1)}{x}$

Здесь решили неравенство относительно переменной $(k)$. Из последнего неравенства следует, что

TR63 в сообщении #1402010 писал(а):

$k<mH$ при $x\ge3$

TR63 в сообщении #1402010 писал(а):

$x=\frac{Hy}{k}$ подставляем в исходное уравнение. Получим $y^2=\frac{k^3}{k^2-mH^2}$

Знаменатель должен быть больше нуля. Т.е. $k\cdot k>m\cdot H\cdot H$. Т.к. $k<mH$ то должно быть $k>H$, чтобы выполнялось условие положительности знаменателя. Получаем, что натуральная переменная $(k)$ может принимать только ограниченное количество значений, заключённых в диапазоне $H\le k\le mH$. Т.е. имеем не уравнение, а серию равенств, которые должны выполняться (правая часть должна быть полным квадратом). Вот и проверяем их. Здесь, хотя переменная $(x)$ неограниченная, но $(k)$ ограниченная. Поэтому перебор ограничен. Если равенство выполняется при некотором значении $(k)$, то получаем после подстановки $(x)$ в исходное уравнение уравнение от одной переменной $(y)$ (это просто; не рассматриваю).

[Andrey A]

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

... что перебираем, что при этом проверяем/делаем

А это как карта ляжет. Что-то ведь нам известно! Что не известно, то и подбираем )

TR63 давайте для начала решим уравнение относительно $y=\dfrac{H\pm \sqrt{H^2+4mx^4}}{2x}.$ Перепишем это так $(2xy-H)^2=H^2+4mx^4.$ Обозначив выражение в скобочках буквой $D$, получаем

$$D^2-4mx^4=H^2$$

Вот уже видно, что для фиксированной пары произвольных аргументов $(m,H)$ такое уравнение не факт что разрешимо, и условия разрешимости я бы не взялся сформулировать. А тем более для тройки аргументов, тут уж подбирай, не подбирай... Если же аргументами назначить пару $(m,x)$, то конечно найдутся $D,H$ такие, что $4mx^4=D^2-H^2$, и целое $y=\dfrac{\pm D+H}{2x}$. И нечего тут подбирать. Да, кстати, а почему семейство?

PS при составном $x$ целое $y$ найдется не для любых пар $(D,H)$, но для некоторых найдется.

[TR63]

Andrey A, я не решала задачу об условиях разрешимости Вашего уравнения, хотя исходное к нему сводится. У меня $(m;H)$ любые конечные фиксированные. Здесь у нас, по-моему, разное понимание ситуации. Смотрите, например, есть задача: при любом конечном фиксированном $(n)$ выяснить, существует ли решение у уравнения $x^n+y^n=z^n$. И есть задача: при любом ли фиксированном $(n)$ (что эквивалентно "любое натуральное") существует решение у уравнения $x^n+y^n=z^n$. Задачи похожие, но по сложности решения разные.
Andrey A, посмотрите, пожалуйста, мой алгоритм (там выкладки все элементарные). Если найдёте ошибку, укажите, где именно она находится. Я её пока не вижу.

[Andrey A]

TR63 в сообщении #1402159 писал(а):

... об условиях разрешимости Вашего уравнения

Почему моего? Уравнение Ваше

TR63 в сообщении #1402085 писал(а):

$xy^2-Hy-mx^3=0$

А где тут аргументы Вы не сообщаете, вот и приходится гадать.

[TR63]

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

А где тут аргументы Вы не сообщаете

Да, Вы правы. Хорошо, что спросили понятным мне языком. (Вот, и надо в лоб спрашивать, что конкретно не понятно.) Добавляю к условию информацию:$(m;H)$ параметры, $(x;y)$ переменные. Поэтому, наверное, в источнике указано в названии "семейство".

-- 29.06.2019, 17:49 --

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

Почему моего?

Я не эб этом уравнении говорила, а об

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

получаем

$$D^2-4mx^4=H^2$$

Вот уже видно, что для фиксированной пары произвольных аргументов $(m,H)$ такое уравнение не факт что разрешимо, и условия разрешимости я бы не взялся сформулировать.

[nnosipov]

TR63 в сообщении #1402139 писал(а):

Получаем, что натуральная переменная $(k)$ может принимать только ограниченное количество значений, заключённых в диапазоне $H\le k\le mH$. Т.е. имеем не уравнение, а серию равенств, которые должны выполняться (правая часть должна быть полным квадратом). Вот и проверяем их. Здесь, хотя переменная $(x)$ неограниченная, но $(k)$ ограниченная. Поэтому перебор ограничен. Если равенство выполняется при некотором значении $(k)$, то получаем после подстановки $(x)$ в исходное уравнение уравнение от одной переменной $(y)$ (это просто; не рассматриваю).

В целом верно, но изложено так, что лучше не читать.

Короче, вердикт: алгоритм можно довести до ума, но при этом он окажется довольно затратный. В первом пункте объем перебора определяется произведением $(H+\sqrt{m})H/\sqrt{m}>H$, а во втором нужно решить порядка $mH$ квадратных уравнений относительно $y$ (это наиболее трудоемкая часть).

[TR63]

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

алгоритм ... окажется довольно затратный. ... а во втором нужно решить порядка $mH$ квадратных уравнений относительно $y$ (это наиболее трудоемкая часть).

Во втором случае можно сделать гипотетическое обобщение и исследовать его. Но это уже другая история.