Given a prime $p$ of the form $4k+3$ and a pair of integers $a,b$ such that $p$ does not divide the gcd of $a$ and $b$, prove that $p$ does not divide $a^2+b^2$.
This is an intermediate step of the following problem
https://math.stackexchange.com/questions/2604791/considering-a-prime-p-of-the-form-4k3-show-that-for-any-pair-of-integers
I have no clue, so any hint will be appreciated.
Suppose $p\mid a^2+b^2$ with $p\nmid a,b$. Write $$a^2\equiv -b^2\pmod{p}$$ and raise both sides to the $(p-1)/2$'th power. By Fermat this gives $$1\equiv a^{p-1}\equiv (-1)^{\frac{p-1}{2}}b^{p-1}\equiv (-1)^{2k+1}\equiv -1 \pmod{p},$$ and this is clearly impossible for $p\ne 2$.