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

[Vadim32]

maxal
Это уже будут три буквы. Первая буква - решение существует, вторая буква - оно занимает столько-то бит, станет известно в каком масштабе, какой двоичной разрядности нужно вести поиск. И третья буква - это уже ответ, после которого становится бессмысленным поиск решения. Я разрабатываю метод перебора. Для этого нужно составить различные программы работы с числами представленными через разложение на простые множители. Идея перебора состоит в том, чтобы найти подходящее основание DENOM которое будет использовано в качестве базового знаменателя. Поиск пар {x,y} идёт по квадратам. Сторона квадрата {x,y} равна DЕNOM. Рассматриваются остатки от деления чисел x и y на DENOM. Для всех пар x,y которые дают остатки от деления на DЕNOM можно заранее исключить пары, которые не могут быть решениями. Чем больше доля таких исключённых из поиска пар, тем эффективнее найдено основание DENOM. Например, для DENOM=124740 коэффициент сокращения поиска равен 629. То есть, вместо (124740*124740) пар, количество необходимое подвергать проверке 24739344 пар, что в 629 раз меньше. По мере увеличения основания DENOM наблюдается рост коэффициента сокращения. В качестве критерия исключения пары из поиска являются соотношения, связанные с разложением на множители чисел x и y, которые входят в состав DENOM. Если выражение 9xy имеет в составе некоторые множители входящие в состав DENOM, то выражение 1+x^2+x^3+y^2 обязано делиться без остатка на этот множитель, в противном случае пара исключается из поиска. Если рассматривать отрицательные x, то выражение 1+x^2-x^3+y^2 также должно делиться без остатка. Для того чтобы перейти к большим значениями DENOM, нужно исключить затратную операцию разложения на множители, которая осуществляется при переборе x от 0 до DENOM. Для этого числа {x,y} нужно представлять в виде разложение на простые множители и итерацию производить в этом представлении на простые множители, а не в двоичном. Если нашлась пара, которая прошла проверку на исключение, то её нужно проверить на делимость (1+x^2+x^3+y^2)/(9xy) на множестве других квадратов, путём добавления n*DENOM. Вот такой был мой план. Но если появится ответ или подсказка, он вероятно изменится или просто отложится без надобности.

[mathpath]

Vadim32 в сообщении #1633468 писал(а):

maxal
Это уже будут три буквы. Первая буква - решение существует, вторая буква - оно занимает столько-то бит, станет известно в каком масштабе, какой двоичной разрядности нужно вести поиск. И третья буква - это уже ответ, после которого становится бессмысленным поиск решения. Я разрабатываю метод перебора. Для этого нужно составить различные программы работы с числами представленными через разложение на простые множители.

Раскладывать на простые множители ?
Да замучитесь пыль глотать
Это же олимпиадная задача, которая в принципе не предполагает разложение на множители как алгоритм решения

[EUgeneUS]

Допустимые остатки $x$ по модулю $81$: $4, 13, 67$.

[Dmitriy40]

Мне тоже более интересна буковка $z$ ...
Ну и/или порядок величины решения, количество цифр в любой букве. Хоть бы убедиться что не пропустил решения при переборе. И что их вообще можно найти теми способами что искал.

[maxal]

Подавляющее большинство проголосовало за букву - вот одна из:

x = -19578556686240310295378317903565
y = 101658411567714319887
z = 418962851513108789978912616277180591709694

[Dmitriy40]

Я в пролёте.
Хорошая задача, не на перебор. Или не на настолько тупой прямой как у меня.

[Ivan 09]

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

Подавляющее большинство проголосовало за букву - вот одна из:

Мне удалось(если не ошибся) показать, что всегда $x$-четно, $y$-нечетно, $z$-нечетно . Я правильно понимаю, что отсюда вывод, что в Вашем сообщении из тройки чисел только $y$ та самая буква. Или я не правильно понял?

[EUgeneUS]

Ivan 09 в сообщении #1633497 писал(а):

Мне удалось(если не ошибся) показать, что всегда $x$-четно, $y$-нечетно, $z$-четно

Тут ошибка.
$1 +x^2 + x^3$ - всегда нечетно
Если $y$ - четно, то левая часть нечетная, правая - четная. Противоречие.
Значит $y$ - нечетно. Тогда левая часть - четная. И $x,z$ не могут быть нечетными одновременно.
Но если $z$ - четно, $x$ вполне может быть нечетным.

-- 20.03.2024, 16:16 --

Dmitriy40
Не факт, что это минимальное решение.

[maxal]

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

Не факт, что это минимальное решение.

Кстати, да - вопрос о минимальном решении открыт. Но вполне может быть, что он гораздо сложнее получения какого-то решения

[mathpath]

Дааааа ...
Получается 94-разрядная сумма
НОД(x,y)=1
НОД(x,z)=1
НОД(y,z)=3
Все числа составные

[Утундрий]

(Оффтоп)

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

[Ivan 09]

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

Значит $y$ - нечетно. Тогда левая часть - четная. И $x,z$ не могут быть нечетными одновременно.

Четными одновременно они тоже быть не могут.
$1+8p^3+4p^2+4q^2-4q+1=36pt(2q-1)$
делим на два
получится $4p^3+2p^2+2q^2-2q+1=18pt(2q-1)$
левая часть всегда нечетная, правая всегда четная
Заменили $x=2p; z =2t ; y=2q-1$

[EUgeneUS]

Ivan 09 в сообщении #1633506 писал(а):

Четными одновременно они тоже быть не могут.

Нуок.
Значит, либо $x$ - чётное, а $z$ - нечётное, либо наоборот.

[maxal]

Утундрий в сообщении #1633502 писал(а):

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

Для произвольных крокодилов коэффициенты сделать очень маленькими не удастся.

[Ivan 09]

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

либо $x$ - чётное, а $z$ - нечётное, либо наоборот.

$(1+x^2+x^3)=(x-1)^3+4(x-1)^2+5(x-1)+3$
$(x-1)^3+4(x-1)^2+5(x-1)$ всегда чётное.

$x-1=t$

$t^3+4t^2+5t+3=9(t+1)zy$

$t^3+4t^2+5t+3=9tzy+9zy$

$t^3+4t^2+5t+3-9zy=9tzy$
$3-9yz$ Должно быть чётным. Значит $z$-нечётно.
Могли бы Вы проверить мои рассуждения?