In one of my classes, the following approach was shown to solve modulo operations involving huge numbers:
Problem to solve:
49 10 mod 187.
Approach taken:
- Prime factorize $187$. It's factors are $11$ and $17$.
- Find 49 10 mod 11, which involves:
- Replacing 49 10 mod 11 as 5 10 mod 11
- 5 10 mod 11 => 1 mod 11 => 1 (Using fermat's little theorem)
- Find 49 10 mod 17, which involves:
- Replacing 49 10 mod 17 as 15 10 mod 17
- 15 10 mod 17 => 4 (Can be solved using repeated exponents approach)
- Find a number which yields remainder of $1$ when divided by $11$ (step-2) and which yields remainder of $4$ when divided by $17$. For ex: $\{4,21,38,55,72,89...\}$ In this set $89$ is such a number.
- Hence it was concluded that 89 is the solution of 49 10 mod 11
What I understood in the above approach I got the parts of solving the prime factored modulo versions using fermets and repeated powering.
What I am failing to understand in the above approach
How does this approach work, like modulo of a number (n) by its individual prime factors (p,q) leading to the modulo of a number (n) by (pq).
Replacement of 49 10 mod 11 as 5 10 mod 11. I believe 5 and 49 are in the same congruence classes of modulo 11. Considering that what are the conditions in which such a replacement is valid?
I am new to this topic, so please try to explain in simple terms and provide some examples to help me understand this.
Thanks for your help.