Question

18.11 Lab: Linear diophantine equations

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 u and 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

Example showing steps of algorithm: Link

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

main function

Use the given main() function to test your Diophantine 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;
}

Can anyone help please?

Answer 1

Here is the code with comments

# include <iostream>
using namespace std;

bool diophantine(int a, int b, int c, int &x, int &y) {
//base case when
//a is divisible by b
if (a % b == 0) {
//the gcd is b
//hence check if c is divisble by b
if (c % b == 0) {
//return the answers
//from the base case
x = 0;
y = c / b;
return true;
} else {
return false;
}
}

//call recursively
if (diophantine(b, a % b, c, x, y)) {
//if successful
//use the recursive formula
int u = x;
int v = y;
int q = a / b;
x = v;
y = u - q*x;
return true;
} else {
return false;
}
}

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;
}

Here is a screenshot of outputs:

Comment in case of any doubts.