方程“a + bx = c + dy'的积分解 [英] Integral solution to equation `a + bx = c + dy`

问题描述

在方程 a + bx = c + dy 中，所有变量都是整数。 a ， b ， c c> d 。如何找到 x 和 y 的整体解决方案？如果我想是正确的，将有无限数量的解决方案，由 b 和 d ，但我需要的只是一个解决方案，我可以计算其余的。下面是一个例子：

  a = 2 
b = 3 
c = 4 
d = 5 
a + bx：（2,5,8,11,14）
c + dy：（4,9,14,19,24）
 
a + bx相交c + dy 14，so：
x = 4 
y = 2 
  

m循环通过 x 的整数值，直到找到 y （伪代码）的整数值：

  function integer_solution（int a，int b，int c，int d）{
 // a + bx == c + dy 
 //（a + bx  -  c）/ d == y 
 
 //一些参数可能没有整数解，
 //例如如果b == d和a  -  c）％b！= 0 
 //如果我们在x == d之前没有解，没有。 
 
 int x = 0; 
 while（x< d）
 {
 if（（a + bx  -  c）％d == 0）
 {
 return [x， + bx-c）/ d]; 
} 
 x ++; 
} 
 return false; 
} 
  

我觉得有更好的方法。有没有办法找到x和y没有循环？我使用C ++，如果这是重要的。

解决方案

查找整数 x 和 y （其中一个通常为负）满足Bézout的身份

您的回答是：

a = k * x ，
b = k * y ，$对于任何整数 k ，b $ b c - a = k * gcd（a，b）。

（附注：这也适用于任何其他欧几里德域，即多项式环每个欧几里得域名都是唯一因子分解域）。您可以使用迭代方法找到这些解决方案：

---

迭代方法

通过扩展和分组术语的常规代数（请参阅的最后一部分前面提到的维基百科条款），获得迭代方法的以下算法：

• 1。应用欧几里得算法，并让qn（n从1开始）是商中的商的有限列表。


• 2。初始化x0，x1为1，0，y0，y1分别为0,1。
  
  
  
  
  • 2.1然后对于每个i，只要qi被定义，
  
  
  • 2.2计算xi + 1 = xi-1 - qixi
  
  
  • 2.3计算yi + 1 = yi-1 - qiyi
  
  
  • 2.4在将i递增1后重复上述操作。
  
  


• 3。答案是xn和yn的倒数第二个。

伪代码：

  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  - 商* x，x）
（y，lasty）：=（lasty  -  quotient * y，y）
 return（lastx，lasty）
  

所以我写了一个示例算法，使用欧氏算法迭代法计算非最小公约数非负 code>和 b （对于否定 - 需要这些额外的步骤），它返回GCD并存储 x 和 y 在通过引用传递给它的变量中：

  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<< \\\
q：; 
 for（it = q.begin（）; it！= q.end（）; it ++）{std :: cout< * it< ，; } 
 std :: cout<< \\\
x：; 
 for（it = x_coeff.begin（）; it！= x_coeff.end（）; it ++）{std :: cout< * it<<，;} 
 std :: cout<< \\\
y：; 
 for（it = y_coeff.begin（）; it！= y_coeff.end（）; it ++）{std :: cout< * it<<，;} 
 return a; 
} 
  



通过传递示例来自wikipedia for a = 120 和 b = 23 我们获得：

  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，

对于这个例子，根据给定的表格是什么：

In the equation a + bx = c + dy, all variables are integers. a, b, c, and d are known. How do I find integral solutions for x and y? If I'm thinking right, 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's 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'm looping through integral values of x until I find an 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 like there's a better way to do this. Is there any way to find x and y without a loop? I'm using C++, if that's of any importance.

解决方案

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

with a=z' and b=z'' and the equation has an infinite number of solutions. So instead of trial searching method you can check if c is the greatest common divisor (GCD) of a and b (in your case this translates into bx - dy = c - a)

If indeed a and b are multiples of c then x and y can be computed using extended Euclidean algorithm which finds integers x and y (one of which is typically negative) that satisfy Bézout's identity

and your answer is:

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

(as a side note: this holds also for any other Euclidean domain, i.e. polynomial ring & every Euclidean domain is unique factorization domain). You can use Iterative Method to find these solutions:

---

Iterative method

By routine algebra of expanding and grouping like terms (refer to last section of wikipedia article mentioned before), the following algorithm for iterative method is obtained:

• 1 . Apply Euclidean algorithm, and let qn (n starts from 1) be a finite list of quotients in the division.
• 2 . Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
  • 2.1 Then for each i so long as qi is defined,
  • 2.2 Compute xi+1 = xi−1 − qixi
  • 2.3 Compute yi+1 = yi−1 − qiyi
  • 2.4 Repeat the above after incrementing i by 1.
• 3 . The answers are the second-to-last of xn and yn.

pseudocode:

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 have written example algorithm which calculates greatest common divisor using Euclidean Algorithm iterative method for non-negative a and b (for negative - these extra steps are needed), it returns GCD and stores solutions for x and y in 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;
} 

by passing to it an example from wikipedia for a = 120 and b = 23 we obtain:

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,

what is in accordance with the given table for this example:

这篇关于方程“a + bx = c + dy'的积分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！