gcf là gì

Bách khoa toàn thư banh Wikipedia

Trong toán học tập, ước số cộng đồng rộng lớn nhất (ƯCLN) hoặc ước cộng đồng rộng lớn nhất (ƯCLN) của nhì hoặc nhiều số nguyên vẹn là số nguyên vẹn dương lớn số 1 là ước số cộng đồng của những số cơ. Ví dụ, ước cộng đồng lớn số 1 của 6 và 15 là 3 vì như thế và .

Bạn đang xem: gcf là gì

Trong giờ Anh, ước cộng đồng lớn số 1 gọi là greatest common divisor (GCD), greatest common factor (GCF),^[1] highest common factor (HCF),^[2] greatest common measure (GCM),^[3] hoặc highest common divisor (HCD).^[4]

Trong tình huống toàn bộ số nguyên vẹn đều vì như thế 0 thì bọn chúng không tồn tại ƯCLN vì như thế Khi cơ từng số bất ngờ không giống không được đều là ước cộng đồng của những số cơ. Nếu trong những số cơ sở hữu tối thiểu một trong những vì như thế 0 và tối thiểu một trong những không giống 0 thì ƯCLN của bọn chúng vì như thế ƯCLN của những số không giống 0.

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

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

Ước cộng đồng lớn số 1 của a₀, a₁, a₂,... a_n được ký hiệu là ƯCLN(a₀, a₁, a₂,... a_n)

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

Tìm ước cộng đồng lớn số 1 của 27 và 45?

Ta có:

Những số ở trong cả nhì list được gọi là những ước cộng đồng của 27 và 45:

Trong cơ số lớn số 1 là 9. Vậy 9 là ước cộng đồng lớn số 1 của 27 và 45. Viết UCLN(27,45)=9

Số yếu tố nằm trong nhau[sửa | sửa mã nguồn]

Các số được gọi là số yếu tố bên nhau nếu như ước cộng đồng lớn số 1 của bọn chúng vì như thế 1. Chẳng hạn, 9 và 28 là nhì số yếu tố bên nhau.

Xem thêm: acquire nghĩa là gì

Ước cộng đồng lớn số 1 được dùng để mang một phân số về dạng phân số tối giản. Chẳng hạn, ƯCLN(42, 56)=14, vì thế,

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

• Mọi ước cộng đồng của những số là ước của ƯCLN của những só cơ.
• Với những số nguyên vẹn a₀, a₁, a₂,... a_n, ƯCLN(a₀, a₁, a₂,... a_n) hoàn toàn có thể được khái niệm tương tự như số nguyên vẹn dương d nhỏ nhất sở hữu dạng d =  nhập cơ x_k là những số nguyên vẹn. Định lý này được gọi là đẳng thức Bézout. Các số x_k hoàn toàn có thể tính nhờ Giải thuật Euclid không ngừng mở rộng.
• ƯCLN(a, 0) =|a|, với từng a ≠ 0, vì như thế từng số không giống 0 ngẫu nhiên là ước của 0, và ước lớn số 1 của a là|a|. Đây là tình huống hạ tầng nhập 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 vẹn dương, thì ƯCLN(ma₀, ma₁, ma₂,...ma_n) = m · ƯCLN(a₀, a₁, a₂,... a_n).
• Nếu m là số nguyên vẹn ngẫu nhiên, thì ƯCLN(a + m · b, b) = ƯCLN(a, b). Nếu m ước cộng đồng (khác 0) của a và b, thì UCLN(a/m, b/m) = ƯCLN(a, b)/m.
• ƯCLN là một trong những hàm sở hữu tính nhân theo đòi nghĩa sau: nếu như những số a₁, a₂,...,a_n là những số yếu tố bên nhau, thì ƯCLN(a₁ · a₂ · ... · a_n, b) = ƯCLN(a₁, b) · ƯCLN (a₂, b) · ... · ƯCLN (a_n, b).
• ƯCLN là hàm phú 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) mối liên hệ nghiêm ngặt với BCNN(a, b): tao có

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

Công thức này thông thường được dùng làm tính BCNN của 2 số. Dạng không giống của quan hệ này là đặc điểm phân phối:

BCNN(a, ƯCLN(a₀, a₁, a₂,... a_n)) = ƯCLN(BCNN(a, a₀), BCNN(a, a₁), BCNN(a,a₂),...,BCNN(a,a_n)).

• Nếu dùng khái niệm ƯCLN(0, 0) = 0 và BCNN(0, 0) = 0 thì Khi cơ luyện những số bất ngờ trở nên một dàn tương đối đầy đủ phân phối với ƯCLN.
• Trong Hệ tọa chừng Descartes, ƯCLN(a, b) màn biểu diễn số những điểm với tọa chừng nguyên vẹn bên trên đoạn trực tiếp nối những điểm (0, 0) và (a, b), trừ chủ yếu điểm (0, 0).

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

Tìm ước cộng đồng lớn số 1 bằng phương pháp phân tách đi ra quá số nguyên vẹn tố[sửa | sửa mã nguồn]

Định lý cơ phiên bản của số học tập bảo rằng từng số nguyên vẹn dương to hơn 1 hoàn toàn có thể màn biểu diễn một cơ hội độc nhất dạng tích những số yếu tố (nếu ko kể tới trật tự của những quá số). Như vậy những thích hợp số hoàn toàn có thể coi như thể những yếu tố cấu trở thành thích hợp số. Ví dụ:

Ở phía trên tất cả chúng ta sở hữu thích hợp số 90 tạo nên trở thành vì như thế một nguyên vẹn tử 2, nhì nguyên vẹn tử 3 và một nguyên vẹn tử 5.

Kiến thức này hoàn toàn có thể canh ty tất cả chúng ta mò mẫm ƯCLN của một tập trung những số.

Ví dụ: Tìm độ quý hiếm của ƯCLN(12, 32, 60).

Đầu tiên, tao phân tách từng số trở thành dạng thu thập quá những số yếu tố.

Với từng quá số yếu tố có chung nhập toàn bộ những số, nâng lũy quá bậc thấp nhất, tích của bọn chúng mang đến tao độ quý hiếm ƯCLN cần thiết mò mẫm. Thừa số 2 sở hữu ở cả tía số, sở hữu bậc thấp nhất là 2². Do đó:

Trên thực tiễn cách thức này chỉ người sử dụng cho những số nhỏ. Việc phân tách những số rộng lớn đi ra quá số yếu tố mất mặt thật nhiều thời hạn.

Xem thêm: gara là gì

Để mò mẫm ƯCLN của 2 số bất ngờ thì cách thức hiệu suất cao là giải thuật Euclid dựa vào sản phẩm liên tục những luật lệ phân chia sở hữu dư.

Tính qua loa bội số cộng đồng nhỏ nhất[sửa | sửa mã nguồn]

Nếu a và b là những số không giống ko, thì ước cộng đồng lớn số 1 của a và b hoàn toàn có thể tính qua loa bội cộng đồng nhỏ nhất (BCNN) của a và b:

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

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

• 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 tát 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 và Garrett Birkhoff. A Survey of Modern Algebra, Fourth Edition. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1-7: "The Euclidean Algorithm."

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

• GCD Implementation in C++
• greatest common divisor bên trên Everything2.com
• Greatest Common Measure: The Last 2500 Years, by Alexander Stepanov