Диофантово уравнение 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$, т.е. к нормальной форме Вейрштрасса.

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

[scwec]

Исходное уравнение определяет семейство эллиптических кривых с параметром z.
Уравнение фактически записано в форме Вейерштрасса, нужна только замена $X=-x$
Тогда $y^2+9Xyz=X^3-X^2-1$ и инициализационный вектор $[a_1, a_2, a_3, a_4, a_6]=[9z, -1, 0, 0, -1]$,
Рациональные точки на этих кривых при целых $z$ записываются как $X=\dfrac{m}{q^2}, y=\dfrac{n}{q^3}$. где $m,n,q$
целые числа и $\gcd(m,q)=\gcd(n,q)=1$.
Таким образом $n^2+9mnqz=m^3-q^2{m^2}-q^6$
Для $q=1$ два решения его здесь приведены maxal
Приведу решения с $q=2,3,5$ сразу для переменных $x,y,z$ (найдены с помощью Pari/GP без прямого перебора $m,n$)
$x=-\dfrac{518465}{2^2},y=\dfrac{225652149}{2^3},z=42$
$x=\dfrac{5}{3^2},y=\dfrac{1}{3^3},z=8$
$x=\dfrac{1}{5^2}, y=\dfrac{3}{5^3},z=116$
Известны также решения с целыми $z$ для $q=6,9,12,20,30,179,267$
Возможно, представит интерес нахождение решений с другими $q$
Сообщение подготовлено в апреле 2024 г.

[dmd]

Просто некоторые наблюдения. В иксах известных решений есть огромное простое. Зная только его и решая соответствующие сравнения, можно получить сами решения.

Пусть $x=a p$, где $p$ наибольший простой делитель $x$.

Тогда $y$ находим из сравнения $1+y^2\equiv 0 \pmod p$.

Затем решим сравнение $1+x'^2+x'^3\equiv 0 \pmod y$,

найдем $a'$ решая $a' p\equiv x' \pmod y$,

и тогда $a=a'$ если $x$ положительный, или $a=a'-y$ если $x$ отрицательный.

(код для проверки)

p= 2325997176536213467129;

\\  p= 1611312908701618227721096799976372690229;

  Y= lift(polrootsmod(1 + 'y^2, p)~);
  
  for(i=1, #Y,

   y= Y[i]; ch= Mod(1,3);

   if(y%6==3, if(issquarefree(y),

    YM= factorint(y/3);

    for(j=1, #YM~,

     py= YM[j,1];

     X= polrootsmod(1 + 'x^2 + 'x^3, py)~;

     if(#X,
      ch= chinese(ch, X[1])
     )
    )

   ));

   if(ch != Mod(1,3),

    Xo= lift(polrootsmod(p*'x - lift(ch), y)~);

    x= Xo[1]*p; z= (1+x^2+x^3+y^2)/(9*x*y);

    if(z==floor(z),
     print("\n("x", "y", "z")    "p"\n");
    );

    x= (Xo[1]-y)*p; z= (1+x^2+x^3+y^2)/(9*x*y);

    if(z==floor(z),
     print("\n("x", "y", "z")    "p"\n");
    )

   )
  )

[dmd]

$(x,y,z)$=(-707898957401771913757226, 6377985188886147, 8730045949720501300467109875755)