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.

Input:

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

Output:

x = 81204

(1 votes, average: 5.00 out of 5)