In this PROGRAM, you will be solving linear Diophantine equations recursively. A
ID: 3832359 • Letter: I
Question
In this PROGRAM, you will be solving linear Diophantine equations recursively.
A linear Diophantine equation is an equation in the form:
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:
Required Recursive Function
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
Now, we can define a as:
where q is (a / b) (using integer division) and r is the remainder (a % b).
Substituting (bq + r) in for a now:
which is the same as
and now we have the equation in the same form, only with smaller coefficients:
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:
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:
Use this main function to test your function.
Explanation / Answer
/**
C++ program that prompts user to enter a , b and c values and
prints x and y values if exists using linear Diophantine equation
otherwise print no solution.
*/
//program.cpp
#include<iostream>
using namespace std;
//function prototypes
bool diophantine(int a, int b, int c, int &x, int &y);
int gcd(int a, int b);
int main()
{
//declare integer variables
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;
}
//pause program output on console
system("pause");
return 0;
}
/*
The function diophantine that takes three integer values by pass by value
and two integer values pass by reference and finds the solution of the
equation ax+by=c using linear Diophantine equation.
*/
bool diophantine(int a, int b, int c, int &x, int &y)
{
// q is the quotient between a and b, r is the remainder
int quotient, remainder, u, v;
bool result = false;
//calculate remainder
remainder = a % b;
//calculate quotient
quotient = a / b;
// Uses gcd() function to determine greatest common factor.
if(c % gcd(a,b) == 0)
{
//case -1:
if(a % b == 0)
{
x = 0;
y = c/b;
return true;
}
//case -2:
else if(b % a == 0)
{
y = 0;
x = c/a;
return true;
}
else
{
//recursive calling
//calling the function. diophantine
result = diophantine(b, a % b, c, u, v);
//update x and y values
x = v;
y = u - (a/b) * x;
}
}
return result;
}
/*
The gcd method that takes two integers and returns the
greatest common divisior of two integer a and b.
*/
int gcd(int a, int b)
{
if ( a==0 )
return b;
return gcd ( b%a, a );
}
Sample Output:
Enter a b c
28 7 490
Result: 0 70
Sample Output:
Enter a b c
25 75 1
Result: No solution!