Results 1 to 3 of 3

Math Help - Division by a prime ≡ 3 (mod 4)

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    41

    Division by a prime ≡ 3 (mod 4)

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by kimberu View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    106
    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?)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: June 28th 2010, 08:32 PM
  2. a^p≡1 (mod p^n) iff a≡1 (mod p^(n-1)), n≥2
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 8th 2010, 08:59 AM
  3. lcm of k,k+1,k+2 where k≡3(mod 4)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 12th 2010, 01:46 PM
  4. x≡y (mod a) => (x,a)=(y,a)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 7th 2010, 05:05 AM
  5. Odd prime division problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 30th 2008, 02:48 PM

Search Tags


/mathhelpforum @mathhelpforum