Máy tính ƯCLN ước chung lớn nhất

Với phân tích thừa số nguyên tố, hãy tách mỗi số thành các thừa số nguyên tố, chỉ giữ những số nguyên tố xuất hiện trong tất cả các số, và lấy lũy thừa nhỏ nhất của mỗi số. 48 = 2⁴ × 3, 180 = 2² × 3² × 5 và 300 = 2² × 3 × 5². Số nguyên tố 5 không có trong 48 nên bị loại; 2 xuất hiện ít nhất với bình phương và 3 ít nhất một lần. ƯCLN là 2² × 3 = 12.

Thuật toán Euclid bỏ qua bước phân tích thừa số. Chia số lớn hơn cho số nhỏ hơn và giữ số dư, rồi lặp lại với số chia và số dư cho đến khi số dư bằng 0. Với 180 và 48: 180 = 3 × 48 + 36, rồi 48 = 1 × 36 + 12, rồi 36 = 3 × 12 + 0. Số dư khác 0 cuối cùng, 12, là ƯCLN.

ƯCLN là chìa khóa để rút gọn phân số. Vì ƯCLN của 48 và 180 là 12, phân số 48/180 rút gọn thành 4/15 chỉ trong một bước. Khi ƯCLN là 1, phân số đã ở dạng tối giản.

Kiểm tra nhanh: chia mỗi số cho ƯCLN thì kết quả phải không còn thừa số chung nào. 48, 180 và 300 chia cho 12 được 4, 15 và 25, và không có số nào lớn hơn 1 chia hết cả ba.