Thuật toán Euclid tìm ước chung lớn nhất (ƯCLN) của hai số bằng cách lấy số lớn chia số nhỏ, rồi lấy số nhỏ chia phần dư, cứ thế cho đến khi phần dư bằng 0; số chia cuối cùng chính là ƯCLN. Không cần phân tích ra thừa số nguyên tố, chỉ vài phép chia là xong, kể cả với số rất lớn. Đây là thuật toán cổ nhất còn được dùng hằng ngày, từ rút gọn phân số đến mã hoá dữ liệu.
Ước chung lớn nhất là gì và để làm gì
Ước của một số là số chia hết số đó. Ước chung của hai số là số chia hết cả hai. Ước chung lớn nhất là số lớn nhất trong các ước chung. Ví dụ các ước của 12 là 1, 2, 3, 4, 6, 12; các ước của 18 là 1, 2, 3, 6, 9, 18; ước chung là 1, 2, 3, 6; ƯCLN là 6.
ƯCLN là câu trả lời cho mọi bài toán dạng "chia thành phần giống hệt nhau, càng nhiều phần càng tốt":
- Có 48 bút, 36 vở, 60 cái kẹo, muốn chia thành các phần quà giống nhau, không thừa món nào. Số phần quà nhiều nhất là ƯCLN(48, 36, 60) = 12, mỗi phần 4 bút, 3 vở, 5 kẹo.
- Lát nền phòng 4,8 m × 3,6 m bằng gạch vuông to nhất mà không phải cắt viên nào. Cạnh gạch là ƯCLN(480, 360) = 120 cm, cần 4 × 3 = 12 viên.
- Rút gọn phân số 462/1071 về tối giản: chia cả tử và mẫu cho ƯCLN.
Với số nhỏ, liệt kê ước như trên là được. Với số có bốn, năm chữ số, liệt kê ước rất mệt. Thuật toán Euclid giải quyết chuyện này.
Thuật toán Euclid từng bước: một ví dụ tính tay
Tìm ƯCLN(1071, 462):
| Bước | Phép chia | Thương | Dư |
|---|---|---|---|
| 1 | 1071 = 2 × 462 + 147 | 2 | 147 |
| 2 | 462 = 3 × 147 + 21 | 3 | 21 |
| 3 | 147 = 7 × 21 + 0 | 7 | 0 |
Phần dư bằng 0 ở bước 3, số chia của bước đó là 21. Vậy ƯCLN(1071, 462) = 21. Kiểm lại: 1071 = 21 × 51 và 462 = 21 × 22, còn 51 và 22 không có ước chung nào ngoài 1. Phân số 462/1071 rút gọn thành 22/51.
Quy tắc gói gọn trong một câu: ƯCLN(a, b) = ƯCLN(b, a chia b lấy dư), lặp lại cho đến khi số thứ hai bằng 0. Ví dụ phòng lát gạch ở trên: 480 = 1 × 360 + 120, rồi 360 = 3 × 120 + 0, nên ƯCLN là 120.
Vì sao thuật toán đúng
Lý lẽ chỉ cần một quan sát: nếu d chia hết cả a và b, thì d chia hết a − b, a − 2b, và nói chung a − q × b với mọi q. Phần dư r chính là a − q × b. Vậy mọi ước chung của a và b cũng là ước của r. Ngược lại, mọi ước chung của b và r cũng chia hết a = q × b + r.
Kết quả: cặp (a, b) và cặp (b, r) có đúng cùng một tập ước chung, nên cùng ƯCLN. Mỗi bước thay cặp số bằng cặp nhỏ hơn mà không làm đổi đáp án. Vì các phần dư giảm dần và không âm, đến lúc nào đó phải bằng 0, và khi đó ƯCLN(d, 0) = d.
Hình dung bằng hình chữ nhật
Euclid không nghĩ bằng phép chia mà bằng đo đạc. Lấy một hình chữ nhật 1071 × 462. Cắt ra những hình vuông cạnh 462 lớn nhất có thể: được 2 hình vuông, còn dải 462 × 147. Cắt dải này thành hình vuông cạnh 147: được 3 hình, còn dải 147 × 21. Cắt tiếp được đúng 7 hình vuông cạnh 21, không còn thừa. Hình vuông nhỏ nhất, cạnh 21, lát kín mọi phần trước đó, nên lát kín cả hình chữ nhật ban đầu. Đây cũng là cách nghĩ bằng phép trừ lặp lại: trừ 462 khỏi 1071 hai lần thay vì chia.
Euclid viết gì và người xưa dùng ra sao
Thuật toán nằm ở quyển VII bộ Cơ sở của Euclid, viết ở Alexandria khoảng năm 300 trước Công nguyên, trong hai mệnh đề đầu: mệnh đề 1 cho biết khi nào hai số "nguyên tố cùng nhau", mệnh đề 2 chỉ cách tìm "số đo chung lớn nhất". Euclid trình bày bằng lời và bằng đoạn thẳng, dùng phép trừ lặp lại. Các nhà nghiên cứu cho rằng phương pháp này có thể đã được biết trước Euclid, ông là người ghi lại có hệ thống.
Ở Trung Hoa, sách Cửu chương toán thuật (khoảng thế kỷ 1) có cách rút gọn phân số gọi là "canh tương giảm tổn": lấy số lớn trừ số nhỏ, lặp lại cho đến khi hai số bằng nhau, số đó là ước chung lớn nhất. Đó chính là thuật toán Euclid dạng phép trừ, ra đời độc lập.
Nhà khoa học máy tính Donald Knuth trong bộ The Art of Computer Programming gọi thuật toán Euclid là "ông tổ của mọi thuật toán", vì đây là thuật toán không tầm thường cổ nhất còn được dùng đến ngày nay.
Thuật toán chạy nhanh đến mức nào
Năm 1844, nhà toán học Pháp Gabriel Lamé chứng minh: số bước chia của thuật toán Euclid không vượt quá 5 lần số chữ số của số nhỏ hơn. Với hai số có 100 chữ số, tối đa khoảng 500 phép chia, máy tính làm trong chớp mắt. So với cách phân tích ra thừa số nguyên tố, thứ có thể mất hàng nghìn năm với số đủ lớn, khác biệt là một trời một vực.
Trường hợp tệ nhất là hai số Fibonacci liên tiếp, ví dụ 89 và 55: mỗi bước thương đều bằng 1, phần dư giảm chậm nhất có thể (89, 55, 34, 21, 13, 8, 5, 3, 2, 1). Đây là chỗ hiếm hoi dãy Fibonacci xuất hiện như "kẻ khó chịu" thay vì vẻ đẹp tự nhiên.
Người ta còn có biến thể chỉ dùng phép chia đôi và phép trừ, gọi là thuật toán ƯCLN nhị phân (Josef Stein công bố năm 1967), hợp với máy tính vì chia đôi trong hệ nhị phân chỉ là dịch bit.
Thuật toán Euclid mở rộng: đi ngược để tìm hệ số
Từ các bước chia, có thể đi ngược để viết ƯCLN thành tổng của hai số ban đầu nhân hệ số nguyên. Với ví dụ trên:
- Từ bước 2: 21 = 462 − 3 × 147.
- Từ bước 1: 147 = 1071 − 2 × 462.
- Thay vào: 21 = 462 − 3 × (1071 − 2 × 462) = 7 × 462 − 3 × 1071.
Kiểm lại: 7 × 462 = 3.234, 3 × 1071 = 3.213, hiệu đúng bằng 21. Kết quả này mang tên đẳng thức Bézout: luôn tìm được hai số nguyên x, y để a × x + b × y = ƯCLN(a, b).
Đẳng thức có ứng dụng rất đời thường. Bài toán quen thuộc: có bình 5 lít và bình 3 lít, đong đúng 4 lít nước thế nào? Vì ƯCLN(5, 3) = 1 và 4 = 2 × 5 − 2 × 3, ta đong đầy bình 5 lít hai lần và đổ bỏ hai bình 3 lít, theo thứ tự hợp lý là ra 4 lít. Nếu hai bình là 6 lít và 4 lít thì không bao giờ đong được 3 lít, vì ƯCLN(6, 4) = 2 và mọi lượng đong được đều chẵn.
Ở quy mô lớn hơn, thuật toán Euclid mở rộng là bước tìm "khoá giải mã" trong hệ mã hoá RSA, thứ bảo vệ kết nối ngân hàng và trang web có ổ khoá trên trình duyệt.
Góc nhìn hôm nay: dùng Euclid khi nào
Trong đời thường, thuật toán Euclid có ích mỗi khi phải chia đồ thành phần đều: xếp hoa vào bó, chia quà Trung thu cho các lớp, cắt vải thành mảnh vuông không phí. Nhớ một mẹo: ƯCLN của nhiều số tính lần lượt từng cặp, ƯCLN(48, 36, 60) = ƯCLN(ƯCLN(48, 36), 60) = ƯCLN(12, 60) = 12.
Một mẹo nữa: bội chung nhỏ nhất tính được ngay từ ƯCLN, bằng tích hai số chia ƯCLN. BCNN(1071, 462) = 1071 × 462 : 21 = 23.562. Trong bảng tính Excel hay Google Sheets, hàm GCD và LCM làm đúng việc này. Ai muốn đọc nguyên văn, bản dịch tiếng Anh bộ Cơ sở của Euclid có miễn phí trên nhiều thư viện số đại học; quyển VII ngắn và đọc được với kiến thức lớp 6.
Câu hỏi thường gặp
Thuật toán Euclid là gì?
Là cách tìm ước chung lớn nhất của hai số bằng các phép chia liên tiếp: lấy số lớn chia số nhỏ, rồi số nhỏ chia phần dư, lặp lại đến khi dư bằng 0. Số chia cuối cùng là ƯCLN. Thuật toán được ghi trong bộ Cơ sở của Euclid khoảng năm 300 trước Công nguyên.
Cách tìm ƯCLN của hai số lớn nhanh nhất?
Dùng thuật toán Euclid thay vì phân tích ra thừa số. Ví dụ ƯCLN(1071, 462): 1071 chia 462 dư 147, 462 chia 147 dư 21, 147 chia 21 dư 0, vậy ƯCLN là 21. Số bước không quá 5 lần số chữ số của số nhỏ.
Vì sao thuật toán Euclid đúng?
Vì mọi ước chung của a và b cũng chia hết phần dư r = a − q × b, và ngược lại. Cặp (a, b) và (b, r) có cùng tập ước chung nên cùng ƯCLN; lặp lại đến khi phần dư bằng 0 thì số còn lại chính là ƯCLN.
ƯCLN và BCNN liên hệ thế nào?
Tích hai số bằng tích ƯCLN và BCNN của chúng. Vì vậy BCNN(a, b) = a × b : ƯCLN(a, b). Ví dụ ƯCLN(12, 18) = 6 nên BCNN = 216 : 6 = 36.
Thuật toán Euclid mở rộng dùng để làm gì?
Nó tìm hai số nguyên x, y sao cho a × x + b × y bằng ƯCLN(a, b). Kết quả dùng để giải bài toán đong nước bằng hai bình, giải phương trình nghiệm nguyên, và tìm khoá giải mã trong hệ mã hoá RSA.