Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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]$. 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
up vote 2 down vote accepted

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

share|cite|improve this answer


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)

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

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.