Find a general solution of the Linear Diophantine equation

Write a C/C++ program to find a general solution to the Linear Diophantine equation. A linear Diophantine equation is a first degree (linear) polynomial whose solutions are restricted to integers.

For example,

Input: 25x + 10y = 15

Output: General Solution of the given equation is
x = 3 + 2k for any integer m
y = -6 – 5k for any integer m

Input: 21x + 14y = 35

Output: General Solution of the given equation is
x = 5 + 2k for any integer m
y = -5 – 3k for any integer m

Method for computing the initial solution to a linear Diophantine equation:

Given an equation ax + by = n

Use the Euclidean algorithm to compute gcd(a, b) = d.
Determine whether d | n. If not, then there are no solutions.
Reformat the equations from the Euclidean algorithm.
Using substitution, go through the steps of the Euclidean algorithm to find a solution to the equation ax_i + by_i = d.
The initial solution to the equation ax + by = n is the ordered pair (x_i . n/d, y_i . n/d).

General Solution to Linear Diophantine Equation:

When integer solutions exist to an equation ax + by = n, there are infinitely many solutions.

Theorem:

If (x*, y*) is an integer solution of the Diophantine equation ax + by = n, all integer solutions to the equation are of the following form for some integer m.

Linear Diophantine Equation Theorem

Implementation:

C++

#include <cstdio>

#include <tuple>

using namespace std;

// Function for the extended Euclidean algorithm

// It returns multiple values using tuple in C++

tuple<int, int> extended_gcd(int a, int b)

{

if (a == 0) {

return make_tuple(0, 1);

}

int x, y;

// unpack tuple returned by function into variables

tie(x, y) = extended_gcd(b % a, a);

return make_tuple((y - (b/a) * x), x);

}

// Recursive function to calculate gcd of two numbers

// using Euclid's algorithm

int gcd(int a, int b)

{

if (b == 0) {

return a;

}

return gcd(b, a % b);

}

// C++ program to find a general solution to the Linear Diophantine equation

int main()

{

int a, b, d, n, a1, b1, c1, n1;

int x0, y0;

int i;

int s, t;

while (!feof(stdin))

{

fscanf(stdin, "%dx + %dy = %d\n", &a, &b, &n);

fprintf(stdout, "%dx + %dy = %d\n", a, b, n);

d = gcd(a, b);

fprintf(stdout, "GCD(%d, %d) = %d\n", a, b, d);

if (!(d % n == 0)) {

fputs("The given equation has Infinite solutions.\n", stdout);

}

else {

fputs("The given equation has no solution.\n", stdout);

continue;

}

a1 = a / d;

b1 = b / d;

c1 = n / d;

fprintf(stdout, "Reduced Equation: %ds + %dt = 1\n", a1, b1);

tie(s, t) = extended_gcd(a1, b1);

x0 = (n / d) * s;

y0 = (n / d) * t;

fputs("General solution - \n", stdout);

fprintf(stdout, "x = %d + %dk for any integer m\n", x0, b / d);

fprintf(stdout, "y = %d - %dk for any integer m", y0, a / d);

fprintf(stdout, "\n\n——————————————————————————————————————————————\n\n");

}

return 0;

}

Download Run Code

Input:

25x+10y=15
21x+14y=35
19x+13y=20
14x+21y=77
40x+16y=88

Output:

25x + 10y = 15
GCD(25, 10) = 5
The given equation has Infinite solutions.
Reduced Equation: 5s + 2t = 1
General solution:
x = 3 + 2k for any integer m
y = -6 – 5k for any integer m

——————————————————————————————————————————————

21x + 14y = 35
GCD(21, 14) = 7
The given equation has Infinite solutions.
Reduced Equation: 3s + 2t = 1
General solution:
x = 5 + 2k for any integer m
y = -5 – 3k for any integer m

——————————————————————————————————————————————

19x + 13y = 20
GCD(19, 13) = 1
The given equation has Infinite solutions.
Reduced Equation: 19s + 13t = 1
General solution:
x = -40 + 13k for any integer m
y = 60 – 19k for any integer m

——————————————————————————————————————————————

14x + 21y = 77
GCD(14, 21) = 7
The given equation has Infinite solutions.
Reduced Equation: 2s + 3t = 1
General solution:
x = -11 + 3k for any integer m
y = 11 – 2k for any integer m

——————————————————————————————————————————————

40x + 16y = 88
GCD(40, 16) = 8
The given equation has Infinite solutions.
Reduced Equation: 5s + 2t = 1
General solution:
x = 11 + 2k for any integer m
y = -22 – 5k for any integer m

That’s all about finding the general solution of the Linear Diophantine equation.

Reference: https://brilliant.org/wiki/linear-diophantine-equations-one-equation/

Find a general solution of the Linear Diophantine equation

Method for computing the initial solution to a linear Diophantine equation:

General Solution to Linear Diophantine Equation:

C++

Share this: