# 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

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$.
$(a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2$.