# Number theory counting sums of squares modulus

This is an extra question from an old examination paper:

VI. Let $n>1$ in $\mathbf{Z}$ and let $r(n) = \#\{(a,b)\in \mathbf{Z}^{2};n=a^{2}+b^{2}\}$ Let also $n=n'n''n'''$ where $n',n'',n''' \in \mathbf{N}$ and

$p|n' \Longrightarrow p\equiv 1\mod 4 ; p|n'' \Longrightarrow p=2 ; p|n''' \Longrightarrow p\equiv 3 \mod 4$

for $p\in \mathbf{N}$ prime.

i) Show that if $n'''$ is not a square, then $r(n)=0$.

ii) Show that if $n'''$ is a square and $n' = 1$, then $r(n)=4$

iii) Show that if $n'''$ is a square and $1<n'=p_{1}^{e_{1}}\ddots p_{k}^{e_{k}}$ where $p_{1},...,p_{k}$ are different primes in $\mathbf{N}$ and $e_{1},...,e_{k} \in \mathbf{N}$, then it holds that $r(n)=r(n')=4(e_{1}+1)\ddots (e_{k}+1)$

I am completely dumbstruck and can't see how to begin (and neither did an older student who took this exam and whom I asked for hints). Help is greatly appreciated.

-
A proof of this quite standard result can be found in most introductions to Number Theory. The full details take a while! There is the least work to do if one knows about Gaussian integers. – André Nicolas Nov 9 '11 at 18:34
This is all built on factorizations on Gaussian integers: $\mathbb{Z}[i]$. en.wikipedia.org/wiki/Gaussian_integer It has do with things like: only primes congruent to 3 mod 4 can be represented at the sum of squares. In part ii) the 4 shows up because there are 4 units in $\mathbb{Z}[i]$. Look at some of the links which appear next to your question and explore. You'll probably collect what you need to prove these things. – Bill Cook Nov 9 '11 at 18:37
André Nicolas, I don't want to sound rude, but can you give me an explicit title in which this is explained for undergraduates? That would be a great help :) :) Bill Cook, thanks for the hint :) – PumaDAce Nov 9 '11 at 18:37
@PumaDAce: For the Gaussian integer approach, "Elementary Number Theory and its Applications," Kenneth Rosen, in Edition 5 at least, not in Edition 3. – André Nicolas Nov 9 '11 at 18:58
Thank you. :) :) – PumaDAce Nov 9 '11 at 19:01

The above theorem can be summarized by defining $r_0(n)=\frac{r(n)}4$, and then showing:

1. $r_0(n)$ is multiplicative - that is, if $m,n$ are relatively prime, then $r_0(nm)=r_0(n)r_0(m)$.
2. If $p\equiv 3\pmod 4$ is prime, then $r_0(p^k)=0$ if $k$ odd, and $r_0(p^k)=1$ if $k$ even.
3. $r_0(2^k)=1$ for all k
4. $r_0(p^k)=k+1$ if $p\equiv 1\pmod 4$ is prime

(1) is shown using unique factorization in $\mathbb Z[i]$. (2) is essentially due to the fact that $-1$ is not a square mod $p$ if $p\equiv 3\pmod 4$. (3) You can essentially brute force. (4) Again uses unique factorization in $\mathbb Z[i]$.

-

Outline:

Step 1: Prove Fermats Theorem which states that every prime $p\equiv 1 \pmod{4}$ can be written as the sum of two squares uniquely up to order and sign. I would hope that this was already done in your class, since its proof will require by far the most work here.

Step 2: Show that $\frac{1}{4}r(n)$ is a multiplicative function. This follows since $\mathbb{Z}[i]$ is a unique factorization domain, and that the norm is multiplicative.

From here, you can conclude both $(ii)$ and $(iii)$. (i) then follows from considering modulo $4$. (and using multiplicativity)

-
Thank you Eric Naslund. :) – PumaDAce Nov 9 '11 at 18:41
@AndréNicolas: Oo yes that is correct. I was using the multiplicative part when I was thinking about it. – Eric Naslund Nov 9 '11 at 20:10