Division by a prime ≡ 3 (mod 4)

**kimberu** · November 4th 2010, 06:59 PM

Hi,

"If p is a prime congruent to 3 (mod 4) and $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.

**tonio** · November 4th 2010, 07:09 PM

Originally Posted by kimberu

Hi,

"If p is a prime congruent to 3 (mod 4) and $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

**Unbeatable0** · November 5th 2010, 12:39 AM

If $x\not\equiv 0 \pmod{p}$ , from $y^2 \equiv -x^2\pmod{p}$ it follows that

$<br /> 1 = \left(\frac{-x^2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{x^2}{p}\right) = \left(\frac{-1}{p}\right)<br />$

which is a contradiction (why?)

Thread: Division by a prime ≡ 3 (mod 4)

LinkBack

Thread Tools

Display

Division by a prime ≡ 3 (mod 4)

Similar Math Help Forum Discussions

Give a proof of ⊢ A ≡ B ≡ (A ∧ B) ∨ (¬A ∧ ¬B)

a^p≡1 (mod p^n) iff a≡1 (mod p^(n-1)), n≥2

lcm of k,k+1,k+2 where k≡3(mod 4)

x≡y (mod a) => (x,a)=(y,a)

Odd prime division problem

Search Tags