Квадратный трехчлен, уравнения в целых числах

[Nikotin]

Всем доброго дня!

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

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

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

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

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

[RIP]

Насколько я понял, даны целые 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. Иначе выделяется полный квадрат и тоже нет проблем.

[Nikotin]

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

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

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

[RIP]

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

[Nikotin]

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

[RIP]

А что Вас смущает? Вас пугает большой перебор всех делителей?

[Nikotin]

Не то что перебор.. Их поиск)

[RIP]

Могу предложить альтернативный вариант, учитывающий, что 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$, тем меньше перебор.

[Nikotin]

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

[RIP]

Отнюдь. Рассмотрим $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.

[Nikotin]

RIP, огромное спасибо!

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

[$]

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} \]

[Vadimjr]

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

[Nikotin]

$ писал(а):

Nikotin писал(а):

Не то что перебор.. Их поиск)

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

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

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

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

Vadimjr писал(а):

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

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

[Nikotin]

К уравнениям Пелля свести не получается, т.к. коэф-т при $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) $

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