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,


Input:

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.

Input:

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

Input:

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

Output: The given equations has no solutions.

 

C++

Download   Run Code


Input:

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

Output:

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 🙂