- #1
Benny
- 584
- 0
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.
[tex]
32x \equiv 1\left( {\bmod 15} \right) \Leftrightarrow 32x \equiv 1\left( {\bmod 5} \right),32x \equiv 1\left( {\bmod 3} \right)
[/tex]
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?
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.
[tex]
32x \equiv 1\left( {\bmod 15} \right) \Leftrightarrow 32x \equiv 1\left( {\bmod 5} \right),32x \equiv 1\left( {\bmod 3} \right)
[/tex]
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?