Ước chung lớn nhất là gì?
Ước chung lớn nhất (ƯCLN) của hai số nguyên là số nguyên dương lớn nhất chia hết cho cả hai số mà không để lại số dư. Ví dụ, ƯCLN của 48 và 36 là 12, vì 12 là số lớn nhất chia hết cho cả hai số này. Máy tính ƯCLN này sẽ tìm ngay giá trị đó, đồng thời cho biết luôn cả bội chung nhỏ nhất (BCNN).
Cách sử dụng máy tính
Bạn chỉ cần nhập hai số nguyên vào ô A và ô B, rồi xem kết quả hiện ra. Công cụ tự lấy giá trị tuyệt đối của mỗi số nhập vào, nên số âm vẫn được xử lý đúng. Nếu bạn nhập 0 cho một trong hai số thì ƯCLN sẽ bằng đúng số còn lại (vì mọi số nguyên đều chia hết cho 0).
Thuật toán Euclid giải thích đơn giản
Máy tính này dùng thuật toán Euclid, một trong những thuật toán lâu đời nhất vẫn còn được sử dụng phổ biến đến ngày nay. Nó dựa trên một quy tắc rất đơn giản: \(\gcd\left(a,\ b\right) = \gcd\left(b,\ a \bmod b\right)\). Bạn liên tục thay số lớn hơn bằng số dư của phép chia hai số, cho đến khi số dư bằng 0. Số chia khác 0 cuối cùng chính là ƯCLN. Cách làm này không cần phân tích các số ra thừa số nguyên tố và cực kỳ nhanh ngay cả với những số rất lớn.
Ví dụ minh họa
Tìm ƯCLN(48, 36):
$$48 \bmod 36 = 12 \rightarrow \gcd\left(36,\ 12\right)$$$$36 \bmod 12 = 0 \rightarrow \gcd\left(12,\ 0\right) = \mathbf{12}$$Khi đó BCNN là $$\text{lcm} = \frac{\left|48\right| \times \left|36\right|}{\gcd\left(48,\ 36\right)} = \frac{1728}{12} = \mathbf{144}$$
Câu hỏi thường gặp
ƯCLN và GCD/HCF có khác nhau không? Không hề — đó chỉ là những tên gọi khác nhau cho cùng một giá trị. Trong tiếng Anh, người Mỹ thường dùng "greatest common divisor" (GCD), còn người Anh dùng "highest common factor" (HCF); tiếng Việt gọi chung là ước chung lớn nhất (ƯCLN).
ƯCLN của hai số nguyên tố cùng nhau bằng bao nhiêu? Luôn bằng 1. Những số như 8 và 15 không có ước chung nào ngoài 1, nên chúng được gọi là hai số nguyên tố cùng nhau.
ƯCLN có thể lớn hơn số nhỏ hơn trong hai số không? Không. ƯCLN không bao giờ vượt quá số nhỏ hơn trong hai số đã nhập, và nó bằng đúng số nhỏ hơn khi số đó là ước của số lớn hơn.
