Finding the inverse of 32 (mod 15) using the Chinese remainder theorem

[Benny]

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 $$32x \equiv 1\left( {\bmod 15} \right)$$. 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 $$32x \equiv 1\left( {\bmod 15} \right)$$.

Does using the CRT actually simplify any of the calculations?

 

[HallsofIvy]

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.

 

[Benny]

Thanks for the response.