18.11 Lab: Linear diophantine equations

In this program, you will be solving linear Diophantineequations 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 alsobe integers.

See the following entry in Wikipedia: Linear Diophantineequations.

You will be solving this using the recursive version of theExtended Euclidean algorithm for finding the integers x and y inBezout'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 justdivide 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 andsolve 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 theremainder (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 smallercoefficients:

bu + rv = c

with u = qx + y and v = x.

Finally, you recursively call your function on this simplerversion of the original problem. Don't forget that this recursivecall will actually solve for u and v in this case, so you stillhave to solve for x and y to get the solution to the originalproblem:

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 Diophantinefunction.

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?