Thuật toán Euclid là gì?
Thuật toán Euclid là một trong những thuật toán cổ xưa nhất từng được biết đến, do nhà toán học Hy Lạp Euclid mô tả vào khoảng năm 300 trước Công nguyên. Nó dùng để tìm ước chung lớn nhất (UCLN) của hai số nguyên — tức là số lớn nhất chia hết cho cả hai số mà không để lại số dư. Công cụ này áp dụng thuật toán cho bất kỳ cặp số nguyên không âm nào, đồng thời cho ra cả bội chung nhỏ nhất (BCNN) của chúng.
Cách sử dụng
Nhập hai số của bạn vào hai ô có nhãn a và b rồi bấm tính. Công cụ sẽ hiển thị UCLN là kết quả chính và BCNN là giá trị phụ. Thứ tự nhập không quan trọng — \(\gcd(48, 36)\) bằng đúng \(\gcd(36, 48)\). Nếu nhập số âm, máy tính sẽ lấy giá trị tuyệt đối; còn nếu một trong hai số bằng 0 thì UCLN chính là số còn lại.
Giải thích công thức
Thuật toán dựa trên một nhận xét đơn giản: bất kỳ ước chung nào của a và b cũng đồng thời là ước của số dư a mod b. Vì vậy, ta liên tục thay số lớn hơn bằng số dư:
$$\gcd(a,b) = \gcd(b,\, a \bmod b), \quad \gcd(a,0) = a$$
với trường hợp cơ sở \(\gcd(a, 0) = a\).
Mỗi bước đều làm các số nhỏ đi rất nhanh, nên ngay cả những giá trị khổng lồ cũng chỉ cần vài vòng lặp là ra kết quả. Sau đó BCNN được tính theo công thức $$\operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)}$$
Ví dụ minh họa
Tìm \(\gcd(48, 36)\):
$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$
$$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = 12$$
Vậy UCLN là 12, và $$\operatorname{lcm} = \frac{48 \times 36}{12} = \frac{1728}{12} = 144$$
Câu hỏi thường gặp
Nếu cả hai số đều bằng 0 thì sao? Ở đây UCLN của 0 và 0 được quy ước là 0, và BCNN cũng bằng 0 vì không tồn tại bội số dương nào.
Vì sao thuật toán này nhanh hơn cách liệt kê ước số? Thay vì phải tìm hết tất cả các ước, thuật toán sử dụng mẹo lấy số dư, giúp thu nhỏ bài toán đáng kể sau mỗi bước — thường chỉ mất thời gian theo hàm logarit.
Có xử lý được các số rất lớn không? Có. Thuật toán Euclid rất hiệu quả ngay cả với những số có nhiều chữ số, chỉ cần một số ít phép chia lấy dư là xong.
