Thuật Toán Euclid Mở Rộng – Extended Euclid Algorithm

Có thể bạn quan tâm

maxresdefault

Tác giả: Huỳnh Văn Duy

Có thể nói trong lập trình tính toán thì các bài toán về số học chiếm một phần khá lớn. Trong đó, một trong những thuật toán được biết đến nhiều nhất là Giải thuật euclid mở rộng, thuật toán này có thể giải quyết rất nhiều bài toán liên quan đến số học. Nên hôm nay chúng ta sẽ tìm hiểu về nó.

ĐẦU TIÊN TA CẦN TÌM HIỂU MỘT CHÚT VỀ THUẬT TOÁN EUCLID NGUYÊN THỦY

Lịch sử thuật toán Euclid:

Thuật toán Euclid là một trong những thuật toán cổ nhất được biết đến, từ khi nó xuất hiện trong cuốn Euclid’s Elements khoảng năm 300 trước công nguyên. Euclid khởi đầu đã trình bày rõ ràng vấn đề về phương diện hình học, như vấn đề tìm ra một thước đo chung cho độ dài hai đường thẳng, và thuật toán của ông đã xử lý bằng cách lặp lại phép trừ đoạn dài hơn cho đoạn ngắn hơn. Tuy nhiên, thuật toán đã hầu như không được phát hiện ra bởi Euclid và nó đã có thể được biết đến sớm hơn 200 năm. Nó cũng đã được biết đến bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên).

Mô tả thuật toán:

Cho 2 số tự nhiên a và b, không đồng thời bằng 0: kiểm tra nếu b bằng 0, thì a là ước chung lớn nhất (UCLN). Nếu không, lặp lại xử lý sử dụng b và phần còn lại sau khi lấy a chia cho b. Phần còn lại sau khi chia a cho b thường được viết là a mod b.

Các thuật toán này có thể sử dụng trong bất kì hoàn cảnh nào khi còn phần dư. Điều này bao gồm các nhóm đa thức như nhóm số nguyên Gauxơ. Thuật toán không chỉ áp dụng cho số tự nhiên mà còn áp dụng cho nhiều trường hợp tổng quát khác sẽ được mô tả chi tiết sau.

Thuật toán có thể được cài đặt rất đơn giản:

#include <iostream> #include <algorithm> using namespace std; #define builtin_gcd __gcd int gcd(int a, int b) { if(b==0) return a; else return gcd(b,a%b); } int main() { cout << gcd(252,105) << endl; cout << builtin_gcd(252,105) << endl; return 0; }

Dĩ nhiên, ngôn ngữ lập trình C++ cũng cung cấp cho chúng ta một hàm có sẵn để tìm ước chung lớn nhất của hai số bằng thuật toán euclid, đó là hàm __gcd(a, b) sẽ trả về ước chung lớn nhất của hai số a và b.

THUẬT TOÁN EUCLID MỞ RỘNG

Phương trình diophantine: $ax+by=c$ (1)

Theo định lí Bézout (Bézout’s indentify): Cho hai số nguyên a, b khi đó luôn tồn tại hai số x, y sao cho: $ax + by = gcd(a, b)$

Người ta cũng chứng minh được phương trình trên có nghiệm khi và chỉ khi gcd(a, b) = c. Và như thế có nghĩa là phương trình diophante có thể có vô số nghiệm, và từ mỗi một nghiệm ta có thể sinh ra những nghiệm khác.

Định nghĩa số nguyên k sao cho: $c = gcd(a, b)k$ . Chia vế theo vế phương trình $(1)$ cho $k$ ta được phương trình mới

$as + bt = gcd(a, b) <=> a(sk) + b(tk) = gcd(a,b)k = c$ (2)

Dễ thấy $x = sk$ và $y = tk$ chính là một nghiệm của phương trình (1). Giả sử $x_{1}, y_{1}$ là một nghiệm khác của phương trình (1), ta có:

$a(x_{1} - x) + b(y_{1} - y) = 0$

Suy ra: $a(x_{1} - x) = b(y_{1} - y)$ (3), nghĩa là a là ước của $b(y - y_{1})$ , và $frac{a}{gcd(a, b)}$ là ước của $y - y_{1}$ . Nên ta có: $y = y_{1} + rfrac{a}{gcd(a, b)}$ với r là một số nguyên. Thay vào (3), ta được:

$a(x_{1} - x)=rb(\frac{a}{gcd(a, b)})$

Trong đó:

$gcd(a, b)a(x_{1} - x) = rba$

hay $x = x_{1} - r\frac{b}{gcd(a, b)}$

Như vây, nếu $ax_{1} + by_{1} = c$ có một nghiệm bất kì thì tất cả các nghiệm sẽ có dạng:

$x = x_{1} - r\frac{b}{gcd(a, b)}, y = y_{1} + r\frac{a}{gcd(a, b)}$

Ví dụ: Tìm tất cả các nghiệm của phương trình $258x + 147y = 369$ .

Đầu tiên, ta xét $gcd(258, 147) = 3$ , vì $369 \vdots 3$ nên phương trình chắc chắn có nghiệm.
Áp dụng thuật toán Euclid, ta có:
- $258 = 147(1) + 111$
- $147 = 111(1) + 36$
- $111 = 36(3) + 3$
- $36 = 3(12)$
Bây giờ, ta tìm cách biểu diễn 3 bằng một mối quan hệ tuyến tính giữa 258 và 147. Dựa vào trên, ta có:
- $3 = 111 - 36(3)$
- $= 111 - 3(147 - 111)$
- $= 4(111) - 3(147)$
- $= 4(258 - 147) - 3(147)$
- $= 4(258) - 7(147)$
Tiếp theo, ta viết , và nhân phương trình cho 123 vì . Ta được:
- $258(492) + 147(-861)= 369$ .
Vậy một nghiệm của phương trình là: , và các nghiệm khác có dạng:
- $x = 492 - \frac{147r}{3} = 492 - 49r,$
- $y = -861 + \frac{258r}{3} = 86r - 861$ $(r\in \mathbb{Z})$

