Results 1 to 3 of 3

Math Help - 2^x in a congruence equation

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    2^x in a congruence equation

    Hi,

    How would you figure out if there is a solution to a congruence equation like 2^x = -1 mod 5003. I don't know if it's better to think about it as 2^x + 1 = 0 mod 5003 or 2^x = 5002 mod 5003 or what. Any help would be appreciated. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by jimmyjimmyjimmy View Post
    Hi,

    How would you figure out if there is a solution to a congruence equation like 2^x = -1 mod 5003. I don't know if it's better to think about it as 2^x + 1 = 0 mod 5003 or 2^x = 5002 mod 5003 or what. Any help would be appreciated. Thanks.

    An idea: As (2,5003)=1, Fermat's Little Theorem tells us that 2^{5002}=1\!\!\!\!\pmod{5003}\Longrightarrow 2^{2501}=\pm 1\!\!\!\!\pmod{5003}

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    The answer to this question is given by Euler's criterion, along with Gauss's second supplement to the quadratic reciprocity law. Euler's criterion states that for an odd prime p,

    \left(\frac{a}{p}\right)\equiv a^{(p-1)/2} \mod p

    and Gauss's second supplement to the quadratic reciprocity law states that

    \left(\frac{2}{p}\right)\equiv (-1)^{(p^2-1)/8} \mod p.

    What can you conclude from this?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 18th 2010, 07:26 AM
  2. congruence equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 2nd 2010, 07:20 AM
  3. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2008, 06:54 PM
  4. Congruence Equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 13th 2006, 06:00 PM
  5. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 15th 2006, 08:10 PM

Search Tags


/mathhelpforum @mathhelpforum