Primes that can't be written as sum of two squares. Mod I came to this conclusion: the primes that can't be written as the sum of two squares (lets use$p\prime$ to denote) can be written as ${p}\prime \equiv 3 \;(\bmod\; 4)$.
I need a simple proof to show this and am stuck. I would appreciate guidance!
 A: Let $p = 4k+3$.
From assumption we have $p|a^2+b^2$ thus
$$a^2\equiv -b^2\;({\rm mod}\; p)$$
and
$$a^{2({2k+1})}\equiv -b^{2{(2k+1)}}\;({\rm mod}\; p)$$
By little Fermat theorem we have:
$$a^{4k+2}\equiv b^{4k+2}\equiv 1\;({\rm mod}\; p)$$
so
$$1\equiv -1\;({\rm mod}\; p)$$
and thus $p|2$ 
Contradiction.
A: Every square mod 4 is either 0 or 1, hence writing $p=x^2+y^2$ you get $p\in \{0,1,2\} (\mod 4)$. Since it is an odd prime and odd primes are either 1 or 3 mod 4 we come to the conclusion that $p$ cannot be 3 mod 4.
A: Good thinking.
It's not hard to show that a prime  congruent to $3$ mod $4$ is not a sum of two squares, since all squares are either $0$ or $1$ mod $4$. 
To show that the primes congruent to $1$ mod $4$ actually are the sums of two squares is harder. Fermat did it first. You can probably find a proof on the web.
A: There's a theorem due to Fermat which says that all primes $p$ such that $p\equiv1\pmod4$ can be written as the sum of two squares. And, of course, $2=1^2+1^2$. On the other hand, if an odd number $n$ can be written as $a^2+b^2$ for two integers $a$ and $b$, then, since $n$ is odd, $a$ is odd and $b$ is even or $a$ is even and $b$ is odd. In the first case, $a=2k-1$ and $b=2l$ for some integers $k$ and $l$. Therefore$$n=a^2+b^2=4k^4-4k+1+4l^2\equiv1\pmod4.$$The other case is similar.
A: Suppose $p$ is prime of the form $p=4k+3$ and that it can be written as the sum of two squares $p=a^2+b^2$. If you suppose that both $a$ and $b$ are even you will arive at a contradiction (plug in and square). You will also arrive at a contradiction if you suppose that they are both odd. And also if you suppose that one is odd and the other even. Conclude.
