Thuật toán Bezout

Định lý Bezout

Với a, b thuộc N, 1 <= b < a ta có:

a. Tồn tai x, y thuộc Z sao cho a.x + b.y = gcd (a, b) Ước chung lớn nhất (Greatest common divisor).

b. (a, b) = 1 khi và chỉ khi tồn tại x, y thuộc Z: a.x + b.y = 1

Thuật toán Bezout

Input: a, b thuộc N, 0 <= b < a.

Output: d = gcd(a, b) và x, y thuộc Z: a.x + b.y = d.

1. Nếu b = 0 thì d = a, x = 1, y = 0;

2. Khởi tạo: x1 = 0; x2 = 1; y1 = 1, y2 = 0;

3. while( b >0)
{
i. q -= a/b; r = a – q.b; x = x2 – x1.q; y = y2 – y1.q;

i.i. a = b; b = r; x2 = x1; x1 = x; y2 = y1; y1 = y;
}

d = a;

x = x2;

y = y2;

return (d, x, y).

Cài đặt thuật toán

Tạo 1 struct để lưu kết quả trả về như sau:

struct bezout_t

{
    int d;

    int x;

    int y;

};

Đây là phần cài đặt thuật toán:

bezout_t Bezout(int a, int b)
{
 bezout_t result;
 int x1 = 0, x2 = 1, y1 = 1, y2 = 0, x = 0, y = 0, r = 0, q = 0;
 if (b == 0)
 {
  result.d = a;
  result.x = 1;
  result.y = 0;
 }
 while (b > 0)
 {
  q = a / b;
  r = a - b * q;
  x = x2 - x1 * q;
  y = y2 - y1 * q;
  
  a = b;
  b = r;
  x2 = x1;
  x1 = x;
  y2 = y1;
  y1 = y;
 }
 result.d = a;
 result.x = x2;
 result.y = y2;
 return result;
}