решить уравнение в целых числах

[dmd]

Есть ли способ решить в наименьших целых $D*x+1=y^2$
только не перебором.

[AlexDem]

Имеется ввиду $Dx + 1 = y^2$, где D - константа? Тогда заменяем $y^2 = \sqrt x$...

Прошу прощения, поторопился

[dmd]

это диофантово уравнение, такая замена невозможна

[worm2]

Непонятно, что значит "в наименьших целых".
Пожалуйста, вот Вам решение: (x=0, y=-1). Будет ли оно считаться "наименьшим"? При натуральных D можно привести пример с меньшим у, но большим x. При D = 1 --- решение с меньшим x, но большим y: (x=-1, y=0). А при отрицательных D для любого заданного решения можно указать другое, в котором и x, и y будут меньше, чем в заданном.

[Руст]

Разложите D на простые множители $D=\prod_{i=1}^k p_i^{k_i}$. Это дает, что y находится из сравнений $y=\pm 1(mod \ p_i^{k_i})$. Наименьшее положительное решение есть y=1. В каждом отрезке длины D имеется ровно 2^k решений, полученных из указанных сравнений. Алгоритм решения заключается в нахождении k решений
$y_i=-1(mod p_i^{k_i}, y_i=1(mod\frac{D}{p_i^{k_i}})$ и для каждого из 2^k наборов вычисляя соответствующие произведения из yi (для пустого произведения 1) получаем 2^k решений, остальные получаются из них добавлением числа кратного D, а х есть просто частное от (y^2-1)/D, для соответствующем образом взятого у.

[dmd]

Руст писал(а):

Разложите D на простые множители..

Как? Это все тот же перебор. Посмотрел, как Математика такие уравнения решает - насколько понял - именно перебором.

Извиняюсь, что сразу не уточнил - нужно решение наименьшее целое, кроме тривиальных {0,1}, и положительное. D тоже целое и положительное.

[AlexDem]

Если дело касается алгоритма, то может все же попробовать мой ошибочный вариант?.. Пусть $Dx + 1$ задает прямую, нужно выяснить, через какие целые числа (корень из которых тоже целый) она проходит. Вычисляем квадрат от Counter=2, по нему получаем x, смотрим, на сколько $Dx + 1$ отличается от целого. Не получится ли как-нибудь использовать эту дельту, чтобы перешагнуть через некоторые значения Counter, не вычисляя?

[Руст]

dmd писал(а):

Руст писал(а):

Разложите D на простые множители..

Как? Это все тот же перебор. Посмотрел, как Математика такие уравнения решает - насколько понял - именно перебором.

Извиняюсь, что сразу не уточнил - нужно решение наименьшее целое, кроме тривиальных {0,1}, и положительное. D тоже целое и положительное.

Это не перебор, а осознанное нахождение всех решений. Если D имеет только один простой делитель, то сразу получаем единственное решение для у из интервала 1<y<D это D-1. Количество операций порядка 2^k ln(D) и это гораздо меньше D, как в случае перебора.

[worm2]

dmd писал(а):

Как? Это все тот же перебор.

Боюсь, что Ваша задача по любому эквивалентна факторизации (разложению на множители) D. Т.е. любой алгоритм её решения влечёт за собой либо доказательство, что D --- простое, либо нахождение одного из его нетривиальных делителей, если оно составное.
Пусть у нас D > 4, а (x, y) --- минимальное решение. Можно показать, что если D --- простое, то y=D-1, а если D --- составное, то y<D-1. Тогда либо D > НОД(y+1,D) > 1, либо D > НОД(y-1,D) > 1. Один из этих НОДов является нетривиальным делителем D.
Таким образом, если Вы сможете решить Вашу задачу без перебора, то сможете найти и решение задачи факторизации без использования перебора. А тогда --- озолотитесь.

[maxal]

worm2 писал(а):

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

А почему вы считаете, что факторизовать можно только перебором? Есть много алгоритмов факторизации с субэкспоненциальным временем работы.

[dmd]

worm2 писал(а):

Боюсь, что Ваша задача по любому эквивалентна факторизации

От задачи факторизации я к ней и пришел.

[maxal]

Это мода теперь такая: переформулировать задачу факторизации, а затем просить решить на форумах, ни в коем случае не упоминая исходную задачу. Вдруг кто-нибудь решит и не догадается о ее связи с факторизацией
Видел такое неоднократно.

[dmd]

maxal писал(а):

Это мода теперь такая: переформулировать задачу факторизации, а затем просить решить на форумах, ни в коем случае не упоминая исходную задачу. Вдруг кто-нибудь решит и не догадается о ее связи с факторизацией
Видел такое неоднократно.

Зря Вы так озвучили, я ничего не переформулировал, а именно пытался решить, в результате пришел к такому диофантовому уравнению.

[maxal]

dmd писал(а):

maxal писал(а):

Это мода теперь такая: переформулировать задачу факторизации, а затем просить решить на форумах, ни в коем случае не упоминая исходную задачу. Вдруг кто-нибудь решит и не догадается о ее связи с факторизацией
Видел такое неоднократно.

Зря Вы так озвучили, я ничего не переформулировал, а именно пытался решить, в результате пришел к такому диофантовому уравнению.

О чем я и говорил. Вы свели задачу факторизации к некоторому диофантову уравнению. Как Вам уже здесь показали, решение этого уравнения равносильно решению исходной задачи. Если это не переформулировка, то что?
Откуда у Вас взялась уверенность, что решить полученное уравнение будет проще чем факторизовать?

[dmd]

Вы, конечно, во всем правы, увы мне:(

Вот это уравнение:
$24rx + 1 = y^2$, где $r$ - произведение искомых простых.
Если ${x_m,y_m}$ - минимальное решение этого уравнения, то
$i=IntegerPart[(y_m-1)/4]$, либо $i=IntegerPart[(y_m-1)/4]\pm 1$ гарантировано содержит один из искомых простых множителей: $GCD[i,r]$.