Tính ước chung lớn nhất

Ước chung lớn nhất (UCLN) là gì?

Ước chung lớn nhất (ƯCLN) của hai hay nhiều số nguyên không đồng thời bằng không, còn được gọi là ước số chung lớn nhất, là số nguyên dương lớn nhất mà có thể chia hết cho tất cả các số trong tập số đó mà không để lại số dư.

Phương pháp Phân tích thừa số nguyên tố

Phương pháp phân tích thừa số nguyên tố để tính Ước chung lớn nhất (UCLN) bao gồm việc chia các số ra thành các thừa số nguyên tố cơ bản của chúng, sau đó so sánh các thừa số này để tìm ra thừa số lớn nhất mà chúng có chung. Dưới đây là hướng dẫn từng bước cách sử dụng phương pháp này:

Các bước của phương pháp Phân tích thừa số nguyên tố:

• Liệt kê các thừa số nguyên tố: Phân tích mỗi số ra thành các thừa số nguyên tố của nó. Bạn có thể làm điều này bằng cách chia số đó cho các số nguyên tố bắt đầu từ nhỏ nhất (2, 3, 5, 7, 11, ...) cho đến khi bạn chỉ còn lại số 1.
• Tạo Cây thừa số nguyên tố (tùy chọn): Đặc biệt hữu ích cho những người học trực quan, việc tạo một cây thừa số cho mỗi số có thể giúp dễ dàng hình dung. Đây là một sơ đồ phân nhánh nơi bạn viết số cần phân tích ở đầu và vẽ các nhánh cho từng bước phân tích cho đến khi bạn đạt được các số nguyên tố ở các đầu nhánh.
• Xác định các thừa số chung: So sánh các danh sách thừa số nguyên tố và đánh dấu hoặc ghi chú các thừa số xuất hiện trong tất cả các danh sách. Đảm bảo bao gồm cả thừa số nguyên tố chung nhỏ nhất nếu chúng xuất hiện nhiều lần.
• Nhân các thừa số nguyên tố chung: Nhân các thừa số nguyên tố chung lại với nhau để tìm ra UCLN.

Ví dụ:

Hãy tìm UCLN của 84 và 120 bằng cách phân tích thừa số nguyên tố. Đầu tiên, chúng ta phân tích mỗi số ra thành các thừa số nguyên tố của nó:

• 84 = 2×2×3×7 = 2²×3×7
• 120 = 2×2×2×3×5 = 2³×3×5

Bây giờ, xác định các thừa số nguyên tố chung. Trong trường hợp này, các thừa số nguyên tố chung của 84 và 120 là hai số 2 và một số 3:

• Thừa số nguyên tố chung: 2²×3

Tiếp theo, nhân các số này lại với nhau:

• UCLN: 2×2×3 = 4×3 = 12

Vậy, UCLN của 84 và 120 là 12.

Phương pháp Liệt kê các Ước số

Phương pháp "Liệt kê các Ước số" để tính Ước chung lớn nhất (UCLN) bao gồm việc liệt kê tất cả các ước số của các số bạn đang xem xét và sau đó xác định ước số lớn nhất mà chúng có chung. Dưới đây là cách thực hiện từng bước:

Các bước cho Phương pháp Liệt kê các Ước số:

1. Liệt kê tất cả các Ước số của mỗi Số: Viết ra tất cả các số mà chia hết cho các số đã cho mà không để lại số dư. Đây là các ước số của mỗi số.
2. Xác định các Ước số Chung: So sánh các danh sách và tìm các ước số mà chung cho tất cả các số.
3. Chọn Ước chung lớn nhất: Từ danh sách các ước số chung, chọn ra số lớn nhất. Đây chính là UCLN.

Ví dụ:

Hãy tìm UCLN của 30 và 45 bằng phương pháp liệt kê.

1. Liệt kê tất cả các Ước số:
   • Các ước số của 30: 1, 2, 3, 5, 6, 10, 15, 30
   • Các ước số của 45: 1, 3, 5, 9, 15, 45
2. Xác định các Ước số Chung:
   • Các ước số chung của 30 và 45 là: 1, 3, 5, 15
3. Chọn Ước chung lớn nhất:
   • Ước số lớn nhất mà 30 và 45 có chung là 15.

Vậy, UCLN của 30 và 45 là 15.

Phương pháp Thuật toán Euclid

Thuật toán Euclid là một kỹ thuật đã được sử dụng từ lâu để tìm Ước chung lớn nhất (UCLN) của hai số. Nó dựa trên nguyên tắc rằng UCLN của hai số cũng là UCLN của hiệu số của chúng. Quá trình này lặp lại cho đến khi số dư là 0, tại thời điểm đó UCLN chính là số dư không bằng 0 cuối cùng.

Các bước của Thuật toán Euclid:

1. Bắt đầu với Hai Số: Xác định hai số, a và b, sao cho a > b, để bạn tìm UCLN.
2. Chia a cho b: Thực hiện phép chia của a cho b, và ghi chú lại số dư r. Về mặt toán học, điều này là a = bq + r, nơi q là thương.
3. Cập nhật a và b: Thay thế a bằng b và b bằng r (số dư).
4. Lặp lại Phép Chia: Tiếp tục quá trình chia a mới cho b mới và cập nhật chúng tương ứng.
5. Kết quả Khi Số Dư là Không: Khi bạn đạt được số dư là 0, số chia (b) tại bước đó là UCLN của hai số ban đầu.

Ví dụ:

Hãy sử dụng Thuật toán Euclid để tìm UCLN của 48 và 18.

1. Chia 48 cho 18: 48 ÷ 18 = 2 với số dư là 12.
2. Bây giờ, thay thế 48 bằng 18 (số chia trước đó), và 18 bằng 12 (số dư): 18 ÷ 12 = 1 với số dư là 6.
3. Tiếp theo, thay thế 18 bằng 12, và 12 bằng 6 (số dư mới): 12 ÷ 6 = 2 với số dư là 0.

Vì số dư bây giờ là 0, chúng ta dừng lại. Số chia tại bước này, là 6, chính là UCLN của 48 và 18.

Vậy, UCLN của 48 và 18 là 6.

Thuật toán này đặc biệt mạnh mẽ đối với các số lớn vì nó giảm đáng kể lượng tính toán so với các phương pháp khác như liệt kê tất cả các ước số. Đây là một ví dụ xuất sắc về cách một thuật toán toán học đơn giản có thể được áp dụng để giải quyết các vấn đề ban đầu có vẻ như cần nhiều tính toán.