Máy tính GCF

Công cụ khác

Máy tính diện tích{$ ',' | translate $}
Máy tính chu vi{$ ',' | translate $}
Máy tính toán thể tích{$ ',' | translate $}
Bảng cửu chương{$ ',' | translate $}
Bảng tuần hoàn{$ ',' | translate $}
Máy tính ma trận{$ ',' | translate $}
Máy tính LCM{$ ',' | translate $}
Trình tính toán lượng giác{$ ',' | translate $}

Máy tính ước chung lớn nhất

Trước khi tiến hành định nghĩa khái niệm ước chung lớn nhất (GCD), cần phải hiểu ước chung nói chung là gì.

Một số nguyên có thể có nhiều ước. Chúng tôi quan tâm đến việc truy cập đồng thời vào chúng bởi một số số nguyên. Chúng tôi coi ước số chung của một số số nguyên là số có thể đóng vai trò là ước số cho mỗi số trong chuỗi đã chỉ định.

Ví dụ, các số 8 và 12 có các ước chung như sau: 1 và 4. Có thể dễ dàng xác minh điều này bằng cách viết các biểu thức toán học: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.

Cần lưu ý rằng ban đầu mỗi số có ít nhất hai ước chung: bất kỳ số nào cũng chia hết cho chính nó mà không có số dư và cũng chia hết cho 1.

Xác định ước chung lớn nhất

Ước chung lớn nhất (GCD) của hai số tự nhiên là số tự nhiên lớn nhất mà chúng ta có thể chia hai số của mình. Nếu giá trị của ước chung lớn nhất của hai số tự nhiên là 1 thì ta gọi hai số này là nguyên tố cùng nhau.

Với hai số a và b, ước chung lớn nhất là số mà a và b có thể chia không dư. Biểu thức này được viết như sau: gcd(a, b) = c.

Một cách khác để viết GCD: (a, b) = c. Tuy nhiên, trong hầu hết các trường hợp, tùy chọn đầu tiên được sử dụng.

Ví dụ, số 4 và số 16 có ước chung lớn nhất bằng 4. Hãy viết: gcd (4, 16) = 4.

Hãy mô tả cách chúng tôi đạt được kết quả này:

Ta viết ra tất cả các ước của số 4. Ta được: 4, 2, 1.
Tiếp theo, ta vẽ tất cả các ước của 16. Ta có: 16, 8, 4, 2, 1.
Ta chọn các ước chung cho cả 4 và 16. Ta có: 4, 2, 1.
Từ các ước số chung thu được, ước số lớn nhất đã được chọn. Đây là 4.
Ta nhận được đáp án: đối với số 4 và 16 GCD là 4.

Tương tự, bạn có thể tìm GCD cho ba số nguyên trở lên. Trong trường hợp này, nó sẽ là số nguyên lớn nhất mà bạn có thể chia tất cả các số từ chuỗi được đề xuất.

Vì vậy, ví dụ, ước số lớn nhất của các số nguyên 6, 12, 18, 42 sẽ là số 6, tức là gcd (6, 12, 18, 42) = 6. Câu trả lời có được nhờ một thuật toán tương tự như mô tả ở trên - đối với các số trong một chuỗi, tất cả các ước số được viết ra tuần tự, sau đó số lớn nhất được chọn.

Thuộc tính GCD

Ước chung lớn nhất có một số thuộc tính phù hợp với GCD của các số nguyên dương có ước lớn hơn 0.

Thuộc tính 1

Từ việc thay đổi vị trí của các số, giá trị cuối cùng của GCD sẽ không thay đổi. Bạn có thể viết câu lệnh này như sau:

gcd(a, b) = gcd(b, a).

Thuộc tính 2

Nếu a chia hết cho b thì tập hợp các ước chung của a và b bằng tập hợp các ước của b. Được viết như thế này:

gcd(a, b) = b.

Tính chất ước số lớn nhất đã được chứng minh có thể được sử dụng để tìm gcd của hai số khi một trong số chúng chia hết cho số kia. Trong trường hợp này, GCD bằng một trong các số này, mà một số khác chia hết.

Ví dụ:

gcd(12, 4) = 4.

Tương tự:

gcd(10, 1) = 1.

Thuộc tính 3

Nếu a = bq + c, trong đó a, b, c và q là các số nguyên thì tập hợp các ước chung của a và b bằng tập hợp các ước chung của b và c.

Đẳng thức gcd (a, b) = gcd (b, c) trở nên hợp lệ.

Thuộc tính 4

Biểu thức gcd(ma, mb) = m ⋅ gcd(a, b) đúng với điều kiện m là số tự nhiên bất kỳ.

Thuộc tính 5

Giả sử p là ước chung bất kỳ của a và b.

Sau đó:

gcd(a / p, b / p) = gcd(a, b) / p.

Nếu p = gcd(a, b), ta có:

gcd (a / gcd (a, b), b / gcd (a, b)) = 1,

Như vậy, các số a / gcd (a, b) và b / gcd (a, b) nguyên tố cùng nhau.

Thuộc tính 6

Hai số bất kỳ có ít nhất một ước chung - đó là số 1.

Kiến thức về cơ sở lý thuyết của khái niệm GCD, cũng như các kỹ năng thực hành trong định nghĩa của nó, là cần thiết để làm việc với các phân số thông thường. Ngoài ra, GCD có liên quan chặt chẽ với một đơn vị toán học khác - ước số chung nhỏ nhất. Cả hai định nghĩa thường được nghiên cứu như một phần của chương trình giảng dạy tiêu chuẩn ở trường.

Cách tìm ước chung lớn nhất

Tìm ước chung lớn nhất (gcd) là một nhiệm vụ khá phổ biến. Thao tác này giúp chúng tôi thực hiện các phép tính trong đó các phân số thông thường xuất hiện.

