If a prime $p>2$ is expressible as $p=a^2+b^2$, then $4\mid (p-1)$ Show that if $p\in\mathbb{P}, p>2$ is a sum of squares, i.e $p=a^2+b^2$, then $p\equiv 1\pmod{4}$.  
Have established that the remainder can't be either of $0,2$ for obvious reasons. So we must consider $1$ or $3$. Attempting assume by contradiction that $4\mid (p-3)$:
$$4k+3= a^2+b^2\Longleftrightarrow 4k + 2ab +3 = (a+b)^2$$
I can't find a contradiction, yet when I think about a prime divided by 4 giving the remainder of 3, for example 7, there is no way to express it as a sum of squares.
Another attempt at the same approach is $4k+3 = a^2+b^2$ so we have
$$4k-a^2=b^2-3$$
I believe I should somehow conclude one of the summands is not a square of an integer. How to proceed?
 A: HINT: Show that one of $a$ and $b$ is odd and the other even – it appears that you’ve essentially done this already – and see what this says about $a^2+b^2$ modulo $4$.
A: This problem is easier than it looks.  The only values of $n^2$  mod $4$ are $0$ and $1$.  So $p = a^2+b^2$ must be $0$, $1$, or $2$ mod 4.  Of those, only $4n+1$ is odd, so the other two cases cannot be prime (for $p>2).
A: Instead of cancelling out the remainders, I proved that if this is to happen then the remainder is 1.
Proof:
First of all we note that in all cases $p$ must be odd. So $a^2 + b^2$ must be odd. So $a$ and $b$ can not be both odd and even since then $a^2 + b^2$ would produce an even number. So one of $a$ and $b$ is odd and the other is even. Now let us take that $a$ is odd and $b$ that is even.
Now, $$a^2 + b^2 = (2m+1)^2 + (2n)^2 = 4m^2 + 4m + 1 + 4n^2 = 4(m^2 + m + n^2) + 1 = 4k + 1$$ 
But we know that when we divide $4k + 1$, we get a remainder of 1 so $p \equiv 1 \pmod 4$. Hence, proved.
Hope you found that useful.
A: First of all, recall that if $n$ is a perfect square then $n\equiv0,1\pmod4$:


*

*$k\equiv0\pmod4 \implies k^2\equiv0^2\equiv0\pmod4$

*$k\equiv1\pmod4 \implies k^2\equiv1^2\equiv1\pmod4$

*$k\equiv2\pmod4 \implies k^2\equiv2^2\equiv0\pmod4$

*$k\equiv3\pmod4 \implies k^2\equiv3^2\equiv1\pmod4$


Therefore, $a^2+b^2\equiv0,1,2\pmod4$.


*

*If $a^2+b^2\equiv0\pmod4$ then $a^2+b^2$ is divisible by $4$

*If $a^2+b^2\equiv2\pmod4$ then $a^2+b^2$ is divisible by $2$


Therefore, if $a^2+b^2$ is prime then $a^2+b^2\equiv1\pmod4$.
