1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Relevance of CRT to this question

  1. Nov 5, 2005 #1
    Q. Use the chinese remainder theorem to find the inverse of 32 (mod 3 * 5).

    The question's wording seems to suggest that using the CRT to find the inverse is faster or computationally easier than solving [tex]32x \equiv 1\left( {\bmod 15} \right)[/tex]. I don't see how this is so.

    In any case if I am to use the CRT I need some simultaneous congruences.

    32x \equiv 1\left( {\bmod 15} \right) \Leftrightarrow 32x \equiv 1\left( {\bmod 5} \right),32x \equiv 1\left( {\bmod 3} \right)

    But does using the CRT actually make the calculation of the inverse any more easy? Using the CRT procedure I just back to [tex]32x \equiv 1\left( {\bmod 15} \right)[/tex].

    Does using the CRT actually simplify any of the calculations?
  2. jcsd
  3. Nov 5, 2005 #2


    User Avatar
    Science Advisor

    I don't know that it would be any easier that way- the problem is pretty close to trivial anyway. 32 is, of course, equivalent to 2 (mod 3) or (mod 5).
    It's easy to see that 2x= 1 (mod 3) gives x= 2 {(2*2)= 4= 1 (mod 3)} and that 2x= 1 (mod 5) gives x= 3 {(2*3)= 6= 1 (mod 5)}. Other numbers equivalent to 2 (mod 3) are 2+3= 5, 2+ 2(3)= 8, etc. Other numbers equivalent to 3 (mod 5) are 3+ 2= 8, 3+ 2(5)= 13, etc. The first to appear on both lists is 8. That is 2x= 1 (mod 3) and 2x= 1 (mod 5) for x= 8.
    By the Chinese remainder theorem, 32x= 1 (mod 15) which is equivalent to 2x= 1 (mod 15) for x= 8. Of course, it was easy to see that 2(8)= 16= 1 (mod 15) directly.
  4. Nov 5, 2005 #3
    Thanks for the response.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook