Ước số chung lớn nhất

Trong toán học, ước số chung lớn nhất (ƯCLN) hay ước chung lớn nhất (ƯCLN) của hai hay nhiều số nguyên là số nguyên dương lớn nhất mà các số đó đều chia hết. Ví dụ, ước chung lớn nhất của 6 và 15 là 3 vì $6:3=2$ và $15:3=5$.

Trong tiếng Anh, ước số chung lớn nhất được gọi là greatest common divisor (GCD), greatest common factor (GCF), highest common factor (HCF), greatest common measure (GCM), hoặc highest common divisor (HCD).

Nếu tất cả các số nguyên đều bằng 0 thì không có ƯCLN vì không có số tự nhiên nào có thể chia hết cho 0. Nếu trong số đó có ít nhất một số bằng 0 và ít nhất một số khác 0 thì ƯCLN của chúng chính là ƯCLN của các số khác 0.

Khái quát

Biểu tượng

Ước chung lớn nhất của a0, a1, a2,... an được ký hiệu là ƯCLN(a0, a1, a2,... an)

Ví dụ

Tính ước chung lớn nhất của 27 và 45?

Chúng ta có:

• Các ước của 27 là $1,3,9,27$.
• Các ước của 45 là $1,3,5,9,15,45$.

Các số xuất hiện trong cả hai danh sách là những ước chung của 27 và 45:

$1,3,9$

Số lớn nhất trong danh sách này là 9. Do đó, 9 là ước chung lớn nhất của 27 và 45. Viết UCLN(27,45)=9

Ước số nguyên tố cùng nhau

Hai số được gọi là số nguyên tố cùng nhau nếu ước chung lớn nhất của chúng là 1. Ví dụ, 9 và 28 là hai số nguyên tố cùng nhau.

Ước chung lớn nhất được dùng để đưa một phân số về dạng tối giản. Ví dụ, ƯCLN(42, 56)=14, vì vậy,

$\frac{42}{56}=\frac{3\cdot <!--\; \cdot \; -->14}{4\cdot <!--\; \cdot \; -->14}=\frac{3}{4}.$

Các thuộc tính

• Mọi ước chung của các số là ước của ƯCLN của chúng.
• Đối với các số nguyên a0, a1, a2,... an, ƯCLN(a0, a1, a2,... an) có thể được xác định tương đương với số nguyên dương d nhỏ nhất có dạng d = $\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}{a}_k{x}_k$ trong đó xk là các số nguyên. Định lý này gọi là đẳng thức Bézout. Các số xk có thể được tính bằng Giải thuật Euclid mở rộng.
• ƯCLN(a, 0) =|a|, với mọi a ≠ 0, vì mọi số khác 0 đều là ước của 0, và ước lớn nhất của a là|a|. Đây là trường hợp cơ bản trong thuật toán Euclid.
• Nếu a là ước của tích b·c, và ƯCLN(a, b) = d, thì a/d là ước của c.
• Nếu m là số nguyên dương, thì ƯCLN(ma0, ma1, ma2,...man) = m · ƯCLN(a0, a1, a2,... an).
• Nếu m là số nguyên bất kỳ, thì ƯCLN(a + m · b, b) = ƯCLN(a, b). Nếu m là ước chung (khác 0) của a và b, thì UCLN(a/m, b/m) = ƯCLN(a, b)/m.
• ƯCLN là một hàm có tính chất nhân: nếu các số a₁, a₂,...,a_n là các số nguyên tố cùng nhau, thì ƯCLN(a₁ · a₂ · ... · a_n, b) = ƯCLN(a₁, b) · ƯCLN (a₂, b) · ... · ƯCLN (an, b).
• ƯCLN là hàm giao hoán: ƯCLN(a, b) = ƯCLN(b, a).
• ƯCLN là hàm kết hợp: ƯCLN(a,b,c)= ƯCLN(a, ƯCLN(b, c)) = ƯCLN(ƯCLN(a, b), c).
• ƯCLN(a, b) có mối liên hệ chặt chẽ với BCNN(a, b): ta có

