# Find general solution of Linear Diophantine equation

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.

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

1. Use the Euclidean algorithm to compute gcd(a, b) = d.
2. Determine if d | n. If not, then there are no solutions.
3. Reformat the equations from the Euclidean algorithm.
4. Using substitution, go through the steps of the Euclidean algorithm to find a solution to the equation axi + byi = d
5. The initial solution to the equation ax + by = n is the ordered pair (xi . n/d, yi . 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++

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

(1 votes, average: 5.00 out of 5)