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

-
7 is a prime. Yet 7=/=1mod4. –  simplicity Nov 3 '11 at 0:26
I was unclear, I meant "if $p$ is a prime and if $p = 1 \pmod{4}$, then...", not "if $p$ is a prime, then $p = 1 \pmod{4}$ and..." . –  michael Nov 3 '11 at 0:31
I don't even think this is correct. 7=? you can't write 7 in that form yet 7 is a prime. –  simplicity Nov 3 '11 at 0:35
$7=3 \pmod{4}$. –  michael Nov 3 '11 at 0:36
It's easy if I knew that. Take $a^2+b^2$ mod 4 and that work out what the possibilities. –  simplicity Nov 3 '11 at 0:44

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.

-
I don't like that proof. I know you are using 1mod4 to conclude that a or b is odd. If that was the only thing needed. Why didn't the OP put 1mod2? You get the same deduction. –  simplicity Nov 3 '11 at 0:49
@simplicity: If $p\equiv 3\pmod{4}$, then $p$ is not representable. Also, the Jacobi symbol inversion need not work if $p\equiv 3\pmod{4}$. –  André Nicolas Nov 3 '11 at 0:55
I skipped a middle step between $(a/p)=(p/a)$. I've put it into the solution, so that it is obvious where I use that $p\equiv 1 \pmod 4$. –  Thomas Andrews Nov 3 '11 at 0:58
You can actually use this to prove that not only is $a$ a square, but any divisor of $a$ is a square $\pmod p$. –  Thomas Andrews Nov 3 '11 at 1:23
Note you can skip Jacobi symbols by showing that if $q|a$ is prime, then $(q/p)=(p/q)=(b^2/q)=1$. So $a$ is the product of squares, and therefore must be a square. ($a$ can be negative, but $(-1/p)=1$, too, so that case is covered.) –  Thomas Andrews Nov 3 '11 at 13:50

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

-