Results 1 to 4 of 4

Math Help - congruence problem

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    congruence problem

    Hi,

    Find an x which satisfies 13^x = 13 mod 5003^2.

    I started by noting that the same x will solve 13^(x - 1) = 1 mod 5003^2.

    Since 5003 is prime and of course does not divide 13, we know that 13^(5002) = 13^(5003 - 1) = 1 mod 5003.

    I'm not sure how to move from mod 5003 to mod 5003^2, though i'm kind of guessing that the answer is x = 5002 for the 5003^2 case, but i'm not sure. does anyone know what to do or know of a useful theroem? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    Alternative approach

    The totient function (phi(n)) is the number of integers less than and relatively prime to n. It's known that for an integer relatively prime to the modulus, a^phi(n) = 1 mod n. For instance, for a prime p, phi(p) = p-1 and
    a^(p-1) = 1 mod p. In your case the modulus is of the form p^2, and phi(p^2) = p^2 - p. So an x that would solve your equation is:
    5003^2 - 5003 + 1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
     x=1 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2009
    Posts
    12
    yeah you are right x=1 works, but i forgot to add that you have to find an x greater than 1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Congruence Problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 29th 2011, 07:41 AM
  2. Congruence problem
    Posted in the Number Theory Forum
    Replies: 19
    Last Post: December 25th 2009, 07:23 PM
  3. congruence problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 2nd 2009, 10:24 AM
  4. Another congruence problem
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 3rd 2009, 05:14 PM
  5. Congruence Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 14th 2007, 10:25 AM

Search Tags


/mathhelpforum @mathhelpforum