# Prove that $n$ is a sum of two squares?

Problem Let $n = p_1.p_2.p_3 \cdots p_k.m^2$, where $p_1, p_2, p_3 \cdots p_k$ are distinct primes. Prove that n is sum of two squares if and only if $p_i$ is either 2 or $p_i \equiv 1 \pmod{4}$

For $p_i = 2$ , this is trivial case since $2m^2 = m^2 + m^2$.
For $p_i \equiv 1 \pmod{4}$, I tried to use the fact that the product of a number of the form $4k + 1$ is also in this form. So I come up with: $$n = (4k + 1) \cdot m^2 = 4km^2 + m^2$$ Apparently, $m^2$ is a square, but I could not figure out how to prove $4km^2$ is a square, since k is in unknown form. Any idea?

Thanks,

-
Have you looked at en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares ? – Fixee Mar 28 '11 at 6:02

## 1 Answer

It follows from two facts, the first is that an odd prime is a sum of two squares if and only if it is congruent to $1$ modulo $4$.

The second fact is that a product of two integers that can be written as a sum of two squares is a sum of two squares. Namely:

$(a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2$.

Then you can proceed by induction... This question is in fact a weaker version of Fermat's theorem that give a generic formula for numbers that can be written as a sum of two squares.

-
Many thanks for those hints. – Chan Mar 28 '11 at 15:07
SUre, you are welcome :) – shamovic Mar 28 '11 at 16:06