# Using factorization to solve modulo arithmetic involving big numbers.

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.

• First of all, the guy's name is Fermat. If you know about basic ring theory (of integers) you might want to look into the Chinese Remainder Theorem. This is a classical application of it, and answers your question. Concerning your second question: This follows from the fact that taking a number modulo $11$ (or any other number) commutes with sums and products, e.g. ab mod 11 is the same as taking the product of a mod 11 and b mod 11 (and reducing the product modulo 11 again) Again this is basic ring theory (of integers) – kesa Feb 15 '18 at 9:29
• As @kesa says, this is a Chinese Remainder Theorem application. I'll point out that in your step 3, you can replace $15$ by $-2$ and make the calculation easier. $(-2)^4 \equiv 1 \pmod{17}.$ – B. Goddard Feb 15 '18 at 11:40
• @B.Goddard although it doesn't change the $(-2)^{10}$ result, I'll note that $(-2)^4\equiv -1 \bmod 17$. – Joffan Feb 16 '18 at 7:26