Question
In this PROGRAM, you will be solving linear Diophantine equations recursively. A linear Diophantine equation is an equation in the form: ax + by =
In this PROGRAM, you will be solving linear Diophantine equations recursively.
A linear Diophantine equation is an equation in the form:
ax + by = c
where a, b, and c are all integers and the solutions will also be integers.
See the following entry in Wikipedia: Linear Diophantine equations.
You will be solving this using the recursive version of the Extended Euclidean algorithm for finding the integers x and y in Bezout's identity:
ax + by = gcd(a,b)
Required Recursive Function
/* Returns true if a solution was found and false if there is no solution. x and y will contain a solution if a solution was found. This function will NOT output anything. */ bool diophantine(int a, int b, int c, int &x, int &y);
Basic Algorithm
If gcd(a,b) does not divide c, then there is no solution.
If b divides a (the remainder of a / b is 0), then you can just divide by b to get the solution: x = 0, y = c / b.
Otherwise (b does not divide a), through a substitution method, we can come up with a simpler version of the original problem and solve the simpler problem using recursion.
Substitution method
ax + by = c
Now, we can define a as:
a = bq + r
where q is (a / b) (using integer division) and r is the remainder (a % b).
Substituting (bq + r) in for a now:
(bq + r)x + by = c
which is the same as
b(qx + y) + rx = c
and now we have the equation in the same form, only with smaller coefficients:
bu + rv = c
with u = qx + y and v = x.
Finally, you recursively call your function on this simpler version of the original problem. Don't forget that this recursive call will actually solve for uand v in this case, so you still have to solve for x and y to get the solution to the original problem:
x = v y = u - qx
Linear Diophantine Example
https://docs.google.com/document/d/1NXw2edGf2e4Yoj2uylYiandqvVVUQJlhf9S4PVfxIcY/edit
Input/Output Test Samples
Here are some examples you can test your function on:
| Input (a b c) | Results (x y) | ------------------ | ------------ | 28 7 490 | 0 70 | 1024 96 2048 | -64 704 | 11 11 2010 | No solution! | 1984 3070 1 | No solution! | 395 252 1 | -37 58 | 25 38 2 | -6 4 | 200 -2 4 | 0 -2 | 25 75 100 | 4 0 | 25 75 1000 | 40 0 | 25 75 1 | No solution! | -10 -10 100 | 0 -10 | 12 24 48 | 4 0 | 5 -29 6 | 36 6
Use this main function to test your function.
int main() { int a, b, c, x, y; cout << "Enter a b c" << endl; cin >> a >> b >> c; cout << endl; cout << "Result: "; if (diophantine(a, b, c, x, y)) { cout << x << " " << y << endl; } else { cout << "No solution!" << endl; } return 0; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started