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

**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 if 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 Equations –

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

**Theorem:**

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

for some integer m.

## 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 |
#include <cstdio> #include <tuple> using namespace std; // Function for 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 general solution of 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; } |

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

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

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply