Using factorization to solve modulo arithmetic involving big numbers.

483 Views Asked by At

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:

  1. Prime factorize $187$. It's factors are $11$ and $17$.
  2. 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)
  3. 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)
  4. 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.
  5. 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

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

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