## 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 = p_{1}^{q1}. . . p_{k}^{qk}

**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