Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

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.

share|improve this answer
    
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
3  
@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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.