Integral solution of the equation a + bx = c + dy`

Question

In the equation a + bx = c + dy all variables are integers. a , b , c and d . How to find integral solutions for x and y ? If I think correctly, there will be an infinite number of solutions, separated by the lowest common multiple of b and d , but all I need is one solution and I can calculate the rest. Here is an example:

 a = 2 b = 3 c = 4 d = 5 a + bx: (2, 5, 8, 11, 14) c + dy: (4, 9, 14, 19, 24) a + bx intersects c + dy at 14, so: x = 4 y = 2 

Right now, I am looping through the integral values ​​of x until I find the integral value for y (pseudocode):

 function integral_solution(int a, int b, int c, int d) { // a + bx == c + dy // (a + bx - c) / d == y // Some parameters may have no integral solution, // for example if b == d and (a - c) % b != 0 // If we don't have a solution before x == d, there is none. int x = 0; while (x < d) { if ((a + bx - c) % d == 0) { return [x, (a + bx - c) / d]; } x++; } return false; } 

I feel that there is a better way to do this. Is there a way to find x and y without a loop? I use C ++ if that matters.

Answer 1

Linear diophantine equations take the form ax + by = c . If c is the greatest common factor of a and b , it means a=z'c and b=z''c , then this is a Bézout identity of the form

with a=z' and b=z'' , and the equation has an infinite number of solutions. Therefore, instead of the trial search method, you can check if c is the greatest common factor (GCD) a and b (in your case, this means bx - dy = c - a )

If indeed a and b are multiples of c , then x and y can be computed using an extended Euclidean algorithm that finds integers x and y (one of which is usually negative) that satisfy the Bézout identifier

and your answer:

a = k*x b = k*y c - a = k * gcd(a,b) for any integer k .

(as a note: this applies to any other Euclidean domain , that is, a ring of polynomials and each Euclidean domain has a unique factorization domain ). You can use the Iterative method to find these solutions:

---

Iterative method

According to the usual algebra of decomposition and grouping of similar terms (see the last section of the wikipedia article mentioned above), the following iterative method algorithm is obtained:

• 1. Apply the Euclidean algorithm and let qn (n begin with 1) be a finite list of quotients in division.
• 2. Initialize x0, x1 as 1, 0 and y0, y1 as 0.1, respectively.
  • 2.1 Then for each i, while qi is defined,
  • 2.2 Calculate xi + 1 = xi-1 - qixi
  • 2.3. Calculate yi + 1 = yi-1 - qiyi
  • 2.4 Repeat the above after increasing by 1.
• 3. The responses are the second last of xn and yn.

pseudo code:

 function extended_gcd(a, b) x := 0 lastx := 1 y := 1 lasty := 0 while b ≠ 0 quotient := a div b (a, b) := (b, a mod b) (x, lastx) := (lastx - quotient*x, x) (y, lasty) := (lasty - quotient*y, y) return (lastx, lasty) 

So, I wrote an example algorithm that calculates the largest common factor using the iterative method of the Euclidean algorithm for non-negative a and b (for negative ones these extra steps), it returns GCD and saves the solutions for x and y in the variables passed to it by reference:

 int gcd_iterative(int a, int b, int& x, int& y) { int c; std::vector<int> r, q, x_coeff, y_coeff; x_coeff.push_back(1); y_coeff.push_back(0); x_coeff.push_back(0); y_coeff.push_back(1); if ( b == 0 ) return a; while ( b != 0 ) { c = b; q.push_back(a/b); r.push_back(b = a % b); a = c; x_coeff.push_back( *(x_coeff.end()-2) -(q.back())*x_coeff.back()); y_coeff.push_back( *(y_coeff.end()-2) -(q.back())*y_coeff.back()); } if(r.size()==1) { x = x_coeff.back(); y = y_coeff.back(); } else { x = *(x_coeff.end()-2); y = *(y_coeff.end()-2); } std::vector<int>::iterator it; std::cout << "r: "; for(it = r.begin(); it != r.end(); it++) { std::cout << *it << "," ; } std::cout << "\nq: "; for(it = q.begin(); it != q.end(); it++) { std::cout << *it << "," ; } std::cout << "\nx: "; for(it = x_coeff.begin(); it != x_coeff.end(); it++){ std::cout << *it<<",";} std::cout << "\ny: "; for(it = y_coeff.begin(); it != y_coeff.end(); it++){ std::cout << *it<<",";} return a; } 

passing him an example from wikipedia for a = 120 and b = 23 , we get:

 int main(int argc, char** argv) { // 120x + 23y = gcd(120,23) int x_solution, y_solution; int greatestCommonDivisor = gcd_iterative(120, 23, x_solution, y_solution); return 0; } 

r: 5,3,2,1,0,

q: 5,4,1,1,2,

x: 1,0,1, -4,5, -9,23,

y: 0.1, -5.21, -26.47, -120,

which corresponds to this table for this example: