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

Download   Run Code



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 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  
newest oldest most voted
Notify of
Sanjana
Guest

That was really helpful. Thankyou so much!