Very brief tutorial for Chinese Remainder Theorem |
You can learn CRT mostly from it's wikipedia article.
Break General modulo into prime power modulo's
A summary: Basically when we have to compute something modulo n where n is not prime, according to this theorem, we can break this kind of questions into cases where the number by which you are taking modulo's is a prime power.
This can be done by write n in its prime representation n = p1q1. . . pkqk
Compute modulo p^k by usual methods
Many times we can use standard tricks to find answer modulo p^k.
Merge those answers
After getting modulo p^k answers, we can merge them using CRT. For that see the example given in the wikipedia page.
Short Example
Compute a^b % n assume a = 4 and n = 6.
Write n = 6 = 2 * 3
Compute a^b % 2 = 0
Compute a^b % 3 = 1
Now merge them using CRT. See the formula given in the wikipedia to merge it.
Details of Merging
Assume we want to find a % n.
Let n = p1 * p2.
Find a % p1 and a % p2. Call a % p1 = x1
Call a % p2 = x2; For finding a % n. We can do following.
Write a % n = x1 * alpha1 + x2 * alpha2; (Proof is very simple).
where alpha1 is such that
alpha1 = 1 mod p1
and alpha1 = 0 mod p2
Similarly define alpha2
where alpha1 is such that
alpha2 = 0 mod p1
and alpha2 = 1 mod p2
So basically find alpha1, alpha2. For finding these, you need to solve two equations of two variables. That can be done by simplifying the equations written above.
Finally your answer will x1 * alpha1 + x2 * alpha2.
Sample Implementation
See the following code
