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

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm

Trong toán học, ước số chung lớn nhất (ƯSCLN) 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 chia hết cho mỗi số đó. Ví dụ, ước chung lớn nhất của 6 và 15 là 3 vì .

Trong tiếng Anh, ước chung lớn nhất gọi là greatest common divisor (gcd), greatest common factor (gcf),[1] highest common factor (hcf),[2] greatest common measure (gcm),[3] hay highest common divisor.[4]

Trong trường hợp cả hai số nguyên ab đều bằng 0 thì chúng không có ƯCLN vì khi đó mọi số tự nhiên khác không đều là ước chung của ab. Nếu chỉ một trong hai số a hoặc b bằng 0, số kia khác 0 thì ƯCLN của chúng bằng giá trị tuyệt đối của số khác 0.

Tổng quan[sửa | sửa mã nguồn]

Ký hiệu[sửa | sửa mã nguồn]

Ước chung lớn nhất của ab được ký hiệu là ƯCLN(ab), hay đơn giản hơn là (ab), tiếng Anh ký hiệu là gcd(a,b).

Ví dụ[sửa | sửa mã nguồn]

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

Ta có:

  • Các ước của 27 là .
  • Các ước của 45 là .

Những số nằm trong cả hai danh sách được gọi là những ước chung của 27 và 45:

Trong đó số lớn nhất là 9. Vậy 9 là ước chung lớn nhất của 27 và 45. Viết:

Số nguyên tố cùng nhau[sửa | sửa mã nguồn]

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 bằng 1. Chẳng hạn, 9 và 28 là hai số 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 đó,

Các tính chất[sửa | sửa mã nguồn]

  • Mọi ước chung của ab là ước của ƯCLN(ab).

Bước 0 29 8 5 3 1 0 1 0 1 -3 1 8 5 3 1 0 1 -1 1 -3 4 2 5 3 2 1 1 -1 2 -3 4 -7 3 3 2 1 1 -1 2 -3 4 -7 11 4 2 1 0 2

  • ƯCLN(ab), khi ab không bằng không cả hai, có thể được định nghĩa tương đương như số nguyên dương d nhỏ nhất có dạng d = a·p + b·q trong đó pq là các số nguyên. Định lý này được gọi là đẳng thức Bézout. Các số pq 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(ab) = d, thì a/d là ước của c.
  • Nếu m là số nguyên dương, thì ƯCLN(m·am·b) = m·ƯCLN(ab).
  • Nếu m là số nguyên bất kỳ, thì ƯCLN(a + m·bb) = ƯCLN(ab). Nếu m ước chung (khác 0) của ab, thì UCLN(a/mb/m) = ƯCLN(ab)/m.
  • ƯCLN là một hàm có tính nhân theo nghĩa sau: nếu a1a2 là nguyên tố cùng nhau, thì ƯCLN(a1·a2b) = ƯCLN(a1b)·ƯCLN (a2b).
  • ƯCLN là hàm giao hoán: ƯCLN(a, b) = ƯCLN(b, a).
  • ƯCLN là hàm kết hợp: ƯCLN(a, ƯCLN(b, c)) = ƯCLN(ƯCLN(a, b), c).
  • ƯCLN của ba số được tính nhờ công thức ƯCLN(abc) = ƯCLN(ƯCLN(ab), c), (hoặc vế kia của tính chất kết hợp. Điều này có thể mở rộng cho số bất kỳ các số nguyên.
  • ƯCLN (ab) quan hệ chặt chẽ với BCNN(ab): ta có
ƯCLN(ab)·BCNN(ab) = 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:

(ab), ƯCLN(ac))

BCNN(a, ƯCLN(bc)) = ƯCLN(BCNN(ab), BCNN(ac)).
  • 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.
  • Trong Hệ tọa độ Descartes, ƯCLN(ab) 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à (ab), trừ chính điểm (0, 0).

Tính toán[sửa | sửa mã nguồn]

Ư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 với số mũ dương nhỏ 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 ab là các số khác không, thì ước chung lớn nhất của ab có thể tính qua bội chung nhỏ nhất (BCNN) của ab:

Chú thích[sửa | sửa mã nguồn]

  1. ^ Kelley, W. Michael (2004), The Complete Idiot's Guide to Algebra, Penguin, tr. 142, ISBN 9781592571611 .
  2. ^ Jones, Allyn (1999), Whole Numbers, Decimals, Percentages and Fractions Year 7, Pascal Press, tr. 16, ISBN 9781864413786 .
  3. ^ Barlow, Peter; Peacock, George; Lardner, Dionysius; Airy, Sir George Biddell; Hamilton, H. P.; Levy, A.; De Morgan, Augustus; Mosley, Henry (1847), Encyclopaedia of Pure Mathematics, R. Griffin and Co., tr. 589 .
  4. ^ Hardy & Wright (1979, tr. 20)

Đọc thêm[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]