Find a general solution to the given Linear Congruence Equation

Write a C/C++ program to find a general solution to the 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:

Solve Simultaneous Pairs of Linear Congruence Equations

Implementation:

C

#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 a general solution to the 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;

}

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

That’s all about finding a general solution to the given Linear Congruence Equation.

Find a general solution to the given Linear Congruence Equation

C

Share this: