How does chinese remainder theorem work

For any system of equations like this, the Chinese Remainder Theorem tells us there is always a unique solution up to a certain modulus, and describes how to find the solution efficiently. In fact, this correspondence goes further than a simple relabelling. This is often cheaper because for many algorithms, doubling the size of the input more than doubles the running time.

Proof : This is an easy induction from the previous form of the theorem, or we can write down the solution directly.

Then by a similar argument to before,. The second part basically states that all solutions including the minimum one produce the same remainder when divided by-product of n[0], num[1],.. And 11 is one solution, other solutions are 71, ,.. All these solutions produce the same remainder when divided by 60, i. A Naive Approach to find x is to start with 1 and one by one increment it and check if dividing it with given elements in num[] produces corresponding remainders in rem[].

Once we find such an x, we return it. Below is the implementation of Naive Approach. Length; Console. Auxiliary Space : O 1 See below link for an efficient method to find x.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above. Skip to content. Change Language. Related Articles. Table of Contents. Save Article. Improve Article. Like Article. Returns the smallest. A Python3 program to demonstrate.

As per the Chinise remainder. Check if remainder of. If all remainders. Else try next number. This code is contributed by mits.