CodeChef Logo CodeChef Logo
Learn Practice Compete
Upgrade to Pro
Learn Practice Compete
Home » Wiki » Very brief tutorial for Chinese Remainder Theorem

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

Programming Tools

Online IDE
Upcoming Coding Contests
Host Your Contest
Problem Setting

Learning Resources

Getting Started
Practice Problems
CodeChef Discuss
FAQ's

More

CodeChef For Business
Contact Us
Code Of Conduct
User Ranklist

Usage Policy

Privacy policy
Terms
www.codechef.com
Follow Us

We use cookies to improve your experience and for analytical purposes. Read our Privacy Policy and Terms to know more. You consent to our cookies if you continue to use our website.