Диофантово уравнение 1 + x^2 + x^3 + y^2 = 9xyz

[maxal]

Найдите хотя бы одно решение уравнения $1 + x^2 + x^3 + y^2 = 9xyz$ в целых числах $x,y,z$.

(источник)

[worm2]

Тупой компьютерный перебор, вероятно, не прокатит
Однако помогает найти удивительную закономерность: если $x \ne -1$ и существует решение в целых числах $1+x^2+x^3+y_1^2=xy_1z$, то непременно существует и другое такое решение $1+x^2+x^3+y_2^2=xy_2z,\, y_2 \ne y_1$. То есть решения этого упрощённого уравнения каким-то непостижимым(*) образом разбиваются на пары.

-- Вс мар 10, 2024 23:22:30 --

(*) Хммм, оказывается для постижения "непостижимого факта" достаточно умения решать квадратное уравнение. Относительно $y$ это ведь оно, что ж удивительного в том, что если у него есть один целый корень, то будет и второй?

[ИСН]

Что ж удивительного, что если один делитель $1+x^2+x^3$ сгодился на роль $y$, то и дополнительный к нему сгодится?

[qwert129]

Кв. уравнение относительно $y$ , затем зажать дискриминант между квадратами

[Dmitriy40]

А по моему решений нет: условие $|x \sqrt{81z^2-4x-4}|=2$ не выполняется ни при каких целых $x,z$.

[maxal]

Dmitriy40, решения есть.

[Dendr]

Dmitriy40 в сообщении #1632493 писал(а):

условие $|x \sqrt{81z^2-4x-4}|=2$ не выполняется ни при каких целых $x,z$.

То есть дискриминант не может быть равным нулю - и что?

Чисто пройдясь по свойствам, можно заметить, что если $(x, y, z)$ - решение, то $(x, -y, -z)$ - тоже, поэтому мы можем фиксировать знак либо у $y$, либо у $z$ (смотря что понадобится). Одновременно $x, y$ четными быть не могут. Рассматривая по модулю девятки, можем вывести, что $x\equiv4$, а $y$ обязательно кратно 3. Хотя последнее несильно помогает, разве что "удешевляет" слегка машинный перебор - но тот все равно не помогает вплоть до шестизнаков.

Можно еще заметить, что $\frac{y^2+1}{x}, \frac{1+x^2+x^3}{y}$ должны быть целыми. Вторая дробь интересна тем, что, по сути, это разложение на множители выражения $1+x^2+x^3$ так, чтобы сумма двух сомножителей делилась нацело на $9x$. Выглядит потенциально на первый взгляд, но в общем случае оно не ракладывается. Поиграться с $n$ в $x=9n+4$ пока не результатов не дало.

[Dmitriy40]

Да я выше ошибся посчитав что из разложения квадрата на множители $c^2=ax^2-b^2=(x\sqrt{a}-b)(x\sqrt{a}+b)$ следует что $\sqrt{a}$ целое, а оно не следует (один из контрпримеров $29^2=5\cdot13^2-2^2$).

Проверил перебором два варианта:
1. $z=0$, решений не нашёл до $|x|<10^{12}$.
2. $z\ne0$, решений не нашёл до $|x|<10^8$.
Если нигде снова не ошибся конечно.

[vicvolf]

Случай $z=0$ рассматривать не надо, иначе вообще не было правой части уравнения. При различных целых значениях $z$ мы получаем эллиптическую кривую над кольцом целых чисел. Характеристика кольца целых чисел равна $0$, поэтому путем преобразования координат наша эллиптическая кривая приводится к канонической форме $y^2=x^3+ax+b$, т.е. к нормальной форме Вейрштрасса. Это к вопросу накопления свойств данного уравнения. Как это использовать пока не знаю.
Интересным свойством исходного уравнения, как уже говорилось, является то, что левая часть уравнения должна быть кратна $9$, так как это значительно сокращает количество вариантов перебора. Кроме того, для того, чтобы левая часть была отрицательна, значение $x$ должно быть отрицательно. В этом случае, для того чтобы правая часть тоже была отрицательна, произведение $yz>0$, т.е $y,z$ должны иметь одинаковые знаки. Интересно в переборе рассмотреть именно этот случай: $x<0$, $yz>0$ и значение $1+x^2+x^3+y^2$ - кратно $9$. Может быть это что-то даст?

[Dmitriy40]

