Results 1 to 2 of 2

Thread: 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
    10
    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: Nov 10th 2008, 01:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 30th 2008, 05:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 30th 2008, 09:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 29th 2008, 10:57 AM

Search Tags


/mathhelpforum @mathhelpforum