Thuật Toán Euclid Mở Rộng: Phương Trình Diophantine và Nghịch Đảo
Thuật toán Euclid cổ điển tìm ước chung lớn nhất \(\gcd(a, b)\) là một trong những thuật toán lâu đời nhất và thanh lịch nhất trong lịch sử toán học nhân loại. Tuy nhiên, trong lập trình thi đấu và lý thuyết số hiện đại, chỉ biết giá trị \(\gcd(a, b)\) thôi là chưa đủ. Chúng ta thường xuyên cần tìm một cặp số nguyên \((x, y)\) thỏa mãn hệ thức Bézout:
\[a \cdot x + b \cdot y = \gcd(a, b)\]
Phương trình này là dạng cơ bản nhất của Phương trình Diophantine tuyến tính. Không dừng lại ở đó, thuật toán giải phương trình này — mang tên Thuật toán Euclid mở rộng (Extended Euclidean Algorithm) — chính là nền tảng để tìm phần tử nghịch đảo modulo trong trường hợp tổng quát khi số chia modulo \(M\) là một hợp số bất kỳ, nơi mà Định lý Fermat nhỏ hoàn toàn bất lực.
Bài viết này sẽ giải thích chi tiết nguyên lý toán học của thuật toán Euclid mở rộng, minh họa quá trình lần ngược từng bước trên số liệu cụ thể, và cung cấp mã nguồn chuẩn giúp bạn ứng dụng thuần thục trong các bài thi HSG Quốc gia và ICPC.
1. Định lý Bézout và Nguyên lý thuật toán Euclid mở rộng
Đồng nhất thức Bézout (Bézout's Identity)
Định lý Bézout phát biểu rằng: Với hai số nguyên \(a\) và \(b\) không đồng thời bằng 0, luôn tồn tại ít nhất một cặp số nguyên \(x\) và \(y\) sao cho: \[a \cdot x + b \cdot y = \gcd(a, b)\]
Cặp số \((x, y)\) này được gọi là hệ số Bézout. Đáng chú ý, nếu \((x_0, y_0)\) là một nghiệm riêng, thì phương trình có vô số nghiệm nguyên tổng quát được xác định bởi: \[x = x_0 + k \cdot \frac{b}{\gcd(a, b)}, \quad y = y_0 - k \cdot \frac{a}{\gcd(a, b)} \quad (k \in \mathbb{Z})\]
Xây dựng công thức truy hồi
Xét phép chia có dư của \(a\) cho \(b\): \[a = q \cdot b + r \quad \text{với } q = \lfloor a / b \rfloor, \; r = a \pmod b\]
Thuật toán Euclid chuyển bài toán từ cặp \((a, b)\) sang cặp \((b, a \pmod b)\). Giả sử ta đã đệ quy tìm được nghiệm \((x_1, y_1)\) cho bài toán con: \[b \cdot x_1 + (a \pmod b) \cdot y_1 = \gcd(b, a \pmod b) = \gcd(a, b)\]
Thay \(a \pmod b = a - \lfloor a / b \rfloor \cdot b\) vào phương trình trên: \[b \cdot x_1 + (a - \lfloor a / b \rfloor \cdot b) \cdot y_1 = \gcd(a, b)\] Nhóm lại theo \(a\) và \(b\): \[a \cdot y_1 + b \cdot (x_1 - \lfloor a / b \rfloor \cdot y_1) = \gcd(a, b)\]
So sánh với phương trình ban đầu \(a \cdot x + b \cdot y = \gcd(a, b)\), ta rút ra ngay công thức cập nhật nghiệm: \[x = y_1\] \[y = x_1 - \lfloor a / b \rfloor \cdot y_1\]
Điều kiện dừng đệ quy
Khi \(b = 0\), ta có phương trình: \[a \cdot x + 0 \cdot y = \gcd(a, 0) = a\] Phương trình này có nghiệm hiển nhiên là: \[x = 1, \quad y = 0\] Từ điều kiện dừng này, thuật toán quay lui và lần ngược công thức trên để tính ra \((x, y)\) cho bài toán ban đầu trong thời gian \(O(\log \min(a, b))\).
2. Ứng dụng đột phá: Tìm nghịch đảo Modulo khi M là hợp số
Trong bài toán tìm nghịch đảo modulo: \[a \cdot x \equiv 1 \pmod m\] Định nghĩa này tương đương với tồn tại số nguyên \(y\) sao cho: \[a \cdot x - m \cdot y = 1 \iff a \cdot x + m \cdot (-y) = 1\]
Phương trình này chỉ có nghiệm khi và chỉ khi \(\gcd(a, m) = 1\). Khi đó, gọi hàm extgcd(a, m, x, y), ta thu được giá trị \(x\).
Do \(x\) có thể là số âm, ta chuẩn hóa về khoảng \([0, m - 1]\) bằng công thức quen thuộc:
\[x_{\text{ans}} = (x \pmod m + m) \pmod m\]
Điểm vượt trội: Định lý Fermat nhỏ \(a^{m-2} \pmod m\) chỉ áp dụng được khi \(m\) là số nguyên tố. Khi \(m\) là hợp số (ví dụ \(m = 10^9\)), thuật toán Euclid mở rộng tìm được nghịch đảo trong thời gian \(O(\log m)\) mà không cần biết gì thêm về \(m\). Cách dùng định lý Euler, tính \(a^{\phi(m) - 1} \bmod m\) bằng lũy thừa nhị phân, cũng chạy trong \(O(\log m)\) nhưng phải tính \(\phi(m)\) trước, tức là phải phân tích \(m\) ra thừa số nguyên tố.
Chủ đề này nằm trong Buổi 10 - Modular Inverse & Combinatorics của Tài năng lập trình. Xem đề cương
3. Cài đặt C++17 và Python 3 chuẩn thi đấu
Cài đặt C++17
#include <iostream>
using namespace std;
// Giai phuong trinh a * x + b * y = gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long d = extgcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
// Tim nghich dao modulo a^-1 mod m (khi gcd(a, m) = 1)
long long modInverse(long long a, long long m) {
long long x, y;
long long g = extgcd(a, m, x, y);
if (g != 1) return -1; // Khong ton tai nghich dao neu gcd > 1
return (x % m + m) % m;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Test extgcd: a = 35, b = 15 -> gcd = 5, x = 1, y = -2
long long a = 35, b = 15, x, y;
long long g = extgcd(a, b, x, y);
cout << g << ' ' << x << ' ' << y << '\n';
// Test modInverse: 3^-1 mod 11 = 4 (vi 3 * 4 = 12 = 1 mod 11)
cout << modInverse(3, 11) << '\n';
return 0;
}
Cài đặt Python 3
import sys
def extgcd(a: int, b: int) -> tuple[int, int, int]:
if b == 0:
return a, 1, 0
d, x1, y1 = extgcd(b, a % b)
x = y1
y = x1 - y1 * (a // b)
return d, x, y
def modInverse(a: int, m: int) -> int:
g, x, y = extgcd(a, m)
if g != 1:
return -1
return (x % m + m) % m
def main():
g, x, y = extgcd(35, 15)
print(g, x, y)
print(modInverse(3, 11))
if __name__ == '__main__':
main()
4. Giải phương trình Diophantine tổng quát a * x + b * y = c
Xét phương trình tổng quát: \[a \cdot x + b \cdot y = c\]
- Điều kiện có nghiệm: Phương trình có nghiệm nguyên khi và chỉ khi \(c\) chia hết cho \(g = \gcd(a, b)\). Nếu \(c \pmod g \ne 0\), ta kết luận vô nghiệm.
- Tìm nghiệm riêng \((x_0, y_0)\):
- Gọi
extgcd(a, b, x_g, y_g)để có \(a \cdot x_g + b \cdot y_g = g\). - Nhân cả hai vế với tỉ số \(c / g\): \[x_0 = x_g \cdot \frac{c}{g}, \quad y_0 = y_g \cdot \frac{c}{g}\]
- Gọi
- Tìm nghiệm dương nhỏ nhất của \(x\):
- Ta có họ nghiệm: \(x = x_0 + k \cdot (b / g)\).
- Chọn số nguyên \(k\) thích hợp để đưa \(x\) về đoạn mong muốn hoặc tìm nghiệm cực tiểu cho bài toán tối ưu chi phí.
Bảng chạy tay chi tiết từng bước thuật toán Euclid mở rộng
Để hình dung tường minh cách hàm extgcd lần ngược hệ số Bézout, xét cặp số đầu vào \(a = 35\) và \(b = 15\).
Thuật toán trải qua 2 pha: Pha đệ quy xuôi (Forward) để tìm ƯCLN và Pha quay lui ngược (Backward) để tái tạo hệ số Bézout.
| Tầng đệ quy | \(a\) | \(b\) | Phép chia: \(q = \lfloor a / b \rfloor, r = a \pmod b\) | Hệ số bài con \((x_1, y_1)\) | Hệ số hiện tại: \(x = y_1, y = x_1 - q \cdot y_1\) | Giá trị \(\gcd\) |
|---|---|---|---|---|---|---|
| Bước 1 | 35 | 15 | \(35 = 2 \times 15 + 5\) (\(q = 2, r = 5\)) | \((0, 1)\) | \(x = 1, y = 0 - 2 \times 1 = -2\) | 5 |
| Bước 2 | 15 | 5 | \(15 = 3 \times 5 + 0\) (\(q = 3, r = 0\)) | \((1, 0)\) | \(x = 0, y = 1 - 3 \times 0 = 1\) | 5 |
| Bước 3 (Dừng) | 5 | 0 | \(b = 0\) (Điều kiện dừng) | - | \(x = 1, y = 0\) | 5 |
Kiểm tra lại hệ số thu được ở Tầng 1: \[35 \times (1) + 15 \times (-2) = 35 - 30 = 5 = \gcd(35, 15)\] Kết quả chính xác tuyệt đối! Cặp hệ số Bézout \((x = 1, y = -2)\) được sinh ra một cách tự nhiên nhờ cơ chế lưu vết trên ngăn xếp đệ quy.
Bốn lỗi lập trình và bẫy thường gặp với Euclid mở rộng
-
Nghiệm x bị âm khi tìm nghịch đảo modulo: Thuật toán Euclid mở rộng có thể trả về giá trị \(x\) âm. Trong toán học, \(-2 \equiv 5 \pmod 7\). Nhưng trong các ngôn ngữ lập trình như C++ hay Java, phép toán
-2 % 7sẽ trả về-2thay vì5. Để chuẩn hóa nghiệm về khoảng \([0, m - 1]\), bạn phải luôn viết:x = (x % m + m) % m. -
Quên kiểm tra điều kiện tồn tại nghịch đảo: Nghịch đảo modulo của \(a\) theo modulo \(m\) chỉ tồn tại khi và chỉ khi \(\gcd(a, m) = 1\). Nếu gọi hàm
extgcdmà giá trị trả về \(g > 1\), phương trình đồng dư vô nghiệm. Trả về \(-1\) để báo lỗi thay vì sử dụng giá trị \(x\) rác. -
Tràn số kiểu 32-bit khi tích lũy hệ số: Trong biểu thức \(y = x_1 - (a / b) \cdot y_1\), tích \((a / b) \cdot y_1\) có thể vượt quá giới hạn kiểu
intnếu các hệ số đầu vào lớn hơn \(10^9\). Bắt buộc phải khai báo các tham số và biến truyền tham chiếux, ybằng kiểulong long. -
Xử lý số âm ở đầu vào: Trong toán học, \(\gcd(a, b)\) luôn là số nguyên không âm. Nếu đầu vào \(a\) hoặc \(b\) có giá trị âm, hãy lấy giá trị tuyệt đối trước khi gọi hàm:
extgcd(abs(a), abs(b), x, y). Sau đó, nếu \(a < 0\) thì đổi dấu \(x\), nếu \(b < 0\) thì đổi dấu \(y\).
Luyện ngay trên Big-O Coding
Để rèn luyện kỹ năng làm việc với ước chung lớn nhất, hãy thực hành ngay bài tập sau:
Làm thế nào để cài đặt thuật toán Euclid mở rộng dạng vòng lặp không đệ quy?
Dạng vòng lặp lặp lại việc cập nhật ma trận biến đổi trạng thái qua các bước chia lấy dư. Mặc dù dạng vòng lặp tiết kiệm bộ nhớ ngăn xếp, nhưng do số bước đệ quy của Euclid không bao giờ vượt quá \(2 \log_2(\min(a, b)) \le 128\) bước đối với số nguyên 64-bit, việc dùng hàm đệ quy ngắn gọn 8 dòng lệnh như trên là hoàn toàn an toàn và không bao giờ bị lỗi tràn ngăn xếp (Stack Overflow).
Nếu gcd(a, b) là số âm thì hàm extgcd xử lý thế nào?
Trong toán học, \(\gcd(a, b)\) luôn được coi là số nguyên dương. Nếu đầu vào \(a\) hoặc \(b\) âm, bạn nên lấy giá trị tuyệt đối trước khi gọi hàm: extgcd(abs(a), abs(b), x, y), sau đó đổi dấu \(x\) nếu \(a < 0\) và đổi dấu \(y\) nếu \(b < 0\).
Nguồn tham khảo
- CP-Algorithms - Extended Euclidean Algorithm - Toàn cảnh lý thuyết và các ứng dụng nâng cao của thuật toán Euclid mở rộng
- VNOI Wiki - Thuật toán Euclid - Chuyên đề số học kinh điển cho học sinh chuyên Tin
- USACO Guide - Extended Euclidean Algorithm - Bài tập và kỹ thuật giải phương trình nghiệm nguyên trong thi đấu quốc tế
Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.


