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. Thuật toán này giúp tìm ước chung lớn nhất (UCLN) của hai số nguyên một cách hiệu quả — tức là số lớn nhất chia hết cả hai số mà không để lại số dư. Công cụ này còn trả về cả bội chung nhỏ nhất (BCNN), vốn được suy ra trực tiếp từ UCLN.
Cách sử dụng máy tính
Hãy nhập hai số nguyên vào các ô phía trên rồi nhấn tính. Máy tính sẽ lấy giá trị tuyệt đối của các số bạn nhập, sau đó áp dụng lặp lại quy tắc \(\gcd(a, b) = \gcd(b, a \bmod b)\) cho đến khi số dư bằng 0. Cuối cùng, kết quả hiển thị cả UCLN lẫn BCNN.
Giải thích công thức
Ý tưởng cốt lõi là: UCLN của hai số không thay đổi nếu ta thay số lớn hơn bằng số dư của nó khi chia cho số nhỏ hơn. Viết dưới dạng ký hiệu:
$$\gcd\!\left(a,\,b\right) = \gcd\!\left(b,\,a \bmod b\right)$$Bạn cứ tiếp tục như vậy cho đến khi \(b = 0\); giá trị khác 0 cuối cùng chính là UCLN. Sau đó, BCNN được tính theo công thức
$$\operatorname{lcm}\!\left(a,\,b\right) = \frac{\left|a\right| \times \left|b\right|}{\gcd\!\left(a,\,b\right)}$$bởi tích của hai số luôn bằng tích của UCLN và BCNN của chúng.
Ví dụ minh họa
Tìm \(\gcd(48, 36)\): lấy \(48 \bmod 36 = 12\), vậy chuyển sang \(\gcd(36, 12)\). Tiếp theo \(36 \bmod 12 = 0\), nên UCLN là 12. Còn BCNN là
$$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$
Câu hỏi thường gặp
Nếu một trong hai số bằng 0 thì sao? \(\gcd(a, 0) = a\). Thuật toán xử lý trường hợp này một cách tự nhiên — vòng lặp dừng ngay lập tức và trả về số khác 0.
Thứ tự của a và b có quan trọng không? Không. \(\gcd(a, b) = \gcd(b, a)\); thuật toán tự điều chỉnh ngay ở bước đầu tiên.
Tôi có thể nhập số âm không? Có. Máy tính sẽ lấy giá trị tuyệt đối, vì theo quy ước UCLN luôn là số dương.
