Results 1 to 8 of 8

Math Help - Some congruence questions

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    22

    Some congruence questions

    Hi please help me on these problems

    1. For p an odd prime and a any integer which is not congruent to 0 mod p, prove that the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)

    2. For integers a and b with (a,b) =1, prove that if p is any odd prime which divides a^2+b^2 then p=1 (mod4)

    Thank you very much in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by machack View Post
    Hi please help me on these problems

    1. For p an odd prime and a any integer which is not congruent to 0 mod p, prove that the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)

    2. For integers a and b with (a,b) =1, prove that if p is any odd prime which divides a^2+b^2 then p=1 (mod4)

    Thank you very much in advance!
    1.)

     \left(\frac{-a^2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{a}{p}\right)^2 = \left(\frac{-1}{p}\right) = \begin{cases}<br />
  1, & \mbox{if } p \equiv 1\mod{4} \\<br />
  -1,  & \mbox{if } p \equiv 3\mod{4}<br />
\end{cases}

    Hence  x^2\equiv -a^2\mod{p} is solvable  \iff p \equiv 1\mod{4} .

    2.)

     p\mid a^2+b^2 \implies a^2+b^2\equiv0\mod{p}\implies b^2\equiv-a^2\mod{p} \implies p\equiv 1 \mod{4} since  x^2\equiv-a^2\mod{p} is solvable.

    Here's some work for you: I never explicitly stated that  (a,b)=1 . Let's see if you can figure out where that fact is needed above.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    22
    Quote Originally Posted by chiph588@ View Post
    1.)

     \left(\frac{-a^2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{a}{p}\right)^2 = \left(\frac{-1}{p}\right) = \begin{cases}<br />
  1, & \mbox{if } p \equiv 1\mod{4} \\<br />
  -1,  & \mbox{if } p \equiv 3\mod{4}<br />
\end{cases}

    Hence  x^2\equiv -a^2\mod{p} is solvable  \iff p \equiv 1\mod{4} .

    2.)

     p\mid a^2+b^2 \implies a^2+b^2\equiv0\mod{p}\implies b^2\equiv-a^2\mod{p} \implies p\equiv 1 \mod{4} since  x^2\equiv-a^2\mod{p} is solvable.

    Here's some work for you: I never explicitly stated that  (a,b)=1 . Let's see if you can figure out where that fact is needed above.
    For number 2, is it just that we have to show neither of a or b are 0 mod p, after which we can just apply question 1?

    Since p|a^2+b^b, either p|a and p|b or p divides neither. The former would contradict (a,b)=1. Right?

    Thanks

    Edit: also, is there a way to prove question 1 without using the legendre symbol?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by machack View Post
    For number 2, is it just that we have to show neither of a or b are 0 mod p, after which we can just apply question 1?

    Since p|a^2+b^b, either p|a and p|b or p divides neither. The former would contradict (a,b)=1. Right?

    Thanks

    Edit: also, is there a way to prove question 1 without using the legendre symbol?
    I'll think about #1 again.

    Here's a better way to think about #2: Let's work in  \mathbb{Z}[i] .

     a^2+b^2=(a+ib)(a-ib) , so  p\mid a^2+b^2\implies p\mid a+ib or  p\mid a-ib . Because  (a,b)=1\implies a+ib \neq p\cdot d where  d\in\mathbb{Z}[i] .
    One can deduce from this that  p=(c+id)(c-id) \implies p\equiv 1\mod{4}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2010
    Posts
    22
    Quote Originally Posted by chiph588@ View Post
    I'll think about #1 again.

    Here's a better way to think about #2: Let's work in  \mathbb{Z}[i] .

     a^2+b^2=(a+ib)(a-ib) , so  p\mid a^2+b^2\implies p\mid a+ib or  p\mid a-ib . Because  (a,b)=1\implies a+ib \neq p\cdot d where  d\in\mathbb{Z}[i] .
    One can deduce from this that  p=(c+id)(c-id) \implies p\equiv 1\mod{4}
    Does my suggestion work though?
    1. For p an odd prime and a any integer which is not congruent to 0 mod p, prove that the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)
    2. For integers a and b with (a,b) =1, prove that if p is any odd prime which divides a^2+b^2 then p=1 (mod4)

    So to prove problem 2 (that given a^b=-b^2 (mod p) for (a,b)=1, prove p = 1(mod 4)), we can use the "only if" part of problem 1 as long as we can prove that b is not congruent to 0 mod p. And I believe this can be done by saying p|a^2+b^2 -> its impossible for p to divide only one of a or b, and if p could divide both then the GCD of a and b would be at least p (contradicting the given). Thus neither a nor b are congruent to 0 mod p and we can apply "For p an odd prime and a any integer which is not congruent to 0 mod p, the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)".
    Does this work?

    Also, these are problems for an elementary number theory course and I'm afraid I haven't gotten far enough to understand your new explanation.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by machack View Post
    Does my suggestion work though?
    1. For p an odd prime and a any integer which is not congruent to 0 mod p, prove that the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)
    2. For integers a and b with (a,b) =1, prove that if p is any odd prime which divides a^2+b^2 then p=1 (mod4)

    So to prove problem 2 (that given a^b=-b^2 (mod p) for (a,b)=1, prove p = 1(mod 4)), we can use the "only if" part of problem 1 as long as we can prove that b is not congruent to 0 mod p. And I believe this can be done by saying p|a^2+b^2 -> its impossible for p to divide only one of a or b, and if p could divide both then the GCD of a and b would be at least p (contradicting the given). Thus neither a nor b are congruent to 0 mod p and we can apply "For p an odd prime and a any integer which is not congruent to 0 mod p, the congruence x^2 = -a^2 (mod p) has solutions if and only if p=1 (mod4)".
    Does this work?

    Also, these are problems for an elementary number theory course and I'm afraid I haven't gotten far enough to understand your new explanation.
    Your arguement is almot correct and the same thing I was hinting at earlier.
    We can say WLOG p does not divide b. (For all we know p could divide b and not a.)

    It turns out p doesn't divide a or b. Can you see why?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2010
    Posts
    22
    Quote Originally Posted by chiph588@ View Post
    Your arguement is almot correct and the same thing I was hinting at earlier.
    We can say WLOG p does not divide b. (For all we know p could divide b and not a.)

    It turns out p doesn't divide a or b. Can you see why?
    Well we know p can't divide b and not a because if for 3 integers x,y, and z, if x|y+z and x|y, then x|z. In this case, p|a^2 + b^2 and if p|b (which means p|b^2), then p|a^2. Since p is a prime, it follows that p|a.

    And as I said earlier, if p|a and p|b, then (a,b)=>p, a contradiction. So p doesn't divide a or b.

    I got the gist of things now. Thank you very much for your help!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by machack View Post
    Well we know p can't divide b and not a because if for 3 integers x,y, and z, if x|y+z and x|y, then x|z. In this case, p|a^2 + b^2 and if p|b (which means p|b^2), then p|a^2. Since p is a prime, it follows that p|a.

    And as I said earlier, if p|a and p|b, then (a,b)=>p, a contradiction. So p doesn't divide a or b.

    I got the gist of things now. Thank you very much for your help!
    Of course! Slipped my mind!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] congruence
    Posted in the Geometry Forum
    Replies: 0
    Last Post: January 15th 2011, 02:58 AM
  2. Congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 29th 2010, 03:30 PM
  3. Congruence
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 4th 2010, 07:43 PM
  4. Difficult Congruence related questions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 2nd 2010, 03:29 AM
  5. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 01:52 PM

Search Tags


/mathhelpforum @mathhelpforum