Các phương pháp tìm GCD

Có một số thủ thuật để tìm ước chung lớn nhất. Chúng tôi sẽ xem xét những cách phổ biến nhất trong số đó.

Tìm ƯCLN bằng phân tích các số thành thừa số nguyên tố

Phương pháp này là một trong những phương pháp được sử dụng thường xuyên nhất để giải các bài toán.

Thuật toán xác định GCD có phân tích thành thừa số nguyên tố bao gồm các bước sau:

Chúng ta biểu diễn các số dưới dạng thừa số nguyên tố. Ví dụ: số 20 có thể được biểu diễn dưới dạng tích của 2 ⋅ 2 ⋅ 5.
Chọn các yếu tố sẽ có trong cả hai phần mở rộng.
Tìm tích của các thừa số này.

Hãy xem xét một số ví dụ về ứng dụng của thuật toán này trong thực tế:

Xác định GCD của số 12 và số 8.

Tách 12 và 8 thành thừa số nguyên tố:

12 = 2 ⋅ 2 ⋅ 3.
8 = 2 ⋅ 2 ⋅ 2.

Chúng tôi xem xét những yếu tố nào có mặt trong cả hai bản mở rộng. Tìm: 2 và 2.

Chúng ta nhân các thừa số và nhận được:

2 ⋅ 2 = 4.

Đáp án: gcd (12, 8) = 4.

Xác định ƯCLN của các số 75 và 150.

Trình tự giải pháp tương tự như ví dụ trước.

Hãy biểu diễn 75 và 150 dưới dạng thừa số nguyên tố:

75 = 3 ⋅ 5 ⋅ 5.
150 = 2 ⋅ 3 ⋅ 5 ⋅ 5.

Xác định các thừa số lặp lại trong cả hai lần mở rộng: 3, 5 và 5.

Chúng ta nhân các số có được với nhau: 3 ⋅ 5 ⋅ 5 = 75.

Đáp số: gcd (75, 150) = 75.

Xác định ƯCLN của các số 9 và 5.

Ví dụ này sử dụng các số nguyên tố có bội số chỉ có thể là 1.

Khi quy 9 và 5 thành thừa số nguyên tố ta sẽ thấy chúng không có cùng thừa số:

5 = 5.
9 = 3 ⋅ 3.

Phải nhớ rằng trường hợp này là đặc biệt. Những số như vậy là nguyên tố cùng nhau và ước chung của chúng là một.

Thuật toán Euclid

Thuật toán này được đặt theo tên của nhà toán học Hy Lạp cổ đại Euclid, người đầu tiên mô tả thuật toán này trong các tác phẩm của ông (cuốn sách thứ 7 và thứ 10 của "Sự khởi đầu"). Được biết, Euclid không phải là tác giả của thuật toán này. Tuy nhiên, nó được coi là một trong những thuật toán lâu đời nhất được sử dụng ngày nay.

Thuật toán Euclid giúp dễ dàng tính ước chung lớn nhất của hai số dương.

Để tìm GCD (a, b), thuật toán này như sau:

Nếu a = 0 thì gcd(a, b) = b vì gcd(0, b) = b và thuật toán dừng lại.
Nếu b = 0 thì gcd(a, b) = a vì gcd(a, 0) = a và thuật toán dừng lại.
Chia a cho b có dư (a = b ⋅ q + r)
Tìm gcd(b, r) bằng thuật toán Euclid vì gcd(a, b) = gcd(b, r).

Để xác minh tính hiệu quả của phương pháp trong thực tế, hãy xem xét một ví dụ.

Cần xác định GCD của các số 270 và 192.

a = 270, b = 192.
a ≠ 0.
b ≠ 0.

Chia a cho b, ta được:

270 / 192 = 1 (số dư là 78).

Bạn có thể viết kết quả dưới dạng: 270 = 192 ⋅ 1 + 78.

Tiếp theo, chúng ta sẽ tính gcd (192, 78), vì gcd (270, 192) = gcd (192, 78).

Hãy tiếp tục.

a = 192, b = 78.
a ≠ 0.
b ≠ 0.

Chia a cho b, ta được:

192 / 78 = 2 (số dư là 36).

Có thể viết là:

192 = 78 ⋅ 2 + 36.

Tính gcd(78, 36) vì gcd(192, 78) = gcd(78, 36).

a = 78, b = 36.
a ≠ 0.
b ≠ 0.

Chia a cho b, ta được:

78 / 36 = 2 (số dư là 0).

Hãy viết kết quả là:

78 = 36 ⋅ 2 + 6.

Tính gcd(36, 6) vì gcd(78, 36) = gcd(36, 6).

a = 36, b = 6.
a ≠ 0.
b ≠ 0.

Chia A cho B ta được 36 / 6 = 6 (số dư là 0).

Viết kết quả theo mẫu sau:

36 = 6 ⋅ 6 + 0.

Tiếp theo, chúng ta tìm gcd(6, 0) vì gcd(36, 6) = gcd(6, 0).

a = 6, b = 0.
a ≠ 0.
b = 0.

Kết quả là chúng ta có:

gcd(6, 0) = 6.

Như vậy, chúng ta có trình tự tính toán như sau:

gcd(270, 192) = gcd(192, 78) = gcd(78, 36) = gcd(36, 6) = gcd(6, 0) = 6.

Kết quả là chúng ta có câu trả lời:

gcd(270, 192) = 6.

Mỗi phương pháp tìm kiếm được thảo luận ở trên đều có ưu điểm và nhược điểm. Phương pháp đầu tiên rất phù hợp để làm việc với các ví dụ tương đối đơn giản, không giống như phương pháp thứ hai, phương pháp này có thể dùng để giải các bài toán phức tạp hơn.