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

The Chinese remainder theorem is a theorem that 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:

Solve Simultaneous Pairs of Linear Congruence Equations

 
For example,


Input:
 
x=2(mod 3)
x=3(mod 5)
x=2(mod 7)
 
Output: x = 233
 
The solution of the given equations is x=23(mod 105)
When we divide 233 by 105, we get the remainder of 23.
 
Input:
 
x=4(mod 10)
x=6(mod 13)
x=4(mod 7)
x=2(mod 11)
 
Output: x = 81204
 
The solution of the given equations is x=1124(mod 10010)
When we divide 81204 by 10010, we get the remainder of 1124
 
Input:
 
x=3(mod 7)
x=3(mod 10)
x=0(mod 12)
 
Output: The given equations has no solutions.

 
Implementation:

Download  Run Code


Input:
 
x=4(mod 10)
x=6(mod 13)
x=4(mod 7)
x=2(mod 11)
 
Output:
 
x = 81204

That’s all about the Chinese Remainder Theorem.