# 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

(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

Subscribe
Notify of
Guest

That was really helpful. Thankyou so much!