Вариант с $z\ne0$ проверил до $|x|<10^9$, заняло 14ч (при том что до $10^8$ хватило 40 минут).
На всякий случай опишу алгоритм.
В квадратном относительно $y$ уравнении дискриминант равен $D=\sqrt{(81z^2-4x-4)x^2-4}=\sqrt{ax^2-4}$ и он обязан быть целым (и даже кратным 3), причём $a$ (скобка под корнем) всегда целое, потому можно перебирать $D$, возводить в квадрат, добавлять 4 и раскладывать на множители, отбрасывая варианты не содержащие квадрата ($x=\pm1$ проверяется отдельно). Для оставшихся проверяется условие $x=4\mod9$ для делителя в квадрате, для подходящих вычисляется частное $(D^2+4)/x^2+4$ и проверяются два варианта условия $(D^2+4)/x^2+4\pm 4x=0\mod81 \wedge ((D^2+4)/x^2+4\pm 4x)/81=z^2$ (т.е. что делится на 81 и что извлекается корень, первое просто для ускорения вычислений, оно конечно поглощается вторым). При нахождении такого $|z|$ можно посчитать и четыре $y$, но до $D<10^9$ (а соответственно и $|x|<10^9$ потому что может быть $a=1$, а добавкой $+4$ при больших $D$ можно пренебречь) ни одного подходящего $z$ не нашлось.

[vicvolf]

Dmitriy40 в сообщении #1632932 писал(а):

Вариант с $z\ne0$ проверил до $|x|<10^9$, заняло 14ч (при том что до $10^8$ хватило 40 минут).

Спасибо!

Dmitriy40 в сообщении #1632932 писал(а):

ни одного подходящего $z$ не нашлось.

Странно.

maxal в сообщении #1632504 писал(а):

Dmitriy40, решения есть.

[Dmitriy40]

Вариант $z\ne0$ проверил за 45 минут до $|y|<10^8$, что соответствует $|x|<10^{16}$. Подходящих $z$ не нашёл.
Алгоритм.
Без ограничения общности полагаем $y>0$ (иначе можно просто поменять знак $z$ и вернуть $y>0$).
Перепишем исходное уравнение в виде $y^2+1=x(9zy-x^2-x)$. Отсюда видно что $x$ должно быть делителем $y^2+1$ (возможно с минусом). Перебираем $y$ (кратные 3), для каждого перебираем делители $y^2+1$, это будет $x$ (причём $x\le y^2+1$), Теперь знаем $y$ и $x$, подставляем их в исходное уравнение и проверяем делимость левой части $|y^2+1+x^2 \pm x^3|$ (два значения чтобы учесть оба знака $x$) на величину $9xy$ (т.е. чтобы $z$ было целым).

[worm2]

Вроде бы, если мы перебрали все $|y|<A$, это ещё не означает, что мы перебрали все $|x|<A^2$.
Например, у похожего диофантова уравнения $1+x^2+x^3+y^2=3xyz$ сравнительно легко найти перебором несколько решений. Перебрав все $|y|<10^4$, мы найдём решения $x=-5$, $x=-221$ ($y=3$ и $1347$). Однако не отыщем $x=-3965$, которое соответствует $y=43077$.

[Dmitriy40]

Вы правы, с $y$ на $x$ условие не переносится. Значит только $|y|<10^8$.

[worm2]

Выглядит привлекательной идея вести перебор по $x$. В этом случае наиболее затратной операцией является факторизация $A=1+x^2+x^3$.
С другой стороны, мы ищем только такую факторизацию $A=B\cdot C$, у которой $B+C$ делится на $x$ (точнее, конечная цель — чтобы оно делилось на $9x$). То есть, если $B \pmod x \equiv b$, то должно быть $C \pmod x \equiv -b$. Далее, поскольку $A \equiv 1 \pmod x$, нас устраивает только такой остаток $b$, для которого $-1$ является квадратичным вычетом по тому же модулю $x$.
На конкретном примере: $x=-3965$. Мы должны искать такие сомножители $1+x^2+x^3=B\cdot C$, что остатки от деления $B$ и $C$ на $x$ противоположны (пусть будут $b$ и $-b$) и $b^2 \equiv -1 \pmod x$ (точнее, в задаче нам нужно $\pmod {9x}$, но мы пока ищем там, где светлее). Для $x=-3965$ таких $b$ всего четыре: $\pm 538$, $\pm 1048$, $\pm 1087$, $\pm 1292$. Т.е. мы должны искать сомножители $B$ и $C$, которые имеют только эти 4 остатка при делении на $x$. В данном примере действительно, есть такое разложение: $1+3965^2-3965^3=-43077\cdot 1446687=(3965\cdot(-11)+538)(3965\cdot 365-538)$. Видно что сомножители имеют при делении на $3965$ противоположные остатки $\pm 538$, поэтому их сумма делится на $x$ (и даже на $3x$, но не на $9x$, как нам надо). Могут ли эти соображения как-то радикально сократить время факторизации, да и можно ли вообще быстро отыскать нужные квадратичные вычеты — для меня тёмный лес.

-- Вс мар 17, 2024 14:37:50 --

Можно показать, что остаток от деления $x$ на $27$ равен 4 либо 13. Это, конечно, даёт сокращение перебора на порядок, но такое сокращение я не назову радикальным.