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

**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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <stdio.h> int inverse(int a, int b) { int inv = -1; int q, r, r1 = a, r2 = b, t, t1 = 0, t2 = 1; while (r2 > 0) { q = r1 / r2; r = r1 - q * r2; r1 = r2; r2 = r; t = t1 - q * t2; t1 = t2; t2 = t; } if (r1 == 1) inv = t1; if (inv < 0) inv = inv + a; return inv; } int gcd(int a, int b) { int q, r; while (b > 0) { q = a / b; r = a - q * b; a = b; b = r; } return a; } // C program to find general solution to given Linear Congruence Equation int main() { int a, b, c, d, n, a1, b1, n1, x0; char ch; int inv; while (!feof(stdin)) { fscanf(stdin, "%dx", &a); ch = getc(stdin); if (ch == '+') { fscanf(stdin, "%d=%d(mod %d)\n", &c, &b, &n); fprintf(stdout, "%dx+%d=%d(mod %d)\n", a, c, b, n); b = b - c; if (b < 0) b = b + n; } else { fscanf(stdin, "%d(mod %d)\n", &b, &n); fprintf(stdout, "%dx=%d(mod %d)\n", a, b, n); } fprintf(stdout, "Reduced Equation: %dx=%d(mod %d)\n", a, b, n); d = gcd(a, n); fprintf(stdout, "GCD(%d, %d) = %d\n", a, n, d); if ((n % b == 0) || (d % b == 0)) { fputs("The given equation has No solution.\n", stdout); continue; } a1 = a / d; b1 = b / d; n1 = n / d; fprintf(stdout, "Reduced Equation: %dx=%d(mod %d)\n", a1, b1, n1); inv = inverse(n1, a1); fprintf(stdout, "inv(%d) = %d\n", a1, inv); x0 = (b1 * inv) % n1; fprintf(stdout, "General Solution: " "x = %d + %dk where k is any integer\n\n", x0, n / d); } return 0; } |

**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

**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

That was really helpful. Thankyou so much!