number theory - Greatest common divisor expression

How can we show that for a fixed positive integer $a$

$a^2+\left[\text{GCD}(a,b)\right]^2\equiv0\mod b\,\text{GCD}(a,b)$

has a positive and even number of solutions $b$ (also positive integers)?

Answer

$b=1$ is always a solution, as it's easily verified, so the number of solutions is positive.

Suppose now that $b$ is a solution. We'll find another one. Let be:

• $d=\gcd(a,b)$


• $b_0=b/d$


• $a_0=a/d$


• $c_0=(a_0^2+1)/b_0$


• $c=c_0d$

First, we will show that $c_0$ is an integer:

$$b_0d^2|(a_0^2d^2+d^2)$$
that is,
$$b_0|(a_0^2+1)$$
Now, we will show that $c$ is a solution. Since $a_0^2+1$ and $a_0$ are coprime, so are $c_0$ and $a$. Then, $\gcd(a,c)=d$. Moreover,
$$cd=c_0d^2|(a_0^2+1)d^2=a^2+d^2$$
so it's a solution, indeed.

Now, if we do the same thing with $c$, clearly we obtain $b$. Since $b_0c_0=a_0^2+1$, that is not a perfect square, $b_0$ and $c_0$ are different; hence, so are $b$ and $c$. This proves that the number of solutions is even.