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.

 

Download   Run Code


Input:

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

Output:

x = 81204

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of