For $p$ prime, $p = a^2 + b^2$, why must $a$ or $b$ be a square? If p prime and if $p = 1 \pmod{4}$, then $p = a^2 + b^2$; why must $a$ or $b$ be a square mod $p$?
 A: One of $a$ or $b$ is odd.  Assume it is $a$.
Then $$\left(\frac{a}{p}\right)=(-1)^{\frac{p-1}2\frac{a-1}2}\left(\frac{p}{a}\right) =\left(\frac{p}{a}\right) = \left(\frac{b^2}a\right) = 1$$
Where we are using general Jacobi symbols, rather than Legendre symbols.
A: This answer adds a small amount of detail to the one by @Thomas Andrews, but uses exactly the same idea.
Suppose that $p=a^2+b^2$.  Let $a$ have the prime power factorization
$$a=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}.$$
Suppose first that $a$ is odd.
Then $p\equiv b^2 \pmod{p_i}$, so $p$ is a quadratic residue modulo $p_i$ for every $i$.  It follows that the Legendre symbols $(p/p_i)$ are all equal to $1$, and therefore by Reciprocity so are the Legendre symbols $(p_i/p)$. Thus $a$, and indeed every factor of $a$, is a quadratic residue of $p$. 
Suppose next that $a$ is even.  By the same argument as the one above, every odd factor of $a$ is a quadratic residue of $p$.  If $p$ is of the shape $8t+1$, then $(2/p)=1$, and therefore $a$, and every factor of $a$, is a quadratic residue of $p$. Finally, suppose that $p$ is of the shape $8t+5$. Then $a \equiv 2\pmod{4}$. Since $2$ is not a quadratic residue of $p$, it follows that $a$ is not a quadratic residue of $p$. 
