Case specific perfect square test: $\sqrt{x^2 + 8a}$

Question

Let's say I have a function: $f(x) = \sqrt{x^2+8a}$,

Constraints: $a,x \in \mathbb{N}$, $a$ mod 2 = 1.

What would be the most efficient algorithm to find every natural $x$, so that $f(x) \in \mathbb{N}$?

$a$ is arbitrarily large, thus evaluating $f(x)$ for all $x$ is too computationally expensive. Is it possible to formulate a case specific test, to check that $x^2 + 8a$ is a perfect square?

Answer 1

Set $y=f(x)$

You have $y^2=x^2+8a$ whence $y^2-x^2=(y+x)(y-x)=8a$

Now $y+x$ and $y-x$ differ by $2x$ hence have the same parity, and at least one of them is even ...

I will leave you to work out the consequences of this.

Suppose $a$ (given as odd) is factored as $pq$. Working through leads to the identities $(p+2q)^2=(p-2q)^2+8a$ and/or $(2p+q)^2=(2p-q)^2+8a$

Answer 2

If $x^2+8a=y^2$, then $$8a=y^2-x^2=(y+x)(y-x), $$ so looking for the factorizations of $8a$ might help. In fact, as $8a$ is a multiple of $8$, at least one of $y\pm x$ must be a multiple of $4$, but that means the other factor is also even. Thus find all positive factors $d$ of $2a$, and then $x=|d-\frac{2a}{d}|$ is a non-negative integer solution; indeed $$\begin{align}\left|d-\frac{2a}{d}\right|^2+8a&=d^2-2\cdot d\cdot \frac{2a}{d}+\left(\frac{2a}d\right)^2+8a\\&=d^2+2\cdot d\cdot \frac{2a}{d}+\left(\frac{2a}d\right)^2\\&=\left(d+\frac{2a}d\right)^2.\end{align}$$