# Show the number of solutions

Show that the number of solutions of $x^2+y^2=m$, where $m=2^{\alpha}r$ and $r$ is odd, is given by $U(m)=4\sum_{u|r}(-1)^{\frac{u-1}{2}}=4\gamma(m)$, where $\gamma(m)$ denotes the number of positive divisors of $m$

-

If $X^2+Y^2=p^{n+2k}$ where $X,Y,n>0,k\ge 0$ are integers with $(X,Y)=p^k$ and $p$ is an odd prime, let $\frac X x=\frac Y y=p^k$, so, $x^2\equiv -y^2\pmod {p^n}\implies z^2\equiv-1\pmod {p^n}$ where $z=\frac x y$

We know $p^n$ has primitive roots, so taking discrete logarithm w.r.t. one of the primitive roots $r$ we get, $2 ind_rz\equiv \frac{\phi(p^n)}2\pmod{\phi(p^n)}$

or $2 ind_r z\equiv \frac{p^{n-1}(p-1)}2\pmod{p^{n-1}(p-1)}$

which is a linear congruence equation (compare with $ax\equiv b\pmod c$) which is solvable if $(p^{n-1}(p-1),2)\mid \frac{p^{n-1}(p-1)}2$ i.e, $2\mid \frac{p-1}2\implies p\equiv 1\pmod 4$ to admit any solution.

If $p\equiv 1\pmod 4$, there will be $(p^{n-1}(p-1),2)=2$ solutions.

Clearly, if $z>0$ is one solution, so is $-z$ .

$z=\frac x y$ and $\frac {-x} {-y}$ and $-z=\frac {-x} y$ and $\frac x {-y}$

So, there will be exactly one positive integral solution to $X^2+Y^2=p^{n+2k}$ if $p\equiv 1\pmod 4.$

If $p\equiv -1\pmod 4,$ then $p^{2m}$ can be expressed uniquely in term of non-negative numbers as $(p^m)^2+0^2$

If $p=2,X^2+Y^2=2^{h+2k},$

If $(X,Y)=2^k$, like earlier we can reach to $x^2+y^2=2^h$ where $(x,y)=1$

if $h=0, x^2+y^2=1$

else

$x,y$ must be odd as both must have the same parity as $h\ge 1$

But $(2a+1)^2+(2b+1)^2=8\frac{a(a+1)+b(b+1)}{2}+2\equiv 2\pmod 8\implies h=1$

So, $x^2+y^2=2^h$ reduces to $x^2+y^2=2$ which has exactly one solution $(1,1)$

So, $X^2+Y^2=2^{h+2k}$ has exactly one solution.

Now if $X^2+Y^2=m_1$ and $X^2+Y^2=m_2$ have $t_1,t_2$ solutions respectively, in non-negative integers where $(m_1,m_2)=1$, then $X^2+Y^2=t_1+t_2$ solutions in non-negative integers the reason being $(a^2+b^2)(c^2+d^2)=(ac\pm bd)^2+(ad∓bc)^2$

If $m=2^a\prod p_i^{b_i}\prod q_i^{c_i},$ where $p_i\equiv 1\pmod 4$ and $q_i\equiv -1\pmod 4$

$x^2+y^2=m$ will have no solution if at least one of $c_i$ is odd

and it will have $(1+$ the number of unique $p_i$) solution in non-negative integers.

Now, if $(a,b)$ is a solution to $X^2+y^2=m,$ so are $(a,-b),(-a,-b),(-a,b)$

So there will be $4(1+$ the number of unique $p_i$) solution in integers in the later case.

-
where are you using the fact that $m=2^{\alpha}r$? –  Elmo goya Oct 20 '12 at 0:14
@CamiloAndrésMolano, could you please look into the edited the answer. –  lab bhattacharjee Oct 20 '12 at 3:50