congruence

Aug 2009
639
2
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
 

Opalg

MHF Hall of Honor
Aug 2007
4,039
2,789
Leeds, UK
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 \(\displaystyle 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.
 
  • Like
Reactions: alexandrabel90