Máy Tính GCF (Ước Chung Lớn Nhất)

GCF là gì?

Ước chung lớn nhất (GCF) của một tập số nguyên là số nguyên dương lớn nhất chia hết cho tất cả các số đó, dư 0. Tên gọi khác: GCD (Greatest Common Divisor), ƯCLN, hoặc HCF (Highest Common Factor) — cùng một giá trị, chỉ khác cách gọi theo từng sách giáo trình.

vì 6 chia hết cả 18, 30, 42, và không có số nào lớn hơn làm được điều đó.

Ba cách tìm GCF

1. Liệt kê ước

Liệt kê tất cả ước của từng số, rồi chọn ước chung lớn nhất.

Ví dụ — GCF(8, 12, 20):

• Ước của 8: 1, 2, 4, 8
• Ước của 12: 1, 2, 3, 4, 6, 12
• Ước của 20: 1, 2, 4, 5, 10, 20
• Ước chung: 1, 2, 4 → GCF = 4

Dễ hiểu, nhưng danh sách sẽ rất dài khi số lớn — công cụ này chỉ hiện cách này khi mọi số đầu vào ≤ 1.000.000.

2. Phân tích thừa số nguyên tố

Phân tích mỗi số thành thừa số nguyên tố, rồi nhân các thừa số chung với số mũ nhỏ nhất mà chúng xuất hiện.

Ví dụ — GCF(18, 27): $18 = 2 \times 3 \times 3$, $27 = 3 \times 3 \times 3$. Thừa số chung là $3 \times 3 = 9$, nên GCF = 9.

Ví dụ — GCF(20, 50, 120): $20 = 2^2 \times 5$, $50 = 2 \times 5^2$, $120 = 2^3 \times 3 \times 5$. Thừa số nguyên tố chung là 2 và 5, mỗi thừa số lấy số mũ nhỏ nhất: $2^1 \times 5^1 = 10$, nên GCF = 10.

3. Thuật toán Euclid

Với số lớn, chia liên tiếp nhanh hơn nhiều so với phân tích thừa số. Lấy số lớn chia số nhỏ được số dư, rồi lặp lại với (số nhỏ, số dư) đến khi dư bằng 0 — số dư khác 0 cuối cùng chính là GCF.

Ví dụ — GCF(270, 192):

270 = 1 × 192 + 78
192 = 2 × 78 + 36
78  = 2 × 36 + 6
36  = 6 × 6  + 0

Số dư khác 0 cuối cùng là 6, nên GCF(270, 192) = 6.

GCF và LCM khác nhau thế nào?

GCF và LCM (bội chung nhỏ nhất) là hai thái cực của cùng một phép so sánh thừa số nguyên tố: GCF giữ lũy thừa nhỏ nhất của mỗi thừa số chung, LCM giữ lũy thừa lớn nhất. Với hai số, chúng liên hệ qua:

Vậy khi đã biết GCF của hai số, LCM tính ngay bằng $\dfrac{a \times b}{\text{GCF}(a, b)}$ mà không cần phân tích thừa số thêm lần nữa.

Ví dụ minh hoạ

Ví dụ 1 — GCF(12, 18)

Thừa số nguyên tố: $12 = 2 \times 2 \times 3$, $18 = 2 \times 3 \times 3$. Chung: $2 \times 3 = 6$. Euclid xác nhận: $18 = 1 \times 12 + 6$, rồi $12 = 2 \times 6 + 0$ → GCF = 6.

Ví dụ 2 — GCF(12, 18, 24)

Gộp dần từng cặp: GCF(12, 18) = 6, rồi GCF(6, 24) = 6. GCF = 6. (Thuật toán Euclid chỉ áp dụng cho hai số một lúc — với ba số trở lên, công cụ này hiện phương pháp thừa số nguyên tố và liệt kê ước thay thế.)

Ví dụ 3 — GCF(7, 13)

7 và 13 đều là số nguyên tố và khác nhau, nên không có ước chung nào lớn hơn 1. GCF = 1 — hai số này nguyên tố cùng nhau.

Các thuật ngữ dễ nhầm lẫn