ƯCLN(a, b) · BCNN(a, b) = a · b.

Công thức này thường được áp dụng để tính BCNN của hai số. Một dạng khác của mối quan hệ này là tính chất phân phối:

BCNN(a, ƯCLN(a0, a1, a2,... an)) = ƯCLN(BCNN(a, a₀), BCNN(a, a₁), BCNN(a,a₂),...,BCNN(a,a_n)).

• Với định nghĩa ƯCLN(0, 0) = 0 và BCNN(0, 0) = 0, tập các số tự nhiên trở thành một dàn đầy đủ phân phối với ƯCLN.
• Trong hệ tọa độ Descartes, ƯCLN(a, b) thể hiện số điểm có tọa độ nguyên trên đoạn thẳng nối từ (0, 0) đến (a, b), không bao gồm điểm (0, 0).

Tính toán

Tìm ước chung lớn nhất qua phân tích thành thừa số nguyên tố

Định lý cơ bản của số học cho biết mọi số nguyên dương lớn hơn 1 có thể được biểu diễn một cách duy nhất dưới dạng tích của các số nguyên tố (không tính đến thứ tự của các thừa số). Do đó, các hợp số có thể được xem là các nguyên tố cấu thành của chúng. Ví dụ:

$90=2^1\cdot <!--\; \cdot \; -->3^2\cdot <!--\; \cdot \; -->5^1=2\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5$

Ở đây, số 90 được phân tích thành các thừa số nguyên tố gồm một nguyên tố 2, hai nguyên tố 3 và một nguyên tố 5.

Kiến thức này giúp chúng ta xác định ƯCLN cho một tập hợp các số.

Chẳng hạn: Tìm ƯCLN của các số 12, 32 và 60.

Trước tiên, hãy phân tích từng số thành tích các thừa số nguyên tố.

$12=2^2\cdot <!--\; \cdot \; -->3$

$32=2^5$

$60=2^2\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5$

Để tìm ƯCLN, ta lấy các thừa số nguyên tố chung giữa các số và nâng lên bậc thấp nhất rồi nhân lại. Thừa số 2 xuất hiện trong tất cả các số, với bậc thấp nhất là 2. Vì vậy:

$\mathrm{UCLN}<!--\; \; -->(12,32,60)=2^2=4$

Phương pháp này chỉ phù hợp với các số nhỏ. Đối với các số lớn, việc phân tích ra thừa số nguyên tố rất tốn thời gian.

Để tính ƯCLN của hai số tự nhiên, phương pháp hiệu quả nhất là dùng thuật toán Euclid, dựa vào chuỗi các phép chia có dư liên tiếp.

Tính qua bội số chung nhỏ nhất

Nếu a và b là hai số khác không, thì ước chung lớn nhất của a và b có thể được tính thông qua bội chung nhỏ nhất (BCNN) của a và b:

Chú giải

Xem thêm

• Donald Knuth. Nghệ Thuật Lập Trình Máy Tính, Tập 2: Thuật Toán Seminumerical, Phiên bản Thứ Ba. Addison-Wesley, 1997. ISBN 0-201-89684-2. Phần 4.5.2: Ước Chung Lớn Nhất, trang 333–356.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, và Clifford Stein. Giới Thiệu Về Thuật Toán, Phiên bản Thứ Hai. MIT Press và McGraw-Hill, 2001. ISBN 0-262-03293-7. Phần 31.2: Ước Chung Lớn Nhất, trang 856–862.
• Saunders MacLane và Garrett Birkhoff. Tổng Quan Về Đại Số Hiện Đại, Phiên bản Thứ Tư. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1-7: 'Thuật Toán Euclid.'

Các liên kết bên ngoài

• Triển khai GCD trong C++
• Ước Chung Lớn Nhất tại Everything2.com
• Ước Chung Lớn Nhất: 2500 Năm Cuối, bởi Alexander Stepanov