Chinese Remainder Theorem

Write a C/C++ program to solve given simultaneous pairs of Linear Congruence Equations using Chinese remainder theorem.


The Chinese remainder theorem is a theorem which gives a unique solution to simultaneous linear congruences with coprime moduli. In its basic form, the Chinese remainder theorem will determine a number p that, when divided by some given divisors, leaves given remainders.

Related post: Solving Simultaneous Pairs of Linear Congruences


For example,


x≡2(mod 3)
x≡3(mod 5)
x≡2(mod 7)

Output: x = 233

Solution of the given equations is x≡23(mod 105)
When we divide 233 by 105, we get remainder 23.


x≡4(mod 10)
x≡6(mod 13)
x≡4(mod 7)
x≡2(mod 11)

Output: x = 81204

Solution of the given equations is x≡1124(mod 10010)
When we divide 81204 by 10010, we get remainder 1124


x≡3(mod 7)
x≡3(mod 10)
x≡0(mod 12)

Output: The given equations has no solutions.



Download   Run Code


x=4(mod 10)
x=6(mod 13)
x=4(mod 7)
x=2(mod 11)


x = 81204

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