Thuật toán Euclid được biết đến là một phương pháp dùng để tìm ước chung lớn nhất. Vậy cách sử dụng thuật toán này như thế nào? Chúng ta cùng tìm hiểu trong bài viết sau đây cùng các bài tập áp dụng nhé.
Thuật toán Euclid là gì?
Thuật toán Euclid (Euclidean Algorithm) là thuật toán để tìm ước chung lớn nhất (ƯCLN) của hai số nguyên. Đây được coi là một trong những thuật toán được sử dụng tìm ƯCLN lâu đời nhất. Thuật toán này được tạo ra bởi nhà Toán học vĩ đại Euclid.
Cách tìm ước chung lớn nhất bằng Thuật toán Euclid
Để tìm ƯCLN bằng thuật toán Euclid thì bạn thực hiện theo các bước sau:
Thuật toán Euclid tìm ước chung lớn nhất
Muốn tìm ước chung lớn nhất của hai số bất kỳ bằng thuật toán Euclid, ta cần thực hiện các bước sau đây:
- Bước 1: Trong hai số nguyên đã cho, ta lấy số lớn hơn chia cho số nhỏ hơn
- Bước 2: Nếu phép chia vừa thực hiện còn dư thì ta tiếp tục lấy số chia đem chia cho số dư. Thực hiện lặp lại phép chia này cho đến khi ta nhận được số dư bằng 0.
- Bước 3: Ước chung lớn nhất của 2 số nguyên đó chính là số chia trong phép chia hết cuối cùng mà không còn dư.
Ví dụ: Hãy áp dụng thuật toán Euclid để tìm ước chung lớn nhất của cặp số 234 và 192.
Lời giải
Bước 1: Trong cặp số này, số lớn hơn là 234. Lấy số lớn hơn chia cho số nhỏ hơn, ta được
234 : 192 = 1 (dư 42) (1)
Bước 2:
Ta thấy phép chia (1) là phép chia có dư nên ta lấy số chia (192) đem chia cho số dư (42), ta được phép tính:
192 : 42 = 4 (dư 24) (2)
Phép chia (2) vẫn là phép chia có dư nên ta tiếp tục lấy số chia (42) đem chia cho số dư (24), ta được phép tính:
42 : 24 = 1 (dư 18) (3)
Phép chia (3) vẫn là phép chia có dư nên ta tiếp tục lấy số chia (24) đem chia cho số dư (18), ta được phép tính:
24 : 18 = 1 (dư 6) (4)
Phép chia (4) vẫn là phép chia có dư nên ta tiếp tục lấy số chia (18) đem chia cho số dư (6), ta được phép tính:
18 : 6 = 3 (dư 0) (5)
Phép chia (5) cho ra kết quả với số dư bằng 0 nên ta dừng lại.
Bước 3: Số chia trong phép chia hết cuối cùng (số 6) chính là ước chung lớn nhất mà ta cần tìm.
Do đó, ƯCLN (234, 192) = 6.
Bài tập áp dụng thuật toán Euclid tìm ước chung lớn nhất
Bài 1. Hãy cho biết phép tính đầu tiên trong việc áp dụng thuật toán Euclid vào tìm ước chung lớn nhất của hai số a và b (a > b) là gì?
A. Cộng hai số a và b với nhau.
B. Nhân hai số a và b với nhau.
C. Chia số a cho số b.
D. Trừ số a cho số b.
Đáp án C
Bước đầu tiên của thuật toán Euclid đó là lấy số lớn hơn chia cho số nhỏ hơn.
Bài 2. Tìm ước chung lớn nhất của cặp số 2468 và 1652 bằng thuật toán Euclid
Bước 1: Lấy số lớn hơn chia cho số nhỏ hơn, ta được
2468 : 1652 = 1 (dư 816) (1)
Bước 2: Phép chia (1) còn dư nên lấy 1652 chia cho 816.
1652 : 816 = 2 (dư 20) (2)
Phép chia (2) vẫn là phép chia có dư nên ta tiếp tục lấy số 816 chia cho 20.
816 : 20 = 40 (dư 16) (3)
Phép chia (3) vẫn là phép chia có dư nên ta tiếp tục lấy số 20 chia cho 16.
20 : 16 = 1 (dư 4) (4)
Phép chia (4) vẫn là phép chia có dư nên ta tiếp tục lấy số 16 chia cho 4.
16 : 4 = 4 (dư 0) (5)
Phép chia (5) là có số dư bằng 0 nên ta dừng lại
Bước 3: Số chia trong phép chia hết cuối (số 4) cùng chính là ước chung lớn nhất mà ta cần tìm.
Do đó, ƯCLN (2468, 1652) = 4.
Bài 3. Một bạn thực hiện tìm ước chung lớn nhất của hai số 340 và 155 bằng thuật toán Euclid như sau:
Bước 1: Lấy số lớn hơn chia cho số nhỏ hơn, ta được
340 : 155 = 2 (dư 30) (1)
Bước 2: Do phép chia (1) là phép chia có dư nên ta lấy số chia đem chia cho số dư, ta được
155 : 30 = 5 (dư 5) (2)
Phép chia (2) vẫn là phép chia có dư nên ta tiếp tục lấy số chia đem chia cho số dư, ta được
30 : 5 = 6 (dư 0) (3)
Phép chia (3) là phép chia có số dư bằng 0, nên ta dừng lại
Bước 3: Thương trong phép chia hết cuối cùng chính là ước chung lớn nhất mà ta cần tìm.
Do đó, ƯCLN (340,155) = 6.
Em hãy cho biết bài làm trên có đúng không? Nếu sai, em hãy chỉ ra lỗi sai đó và sửa lại cho đúng.
Lời giải:
Cách giải trên đã đúng ở bước 1 và bước 2. Tuy nhiên, bước 3 bạn đã chọn ƯCLN là thương của phép chia cuối cùng là sai. Theo Thuật toán Euclid thì phải ƯCLN phải là số chia của phép tính cuối cùng.
Vậy ƯCLN (340,155) = 5
Bài 4. Để chuẩn bị cho một bữa tiệc thì các đầu bếp đã chuẩn bị nguyên liệu để làm món chiên bao gồm 105 cánh gà và 70 chân gà. Các bác đầu bếp có thể chia số cánh gà và chân gà đó thành nhiều nhất bao nhiêu phần ăn sao cho số cánh gà cũng như số chân gà được chia đều vào từng phần ăn của mỗi bạn.
Số phần ăn nhiều nhất mà có đều số cánh gà và chân gà là ước chung lớn nhất của 105 và 70.
Áp dụng thuật toán Euclid vào tìm ƯCLN của 105 và 70 như sau:
Bước 1. Lấy 105 chia 70
105 : 70 = 1 dư 35 (1)
Bước 2. Phép chia (1) còn dư nên ta lấy 70 chia 35.
70 : 35 = 2 dư 0 (2)
Phép tính (2) dư 0 nên ta dừng lại.
Bước 3: ƯCLN của 105 và 70 là số chia của phép tính (2)
ƯCLN (105, 70) = 35
Vậy các đầu bếp có thể chia thành nhiều nhất 35 suất ăn có số cánh gà và chân gà bằng nhau.
Trên đây là các thông tin về Thuật toán Euclid để tìm ước chung lớn nhất cho một cặp số nguyên. Mong rằng qua bài viết này sẽ giúp bạn có thêm nhiều kiến thức bổ ích để phục vụ cho công việc và học tập.
