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.