Chào các bạn, nhân dịp VNOI mới sập, à nhầm ..., mới được dựng lại, mình xin viết 1 bài mở màn về thuật toán Euclide mở rộng (Extended Euclidean algorithm).
Theo định lí Benzout (Benzout's identity), cho 2 số nguyên a, b, khi đó luôn tồn tại 2 số nguyên x, y sao cho:
ax + by = d //với d là ước chung lớn nhất của a và b.
Ta có thể viết lại:
\({a \over d}x + {b \over d}y = 1 \)
Giờ ta xét 2 số nguyên a, b nguyên tố cùng nhau và phương trình ax + by = 1. Ta có thể tiến hành tìm nghiệm x, y của bài toán. Áp dụng phương pháp tìm ước chung lớn nhất gcd(a, b) mà các bạn thường code.
Giả sử ta có biểu thức: 52x + 47y = 1 với a = 52, b = 47
- Bước 1: 52 mod 47 = 5
- Bước 2: 47 mod 5 = 2
- Bước 3: 5 mod 2 = 1
- Bước 4: 2 mod 1 = 0
Vì ở bước 4 kết quả là 0 nên mình không xét. Như vậy mình đi ngược từ bước 3 trở lên. Theo đó ở bước 3 ta có:
5 mod 2 = 1 (1)
=> 5 - 2 * 2 = 1
Theo hàm gcd, giá trị 2 ở trên là do có được từ bước 2 nên 47 mod 5 = 2 => 2 = 47 - 9 * 5
=> Thế kết quả của 2 vào (1) ta được: 5 - 2 * (47 - 9 * 5) = 1 (2)
Tiếp tục ở bước 1 ta có 52 mod 47 = 5 => 5 = 52 - 1 * 47.
Thế kết quả vào (2) ta được: (52 - 47) - 2 * [47 - 9 * (52 - 47)] = 1
Ta cũng có thể viết lại (a - b) - 2 * [b - 9 * (a - b)] = 1
=> 19a - 21b = 1
Vậy khi đó nghiệm của bài toán là: x = 19, y = -21
Ta có thể kiểm tra lại 19 * 52 - 21 * 47 = 1
Từ cách làm trên ta có thể rút ra cách tìm x, y của bài toán theo đoạn code sau (do mình tự viết):
bool isSwap = false //Biến dùng để kiểm tra 2 số a và b có hoán đổi nhau không
if a < b:
begin
hoán đổi a, b
gán isSwap = true
end;
int prex = 0, prey = 0, x = 0, y = 1 //prex và prey là 2 biến lưu giá trị trước của x và y
r = a mod b
Nếu r ≠ 0:
begin
y = y * (- int(a / b));
x = 1, prey = 1
a = b, b = r
end;
while b ≠ 0:
begin
r = a mod b
if r ≠ 0
begin
tprex = x,
tprey = y,
//tprex và tprey là 2 biến tạm thời lưu giá trị x, y
md = - int(a / b)
x = x * md + prex,
y = y * md + prey
prex = tprex, prey = tprey
end
a = b, b = r
end
if isSwap = true => trả về bộ 3 (a, y, x) //Vì a, b đã hoán vị nên ta phải hoán vị cả y và x
Trả về bộ 3 (a, x, y) //a là ước chung lớn nhất của a, b ban đầu
Theo thuật toán Euclide mở rộng ra cũng rút ra được: abs(x) < abs(b / d) và abs(y) < abs(a / d)
Áp dụng:
Đây có thể xem là thuật toán dùng để thay thế định lí nhỏ Fermat mà các bạn thường dùng cho bài toán:
\({a \over b} \mod m\)
Với m là số nguyên tố.
Theo đó các bạn sẽ tìm kết quả bài toán bằng cách áp dụng định lí nhỏ Fermat với biểu thức biến đổi: \(a * b^{m - 2} (\mod m)\)
Tuy nhiên nếu áp dụng định lí Euclide mở rộng cho bài toán này thì ta có thể tính giá trị b (mod m) theo dạng:
bx + my = 1
Giải phương trình trên bằng thuật toán Euclide mở rộng sẽ tìm được nghiệm x. Nếu kết quả x âm, ta có thể tăng x lên m đơn vị (vì abs(x) < abs(m / 1))
Như vậy khi đó ta lấy x * a (mod m) sẽ tương đương với biểu thức \({a \over b} \mod m\)
Thay thế định lí Fermat nhỏ bằng thuật toán Euclide mở rộng ta được 2 ưu thế:
- Với bài toán \({a \over b} \mod m\) thì ta có thể tính kết quả với m không nhất thiết là số nguyên tố. Chỉ cần b và m nguyên tố cùng nhau.
- Tốc độ thực thi của thuât toán Euclide mở rộng nhanh hơn định lí nhỏ Fermat: nếu ta dùng 1 ngôn ngữ lập trình có hỗ trợ số lớn để test thì ta sẽ thấy rằng Euclide mở rộng nhanh hơn rõ rệt so với định lí nhỏ Fermat khi a, b, m có kích thước từ vài nghìn để vài triệu bit nhị phân.
