2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3, 4  След.
 
 решить уравнение в целых числах
Сообщение16.11.2006, 16:13 
Есть ли способ решить в наименьших целых $D*x+1=y^2$
только не перебором.

 
 
 
 
Сообщение16.11.2006, 16:30 
Аватара пользователя
Имеется ввиду $Dx + 1 = y^2$, где D - константа? Тогда заменяем $y^2 = \sqrt x$...

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

 
 
 
 
Сообщение16.11.2006, 16:41 
это диофантово уравнение, такая замена невозможна

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

 
 
 
 
Сообщение16.11.2006, 18:02 
Разложите 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, для соответствующем образом взятого у.

 
 
 
 
Сообщение16.11.2006, 18:27 
Руст писал(а):
Разложите D на простые множители..


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

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

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

 
 
 
 
Сообщение16.11.2006, 19:37 
dmd писал(а):
Руст писал(а):
Разложите D на простые множители..


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

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

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

 
 
 
 
Сообщение16.11.2006, 20:04 
Аватара пользователя
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.
Таким образом, если Вы сможете решить Вашу задачу без перебора, то сможете найти и решение задачи факторизации без использования перебора. А тогда --- озолотитесь.

 
 
 
 
Сообщение16.11.2006, 21:14 
Аватара пользователя
worm2 писал(а):
Таким образом, если Вы сможете решить Вашу задачу без перебора, то сможете найти и решение задачи факторизации без использования перебора. А тогда --- озолотитесь.

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

 
 
 
 
Сообщение16.11.2006, 21:51 
worm2 писал(а):
Боюсь, что Ваша задача по любому эквивалентна факторизации


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

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

 
 
 
 
Сообщение16.11.2006, 22:06 
maxal писал(а):
Это мода теперь такая: переформулировать задачу факторизации, а затем просить решить на форумах, ни в коем случае не упоминая исходную задачу. Вдруг кто-нибудь решит и не догадается о ее связи с факторизацией :lol:
Видел такое неоднократно.


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

 
 
 
 
Сообщение16.11.2006, 22:09 
Аватара пользователя
dmd писал(а):
maxal писал(а):
Это мода теперь такая: переформулировать задачу факторизации, а затем просить решить на форумах, ни в коем случае не упоминая исходную задачу. Вдруг кто-нибудь решит и не догадается о ее связи с факторизацией :lol:
Видел такое неоднократно.


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

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

 
 
 
 
Сообщение17.11.2006, 06:21 
Вы, конечно, во всем правы, увы мне:(

Вот это уравнение:
$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]$.

 
 
 [ Сообщений: 48 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group