Ước số chung lớn nhất (GCD) là số lớn nhất chia hết cho hai hoặc nhiều số nguyên mà không có số dư. Đối với 12 và 18, các ước số của chúng lần lượt là 1, 2, 3, 6, vì vậy GCD là 6. GCD còn được gọi là ước chung lớn nhất.

Thuật toán Euclid tìm ước chung lớn nhất (GCD) một cách hiệu quả. Chia số lớn hơn cho số nhỏ hơn, sau đó thay số lớn hơn bằng số dư, và lặp lại cho đến khi số dư bằng 0. Số dư khác 0 cuối cùng chính là GCD. Phương pháp này đã có hơn hai nghìn năm tuổi và vẫn được sử dụng trong khoa học máy tính.

Ước chung lớn nhất (GCD) giúp đơn giản hóa phân số. Chia cả tử số và mẫu số cho GCD sẽ đưa phân số về dạng tối giản. Nó cũng xuất hiện trong số học modulo, mật mã học và lý thuyết số. Bội chung nhỏ nhất (LCM) có liên quan đến GCD theo công thức LCM(a, b) = a × b / GCD(a, b).

• Số lớn nhất chia hết cho các số nguyên
• Được tìm thấy bằng thuật toán Euclid
• Dùng để rút gọn phân số.
• Có liên quan đến Bội chung nhỏ nhất (LCM) bằng một công thức đơn giản.