2014 dxdy logo

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

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




 
 Квадратный трехчлен, уравнения в целых числах
Сообщение20.10.2006, 08:50 
Всем доброго дня!

У меня следующий вопрос, существует ли формула (алгоритм) поиска такого значения $ x $, при котором

$\sqrt {x^2+bx+c} = y$,

где $y$ - число целое.

Добавлено спустя 3 минуты 33 секунды:

забыл сказать, $x,b,c$ - целые положительные .

 
 
 
 
Сообщение20.10.2006, 09:01 
Аватара пользователя
Насколько я понял, даны целые b,c и надо найти целые решения уравнения $x^2+bx+c=y^2$. Делаем замену y=x-t, получаем $(b+2t)x+c-t^2=0$, откуда 2t+b делит $t^2-c$ либо равно 0. В первом случае 2t+b делит также $4(t^2-c)-(4t^2-b^2)=b^2-4c$. Если $b^2-4c\ne0$, то это конечное число возможностей для t и x. Иначе выделяется полный квадрат и тоже нет проблем.

 
 
 
 
Сообщение20.10.2006, 09:46 
Простите мне мою настойчивость и тупость..
Рассмотрим пример, дан трехчлен $x^2+20x+5$, нужно определить, при каком x значение трехчлена равно квадрату какого-либо числа.

Делаем указанную подстановку, получаем: $x=\frac{t^2-5}{20+2t} $, также зная что $D=b^2-4c=380$ делится на 2t+20...

Каким образом найти t? Отталкиваться от делителей числа 380?

 
 
 
 
Сообщение20.10.2006, 10:02 
Аватара пользователя
А что? Из вида x видно, что t нечет. Далее, 190 делится на t+10. Можно отпробовать t=9. Это дает x=2.

 
 
 
 
Сообщение20.10.2006, 10:07 
RIP, спасибо за ответы.
Все верно, только мы опять приходим к перебору..

 
 
 
 
Сообщение20.10.2006, 10:08 
Аватара пользователя
А что Вас смущает? Вас пугает большой перебор всех делителей?

 
 
 
 
Сообщение20.10.2006, 10:10 
Не то что перебор.. Их поиск)

 
 
 
 
Сообщение20.10.2006, 10:23 
Аватара пользователя
Могу предложить альтернативный вариант, учитывающий, что x,b,c>0. Тогда $(x+a_1)^2<x^2+bx+c<(x+a_2)^2$ для некоторых неотрицат. $a_1,a_2$ (например, $a_1=0,a_2=b+c$). Это дает для y конечное число вариантов $y=x+a, a_1<a<a_2$. Чем ближе друг к другу подобрать $a_1,a_2$, тем меньше перебор.

 
 
 
 
Сообщение20.10.2006, 10:48 
Спасибо, буду переваривать..
А как Вы думаете, Х всегда единственно? Т.е. существует только одно значение Х при котором трехчлен равен квадрату целого?

 
 
 
 
Сообщение20.10.2006, 11:03 
Аватара пользователя
Отнюдь. Рассмотрим $x^2+bx+1$, b нечетное, причем b-2 имеет огромное кол-во делителей. Возвращаясь к первому способу, $x=\frac{t^2-1}{2t+b}$. Чтобы x было целым, необходимо и достаточно, чтобы 2t+b делило $b^2-4=(b-2)(b+2)$. Последнее имеет тучу делителей > b, каждый из них дает значение для t и для x.

 
 
 
 
Сообщение21.10.2006, 16:02 
RIP, огромное спасибо!

Да, действительно, рассматривая наш пример, $x^2+20x+5$, решения получаем как при x=2 (y=7), так и при х=38 (y=47).
Подскажите, пожалуйста, а можно ли, найдя одно из решений, найти остальные? Просто кажется, что должна быть какая-то взаимосвязь между корнями, но найти ее никак не получается...

 
 
 
 
Сообщение21.10.2006, 17:00 
Nikotin писал(а):
Не то что перебор.. Их поиск)

Разложите на простые числа. Делители- это всевозможные произведения этих простых чисел в степенях не превышающих степеней в разложении числа.

Например \[
380 = 2^2  \cdot 5 \cdot 19
\]

Тогда всевозможные делители 380 имеют вид \[
q = 2^k  \cdot 5^l  \cdot 19^m ,\;k \in \overline {0,2} \quad ,\;l,m \in \overline {0,1} 
\]

 
 
 
 
Сообщение21.10.2006, 17:47 
Если $a$ - не есть точный квадрат, то это вообще-то должно сводиться к уравнениям Пелля, а там бесконечно много решений обычно. Статейка по уравнениям Пелля есть в журнале Квант за 2002 год кажется - kvant.mccme.ru.

 
 
 
 
Сообщение21.10.2006, 18:04 
$ писал(а):
Nikotin писал(а):
Не то что перебор.. Их поиск)

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


К сожалению факторизация этого числа невозможна, т.к. на практике (в решаемой мной задаче) оно ОЧЕНЬ велико.. А вообще, интересный конечно поворот - чтобы найти требуемый квадрат, нужно прибегнуть к факторизации.

Вот если бы было не $2t+b$ , а $2^t+b$ :) , то она бы решалась прямым перебором очень быстро.

Добавлено спустя 1 минуту 50 секунд:

Vadimjr писал(а):
Если $a$ - не есть точный квадрат, то это вообще-то должно сводиться к уравнениям Пелля, а там бесконечно много решений обычно. Статейка по уравнениям Пелля есть в журнале Квант за 2002 год кажется - kvant.mccme.ru.


Спасибо, почитаю.

 
 
 
 
Сообщение24.10.2006, 17:04 
К уравнениям Пелля свести не получается, т.к. коэф-т при $y$ - полный квадрат ($1^2$).

Появился еще один вариант решения:
$
x^2+20x+5=y^2 \\
x^2+20x+100+5-100=y^2\\
(x+10)^2-y^2=95\\
z=x+10\\
z^2-y^2=95\\
(z-y)(z+y)=95\\

\left\{ \begin{array}{l} 
z+y = 95,\\ 
z-y = 1, 
\end{array} \right\\
(x,y)=(38,47)\\

\left\{ \begin{array}{l} 
z+y = 19,\\ 
z-y = 5, 
\end{array} \right\\
(x,y)=(2,7)
$

Но, как видно, он тоже предполагает разложение на множители.
Замкнутый круг? Больше нет вариантов решения?

 
 
 [ Сообщений: 15 ] 


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