n is of the form 3(mod 4), prove n cannot be sum of two squares.

Question

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.

Answer 1

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

Answer 2

$\begin{array}{c|c} x & x^2 \pmod 4\\ 0 & 0\\ 1 & 1\\ 2 & 0\\ 3 & 1\end{array}\quad$ So the sum of two squares can be $\{0,1,2\}\pmod 4$ but never $3$.