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 . 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.