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

[juna]

EUgeneUS в сообщении #1633594 писал(а):

Но все равно, один из 9 это больше, чем 4 из 81.

11 из 243 еще меньше )

-- Чт мар 21, 2024 11:50:51 --

worm2 в сообщении #1633589 писал(а):

Несколько удивляет, что $y$ мало по сравнению с $x$.

Наверное потому, что перебор идет именно по $y$...

[mathpath]

Поскольку
НОД(y² + 1, x) = x
Предлагаю вычислительный алгоритм:
1. Берем случайное y (~20 разрядов), возводим в квадрат, прибавляем 1
2. Делим результат на случайное число (~10 разрядов) до тех пор, пока не получаем целое x
3. Вычисляем левую часть: 1 + x² + x³ + y²
4. Делим левую часть на 9xy до тех пор, пока не получим целое z

Вопросы:
1. Какое y брать на первом шаге ?
2. Какое число брать на втором шаге ?

[juna]

Это, конечно, шуточно, но вот еще одно решение, полученное из второго решения maxal:

x = 134398663297274547209137686278055005569690302475018
y = 24450051153288123059132476272200502387987242977022468588628892545501208182968552681649479327690850941874270568150324269
z = 20213536978090153723578064261881061403832912545088461051439794069731

$x, z$ те же, $y$ поменялось

[maxal]

juna в сообщении #1633612 писал(а):

Это, конечно, шуточно, но вот еще одно решение, полученное из второго решения maxal:

Как говорится, "тепло".

[Cos(x-pi/2)]

Вот, тоже шуточно получил - из первого решения maxal. $x, z$ те же, $y$ поменялось :

x = -19578556686240310295378317903565
z = 418962851513108789978912616277180591709694

y = -73824191440004541629580002277896931688661875254219846484796640446223251877

(я сосчитал новое $y$ по известным $x, y, z,$ и проверил с новым $y$ равенство $1 + x^2 + x^3 + y^2 = 9xyz$ в WolframAlpha. Не знаю, насколько такому результату можно верить). Увы, никакого понимания, как по-настоящему решается эта задача, у меня не возникло.

(Оффтоп)

У нас, у физиков, таких чисел в жизни не бывает; они даже в страшном бредовом сне не приснятся .

[Ivan 09]

Пришла следующая идея
замена $z=mx+ny+l$
получим $1+x^2+x^3+y^2-9xy(mx+ny+l)=0$ Считаем l-числом.
поделим на $y$ и зная, что $(1+x^2+x^3) $ делится на $y$
получим $p_1+y-9x^2m-9xn-9xl=0$
дальше скомпонуем, так чтобы у нас получилось произведение сомножителей..
$p_1+y-9x^2m-9xny-9xyl=0$
возьмем $l$ девять в степени.
$p_1+y-9x^2m-9xny-9xl=0$
В итоге мы можем подбирать числа так чтобы, они превратились в произведение.
$p_1+y(1-9xn)-9x^2m-9xl=0$
Дальше дело в том, чтобы находить общие делители и подобрать соответствующие $m,n,l$
$p_1+y(1-9xn)-9x(xm-l)=0$
Должно получится, всегда можно найти такую комбинацию.
дальше получится Примерно
$(y-9x)(1-9q)=p_1$
Отсюда в ответах такие большие числа
Придется делить многочлен на многочлен и смотреть, чтобы не было дробей.

[juna]

Можно заметить, что в решениях maxal

$$y\approx\frac{x+x^2}{9z}$$

с достаточной точностью, т.е. один корень много меньше другого.
Правда, неясно, чем это может помочь.

[makxsiq]

А физический смысл в этом есть?
Или профит здесь лишь в том, что наглядно видно, что неразрешимость диофантовых уравнений не доказывает $P \neq NP$ ?

[mathpath]

Тут раньше Vadim32 предлагал алгоритм поиска с разложением на множители
Для 40-разрядных чисел это кажется безумием
Но тем не менее, в порядке безумия:

В первом варианте от maxal имеем:
x = -19578556686240310295378317903565
y = 101658411567714319887
z = 418962851513108789978912616277180591709694

Берется произвольный y = 101658411567714319887, возводится в квадрат, прибавляется 1,
здесь y = 3 * 110066147 * 307870658807
Факторизуется результат:
y² + 1 = 2 * 5 * 17 * 37 * 73 * 349 * 130369 * 212669 * 2325997176536213467129
Дальше перебираем все возможные комбинации из этих делителей, например:
x = 2 * 5 * 2325997176536213467129
x = 5 * 17 * 73 * 2325997176536213467129
x = 5 * 37 * 349 * 130369 * 2325997176536213467129
В последнем случае мы получим тот самый x

Здесь есть два момента:
1. Выбор y - у меня нет никаких идей, кроме одной - нечетный игрек кратен трем
2. Факторизация 40-разрядных чисел - это такое себе, оно конечно реально, но процессор обречен на долгое нагревание окружающей среды

[juna]

mathpath
Не думаю, что этот перебор сильно поможет продвинуться в поиске других решений. Это же олимпиадная задача, наверное должна быть какая-то красивая редукция.

Можно еще уравнение рассматривать как кубическое. Один корень будет целым $x_1$, два других сопряженные (иррациональные или комплексные) $x_2, x_3$ с одинаковой целой частью, причем

$$-(1+y^2)=x_1\cdot x_2\cdot x_3 = x_1 (x_1^2+x_1-9yz)$$

Для пары $y_1, y_2$ будем иметь:

$$x_2'\cdot x_3'=(\alpha+\sqrt{\beta})(\alpha-\sqrt{\beta}) =\alpha^2-\beta= x_1^2+x_1-9y_1z$$

$$x_2''\cdot x_3''=(\alpha+i\sqrt{\gamma})(\alpha-i\sqrt{\gamma}) =\alpha^2+\gamma= x_1^2+x_1-9y_2z$$

Ну и, конечно,

$$y_1\cdot y_2=1+x_1^2+x_1^3$$

$$y_1+y_2=9x_1z$$

[scwec]

Вот два компактных решения с целыми $x,y$ и полуцелым $z$
$x = 13, y = 1578, z = 27/2$
$x = -81365, y = 20624682, z = 15/2$
Без прямого перебора с использованием средств PARI/GP. для эллиптических кривых.

[vicvolf]

scwec в сообщении #1635822 писал(а):

Вот два компактных решения с целыми $x,y$ и полуцелым $z$
$x = 13, y = 1578, z = 27/2$
$x = -81365, y = 20624682, z = 15/2$
Без прямого перебора с использованием средств PARI/GP. для эллиптических кривых.

Я писал об этом в начале темы.

vicvolf в сообщении #1632713 писал(а):

При различных целых значениях $z$ мы получаем эллиптическую кривую над кольцом целых чисел. Характеристика кольца целых чисел равна $0$, поэтому путем преобразования координат наша эллиптическая кривая приводится к канонической форме $y^2=x^3+ax+b$, т.е. к нормальной форме Вейрштрасса.

Но использовать это свойство для нахождения целых решений не представляется возможным. Поэтому для решения задачи требуется перебор, что снижает ее ценность.