Cài đặt cụ thể:

// Extended euclid solve diophantine linear equation #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long ll; typedef pair<int, int> ii; ll a, b, c; ii extended_gcd(ll a, ll b) { if (b == 0) return ii(1, 0); ii qr = ii(a / b, a % b); ii st = extended_gcd(b, qr.y); return ii(st.y, st.x - qr.x*st.y); } void extended_gcd2(ll a, ll b, ll &X, ll &Y) { // another version ll d = __gcd(a, b); ll m = a, n = b; ll xm = 1; // (ym = 0) m = a = a*1 + b*0 ll xn = 0; // (yn = 1) n = a = a*0 + b*1 while (n) { ll q = m / n; ll r = m - q*n; ll xr = xm - q*xn; m = n, xm = xn; n = r, xn = xr; } X = xm * (c/d); Y = ((d - a*xm) / b) * (c/d); } int main() { freopen("in.txt", "r", stdin); scanf("%lld %lld %lld", &a, &b, &c); ll d = __gcd(a, b); ii ex = extended_gcd(a, b); printf("%lld %lldn", c/d*ex.x, c/d*ex.y); ll X, Y; extended_gcd2(a, b, X, Y); printf("%lld %lldn", X, Y); assert(c/d*ex.x == X && c/d*ex.y == Y); return 0; }

NGHỊCH ĐẢO MODULO

Một trong những ứng dụng quan trọng nhất của thuật toán Euclid mở rộng đó chính là dùng để tìm nghịch đảo modulo: $a^{-1}\equiv x \;(mod \; m)$ Nhận xét: nếu $gcd(a, m) = 1$ , giải phương trình $ax + my = 1$

Ta có:

$ax - 1 = -my \; \vdots m$
$ax = 1 \; ( \mod m)$

Khi đó $x$ được gọi là nghịch đảo của a theo modulo m (ký hiệu $x = a^{-1}$ )

Ví dụ: a = 7, m = 10, Xét phương trình $7x + 10y = 1$

Nghiệm $7 \times 3 + 10 \times + (-2) = 1$

Khi đó: $3 = 7^{-1} \; (\mod 10)$

TỔNG KẾT:

Thuật toán Euclid mở rộng có thể dùng để giải phương trình Diophantine $ax + by = c$
Họ nghiệm của phương trình Diophantine khi đã có nghiệm x, y là:
- $a \times (x + k \times \frac{LCM(a, b)}{a}) + b \times (y - k \times \frac{LCM(a, b)}{b}) = c, \; \forall k \in \mathbb{Z}$

BONUS: ĐỊNH LÍ THẶNG DƯ TRUNG HOA (CHINESE REMAINDER THEOREM)

Định lý thặng dư Trung Hoa là tên người phương tây đặt cho định lý này. Người Trung Hoa gọi nó là bài toán Hàn Tín điểm binh. Hàn Tín là một danh tướng thời Hán Sở, từng được phong tước vương thời Hán Cao Tổ Lưu Bang đang dựng nghiệp. Sử ký Tư Mã Thiên viết rằng Hàn Tín là tướng trói gà không nổi, nhưng rất có tài quân sự. Tục truyền rằng khi Hàn Tín điểm quân số, ông cho quân lính xếp hàng 3, hàng 5, hàng 7 rồi báo cáo số dư. Từ đó ông tính chính xác quân số đến từng người.

Gần đây, định lý số dư Trung Quốc có nhiều ứng dụng trong các bài toán về số nguyên lớn áp dụng vào Lý thuyết mật mã. – Wikipedia

Bản chất của bài toán Hàn Tín điểm binh là giải phương trình đồng dư bật nhất được mô tả tổng quát như sau:

Cho các số nguyên:

$a_{1}, a_{2}, ... , a_{k}$
$b_{1}, b_{2}, ... , b_{k}$ : đôi một nguyên tố cùng nhau
Tìm sao cho:
- $x \equiv a_{1} \; (\mod b_{1})$
- $x \equiv a_{2} \; (\mod b_{2})$
- $...$
- $x \equiv a_{k} \; (\mod b_{k})$

Đặt:

$M = b_{1} \times b_{2} \times ... \times b_{k}$
$p_{i} = M/b_{i}$
Nhận xét: $gcd(p_{i}, b_{i}) = 1$
Tính $q_{i} = p_{i}^{-1} \; (\mod b_{i})$

Chỉ ra một nghiệm: $x = \sum _{i = 1} ^{k} (a_{i} p_{i} q_{i})$

$a_{i} p_{i} q_{i} \mod b_{j} = 0$ với mọi $i \neq j$ do $p_{i} \mod b_{j} = 0$
$a_{i} p_{i} q_{i} \mod b_{j} = a_{j}$ do $p_{j} q_{j} \mod b_{j} = 1$
$\rightarrow ( \sum _{i = 1} ^{k} (a_{i} p_{i} q_{i}) \mod b_{j} = a_{j}$ với mọi j.
Họ nghiệm: $x \equiv \sum _{i = 1} ^{k} (a_{i} p_{i} q_{i}) \; (\mod M)$