Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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$


$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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.