Results 1 to 2 of 2

Math Help - congruence

  1. #1
    Super Member
    Joined
    Aug 2009
    Posts
    639

    congruence

    how do you find the smallest possible integer such that x ^35 is congruent to 11 mod 42?

    i know that the order of 42 is 12. that means that x ^12 is congruent to 1 mod 42 where gcd(x,42)=1..
    and then im stuck
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by alexandrabel90 View Post
    how do you find the smallest possible integer such that x ^35 is congruent to 11 mod 42?

    i know that the order of 42 is 12. that means that x ^12 is congruent to 1 mod 42 where gcd(x,42)=1..
    and then im stuck
    If x ^12 is congruent to 1 mod 42 then so is x^36. So x^35 is congruent to x^{-1}. Thus you want to solve 11x\equiv1\!\!\!\pmod{42}. Probably the most painless way to do that is to use the Chinese remainder theorem, in other words solve the congruence mod 6 and mod 7, then glue the results together to get the solution mod 42.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: May 12th 2009, 10:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 01:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 05:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 09:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 10:57 AM

Search Tags


/mathhelpforum @mathhelpforum