I have looked across old past papers whilst revising and have stumbled across a question I have not seen before,
Let $n$ be a positive integer of the form $3(\textrm{mod} \; 4)$, show that n cannot be written as the sum of two squares.
I began by writing $$n=p_1^{a_1} {p_2^{a_2}} \cdot\cdot \cdot {p_k^{a_k}}.$$
Where $p$ is a prime number then I wrote $n=3+4t$, but I am not sure where to go from here, all help would be appreciated.
Best Answer
There's no reason to think in terms of prime factorization. If $m^2+n^2\equiv3\pmod 4$, then $m$ and $n$ can't be both even nor can they be both odd. Therefore, you can assume withou loss of generality that $m$ is odd and $n$ is even. If $m=2a+1$ and $n=2b$, with $a,b\in\mathbb Z$, then$$m^2+n^2=4(a^2+a+b^2)+1\not\equiv3\pmod4.$$