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/

 
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

Notify of
avatar
wpDiscuz