5x2+4=y2 в целых числах

[lorents]

Добрый день.

Нужен алгоритм решения уравнения вида $5(xN)^2 \pm 4 = y^2$ в целых числах.

$N$ - простое или составное число, задано на входе.

Существует ли алгоритм с полиномиальным временем выполнения?

[maxal]

Это уравнение Пелля, которое классически записывается в форме:

$$y^2 - m\cdot x^2 = \pm 4.$$

где в данном случае $m=5N^2$.

Как решать такие уравнения описано много где. Например:
Cohen H. — Number Theory, Volume 1: Tools and Diophantine Equations

Для конкретных значений $m$ можно также воспользоваться солвером:
http://www.alpertron.com.ar/QUAD.HTM

-- Sun Feb 21, 2010 11:15:09 --

Кстати, решениями данного конкретного уравнения относительно $x$ являются целые числа вида $\frac{F_k}{N}$, где $F_k$ - числа Фибоначчи. Более того, все подходящие $k$ являются кратными некоторого числа, зависящего от $N$.