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

Linear Diophantine Equation Theorem

for some integer m.

C++

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

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

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

avatar
  Subscribe  
Notify of