Chinese Remainder Theorem
Understand how to apply the Chinese Remainder Theorem to solve problems involving simultaneous modular equations. Learn to find the minimum value of x that satisfies given remainders using modular inverses and number theory concepts. This lesson explains the theorem’s formula, the role of pairwise coprime moduli, and includes implementation details for practical coding use.
We'll cover the following...
Problem introduction
The Chinese Remainder theorem is used to solve problems typical of the form “Find a number which when divided by 2 leaves remainder 1, when divided by 3 leaves remainder 2, and when divided by 7 leaves remainder 5”. These problems can be reformulated into a system of linear congruence and can then be solved using the Chinese Remainder theorem. For example, the above problem can be expressed as a system of three linear congruences:
x ≡ 1 (mod 2), x ≡ 2 mod(3), x ≡ 5 mod (7)
We are given with two arrays, i.e., num[] and rem[]. For the above example, we can have num[] = {2, 3, 7} and rem[] = {1, 2, 5}.
The Chinese Remainder theorem states that there always exists an x that satisfies given congruence.
Basically, we are given k numbers which are pairwise co-prime and given remainders of these numbers when an unknown number x is ...