# Division by a prime ≡ 3 (mod 4)

• Nov 4th 2010, 06:59 PM
kimberu
Division by a prime ≡ 3 (mod 4)
Hi,

"If p is a prime congruent to 3 (mod 4) and $\displaystyle x^2 + y^2$ is congruent to 0 (mod p), show p divides x and p divides y."

I tried to solve by contradiction, saying that if p doesn't divide x then it doesn't divide y either, but from there I don't know what to do. This is supposed to be a pretty straightforward problem, so any help would be great. Thanks.
• Nov 4th 2010, 07:09 PM
tonio
Quote:

Originally Posted by kimberu
Hi,

"If p is a prime congruent to 3 (mod 4) and $\displaystyle x^2 + y^2$ is congruent to 0 (mod p), show p divides x and p divides y."

I tried to solve by contradiction, saying that if p doesn't divide x then it doesn't divide y either, but from there I don't know what to do. This is supposed to be a pretty straightforward problem, so any help would be great. Thanks.

It seems like you haven't yet heard of the rather well-known theorem that says that a prime is expressable as the sum of two squares

iff it is 1 mod 4, so I think you'll have to prove it. It appears in pretty much every decent number theory book and in thousands of internet sites.

Tonio
• Nov 5th 2010, 12:39 AM
Unbeatable0
If $\displaystyle x\not\equiv 0 \pmod{p}$, from $\displaystyle y^2 \equiv -x^2\pmod{p}$ it follows that

$\displaystyle 1 = \left(\frac{-x^2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{x^2}{p}\right) = \left(\frac{-1}{p}\right)$