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,
Best 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.