Integer solutions to $x^2+1=ay$

Question

I'd like to know if there is a formula for finding integer solutions to equations of the form $$x^{2}+1=ay$$ where $a\in\mathbb{Z}$, and $x$ and $y$ are unknowns.

Answer 1

This is equvalent to solving $$ x^2 \equiv -1 \pmod a $$ That is a well-known problem; look up Quadratic Residues on https://en.wikipedia.org/wiki/Quadratic_residue for example. The punch line is that if $a$ is prime or if you can factor $a$, the problem is fairly easy; if $a$ is composite and so large that you cannot factor it, the problem is very hard.

Answer 2

Of course you need $a \ne 0$. You need $x$ to be a square root of $-1 \mod a$, and then $y = (x^2+1)/a$. For $-1$ to have a square root $\mod a$, you need $a$ to be either odd or $2$ times an odd number, and to have no prime factors $\equiv 3 \mod 4$. Then if $a$ has $k$ distinct odd prime factors, there are $2^k$ possible values for $x \mod a$.