For $p$ prime, $p = a^2 + b^2$, why must $a$ or $b$ be a square?

Question

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

Answer 1

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.

Answer 2

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