Bách khoa toàn thư mở Wikipedia
Trong toán học, ước chung lớn nhất (ƯCLN) của hai số nguyên khác không là số nguyên dương lớn nhất mà 2 số nguyên đó đều chia hết.
[sửa] Ký hiệu và ví dụ
Ước chung lớn nhất của a và b được ký hiệu là ƯCLN(a, b), hay đơn giản hơn là (a, b). Chẳng hạn, ƯCLN(12, 18) = 6, ƯCLN(−4, 14) = 2 and gcd(5, 0) = 5. Hai số được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Chẳng hạn, 9 và 28 là nguyên tố cùng nhau.
Ước chung lớn nhất được sử dụng để đưa một phân số về dạng phân số tối giản. Chẳng hạn, ƯCLN(42, 56)=14, do đó,
[sửa] Tính ước chung lớn nhất
ƯCLN của hai số có thể tìm được bằng việc phân tích hai số đó ra thừa số nguyên tố, chẳng hạn để tìm ƯCLN(18,84), ta phân tích 18 = 2·32 và 84 = 22·3·7 và nhận xét rằng các thừa số chung lớn nhất của hai số này là 2·3; do đó ƯCLN(18,84) = 6. Trên thực tế phương pháp này chỉ dùng cho các số nhỏ; việc phân tích các số lớn ra thừa số nguyên tố mất rất nhiều thời gian.
Một phương pháp hiệu quả là giải thuật Euclid dựa trên dãy liên tiếp các phép chia có dư.
Nếu a và b là các số khác không, thì ước chung lớn nhất của a vàb có thể tính qua bội chung nhỏ nhất (BCNN) của a và b:
[sửa] Các tính chất
- Mọi ước chung của a và b là ước của ƯCLN(a, b).
- ƯCLN(a, b), khi a và b không bằnng không cả hai, có thể được định nghĩa tương đương nhưôs nghuyeen dương d nhỏ nhất có dạng d = a·p + b·q trong đó p và q là các số nguyên. Định lý bày đựoc gọi là đẳng thức Bézout. Các số p và q có thể tính nhờ Giải thuật Euclid mở rộng.
- ƯCLN(a, 0) = |a|, với mọi a ≠ 0, vì mọi số khác không bất kỳ là ước của 0, và ước lớn nhất của a là |a|. Đây là trường hợp cơ sở 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(m·a, m·b) = m·ƯCLN(a, b).
- Nếu m là số nguyên bất kỳ , thì ƯCLN(a + m·b, b) = gcd(a, b). Nếu m ướ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 nhân theo nghĩa sau: nếu a1 và a2 là nguyên tố cùng nhau, thì ƯCLN(a1·a2, b) = ƯCLN(a1, b)·ƯCLN (a2, b).
- ƯCLN là hàm giao hoán: ƯCLN(a, b) = ƯCLN(b, a).
- ƯCLN là hàm kết hợp : ƯCLN(a, gcd(b, c)) = ƯCLN(ƯCLN(a, b), c).
- ƯCLN của ba số được tính nhờ công thức ƯCLN(a, b, c) = ƯCLN(ƯCLN(a, b), c), (hoặc vế kia của tính chất kết hợp. Điều này có thể m[r rộng cho mtj số bất kỳ.
- ƯCLN (a, b) quan 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 dùng để tính BCNN. Dạng khác của mói quan hệ này là tính chất phân phối:
(a, b), ƯCLN(a, c))
-
- BCNN(a, ƯCLN(b, c)) = ƯCLN(BCNN(a, b), BCNN(a, c)).dis cu
- Nếu sử dụng định nghĩa ƯCLN(0, 0) = 0 và BCNN(0, 0) = 0 thì khi đó tập các số tự nhiên trở thành một dàn đầy đủ phân phối với ƯCLN làm [[*Trong Hệ tọa độ Descartes, ƯCLN(a, b) biểu diễn số các điểm với tọa độ nguyên trên đoạn thẳng nối các điểm (0, 0) và (a, b), trừ chính điểm (0, 0).
[sửa] Tham khảo
- Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.2: The Greatest Common Divisor, pp.333–356.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp.856–862.
- Saunders MacLane and Garrett Birkhoff. A Survey of Modern Algebra, Fourth Edition. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1-7: "The Euclidean Algorithm."
[sửa] Liên kết ngoài
Ước số chung lớn nhất - theo chủ đề
Ước số chung lớn nhất - Dự án liên quan
