When $\sqrt{(x+a)^2 -b}$ is an integer?

Question

While working on integer factorization problem, I came to this:

How to find for which values of $x$ the next equation is an integer? $$\sqrt{(x+a)^2 -b}$$

• $a,b$ are positive known integers

In order to find a solution to this question, should I test all the values of $x$? Or can I simplify it some how?

Answer 1

Let that integer be $y^2$ then $b=(x+a)^2-y^2=(x+a+y)(x+a-y)$. So, you only need to consider factorizations of $b=b_1b_2$ and the corresponding solutions of the system $$\begin{align}x+a+y&=b_1\\x+a-y&=b_2\end{align}$$

Example:

Take $a=0$, $b=3$. The factorizations of $b=3$ are $$\begin{align}1&\cdot3\\3&\cdot1\\(-1)&\cdot(-3)\\(-3)&\cdot(-1)\end{align}$$

The first system of equations to consider (the one for the first factorization) would be $$\begin{align}x+y&=1\\x-y&=3\end{align}$$ which has solutions $x=2$, $y=-1$.

The next system would be $$\begin{align}x+y&=3\\x-y&=1\end{align}$$ which has solutions $x=2$, $y=1$.

You can continue the rest of the cases.

Try $a=0$, $b=12$ for an example in which some factorizations give integer solutions and some others don't.

Answer 2

Hint: Write the equation as $$(x+a)^2-b=k^2$$ for some integer $k$, and then factor with SFFT.