2014 dxdy logo

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

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



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 решить уравнение в целых числах
Сообщение16.11.2006, 16:13 


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

 Профиль  
                  
 
 
Сообщение16.11.2006, 16:30 
Заблокирован
Аватара пользователя


07/08/06

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

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

 Профиль  
                  
 
 
Сообщение16.11.2006, 16:41 


16/08/05
715
это диофантово уравнение, такая замена невозможна

 Профиль  
                  
 
 
Сообщение16.11.2006, 17:46 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение16.11.2006, 18:02 
Заслуженный участник


09/02/06
4328
Москва
Разложите 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 


16/08/05
715
Руст писал(а):
Разложите D на простые множители..


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

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

 Профиль  
                  
 
 
Сообщение16.11.2006, 19:10 
Заблокирован
Аватара пользователя


07/08/06

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

 Профиль  
                  
 
 
Сообщение16.11.2006, 19:37 
Заслуженный участник


09/02/06
4328
Москва
dmd писал(а):
Руст писал(а):
Разложите D на простые множители..


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

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

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

 Профиль  
                  
 
 
Сообщение16.11.2006, 20:04 
Заслуженный участник
Аватара пользователя


01/08/06
2178
Уфа
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 
Модератор
Аватара пользователя


11/01/06
5215
worm2 писал(а):
Таким образом, если Вы сможете решить Вашу задачу без перебора, то сможете найти и решение задачи факторизации без использования перебора. А тогда --- озолотитесь.

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

 Профиль  
                  
 
 
Сообщение16.11.2006, 21:51 


16/08/05
715
worm2 писал(а):
Боюсь, что Ваша задача по любому эквивалентна факторизации


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

 Профиль  
                  
 
 
Сообщение16.11.2006, 21:55 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение16.11.2006, 22:06 


16/08/05
715
maxal писал(а):
Это мода теперь такая: переформулировать задачу факторизации, а затем просить решить на форумах, ни в коем случае не упоминая исходную задачу. Вдруг кто-нибудь решит и не догадается о ее связи с факторизацией :lol:
Видел такое неоднократно.


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

 Профиль  
                  
 
 
Сообщение16.11.2006, 22:09 
Модератор
Аватара пользователя


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


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

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

 Профиль  
                  
 
 
Сообщение17.11.2006, 06:21 


16/08/05
715
Вы, конечно, во всем правы, увы мне:(

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