# Find general solution to given Linear Congruence Equation

Write a C/C++ program to find general solution to given Linear Congruence Equation.

For example,

Input: 14x≡12(mod 18)

Output: General Solution of the given equation is x = 6 + 9k where k is any integer

Input: 232x+42≡248(mod 50)

Output: General Solution of the given equation is x = 8 + 25k where k is any integer

Related post: Solving Simultaneous Pairs of Linear Congruences

## C

Input:
14x=12(mod 18)
3x+4=6(mod 13)
232x+42=248(mod 50)
3x+5=4(mod 5)
4x+6=4(mod 6)
9x+4=12(mod 7)

Output:

14x=12(mod 18)
Reduced Equation: 14x=12(mod 18)
GCD(14, 18) = 2
Reduced Equation: 7x=6(mod 9)
inv(7) = 4
General Solution: x = 6 + 9k where k is any integer

3x+4=6(mod 13)
Reduced Equation: 3x=2(mod 13)
GCD(3, 13) = 1
Reduced Equation: 3x=2(mod 13)
inv(3) = 9
General Solution: x = 5 + 13k where k is any integer

232x+42=248(mod 50)
Reduced Equation: 232x=206(mod 50)
GCD(232, 50) = 2
Reduced Equation: 116x=103(mod 25)
inv(116) = 11
General Solution: x = 8 + 25k where k is any integer

3x+5=4(mod 5)
Reduced Equation: 3x=4(mod 5)
GCD(3, 5) = 1
Reduced Equation: 3x=4(mod 5)
inv(3) = 2
General Solution: x = 3 + 5k where k is any integer

4x+6=4(mod 6)
Reduced Equation: 4x=4(mod 6)
GCD(4, 6) = 2
Reduced Equation: 2x=2(mod 3)
inv(2) = 2
General Solution: x = 1 + 3k where k is any integer

9x+4=12(mod 7)
Reduced Equation: 9x=8(mod 7)
GCD(9, 7) = 1
Reduced Equation: 9x=8(mod 7)
inv(9) = 4
General Solution: x = 4 + 7k where k is any integer