Table of Contents
Thuật toán Euclid để tìm ước chung lớn nhất (ƯCLN) là gì? Ta sẽ đi tìm hiểu cách tìm ước chung lớn nhất của hai số bằng cách áp dụng thuật Toán Euclid trong bài viết dưới đây.
1. Thuật toán Euclid là gì?
Thuật toán Euclid là thuật toán đi tìm ước chung lớn nhất của hai số nguyên, thuật toán này là một trong những thuật toán được sử dụng lâu đời nhất, tên gọi của thuật toán này được đặt theo tên của nhà Toán học vĩ đại Euclid.
2. 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ố đã cho, ta lấy số lớn hơn chia cho số nhỏ hơn;
- Bước 2: Nếu phép tính chia vừa thực hiện ở Bước 1 còn dư thì ta tiếp tục lấy số chia đem chia cho số dư. Ta cứ tiếp tục thực hiện như vậy cho tới khi ta nhận được số dư bằng 0 thì ta dừng lại;
- Bước 3: Số chia trong phép chia hết cuối cùng nhận được chính là ước chung lớn nhất mà ta cần tìm.
Nhận xét: Trong việc tìm ước chung lớn nhất của cặp số lớn nào đó, người ta thường dùng thuật toán Euclid để tìm nó.
» Xem thêm: Ước chung lớn nhất là gì? Cách tìm và bài tập vận dụng
Ví dụ 1. Hãy áp dụng thuật toán Euclid để tìm ước chung lớn nhất của cặp số sau đây: 234 và 192.
Lời giải
+ Bước 1: 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 đem chia cho số dư, ta được
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 đem chia cho số dư, ta được
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 đem chia cho số dư, ta được
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 đem chia cho số dư, ta được
18 : 6 = 3 (dư 0) (5)
- Phép chia (5) là phép chia 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 cùng chính là ước chung lớn nhất mà ta cần tìm.
Do đó, ƯCLN (234, 192) = 6.
Bài tập luyện tập: Hãy áp dụng thuật toán Euclid để tìm ước chung lớn nhất của cặp số sau đây: 124 và 217.
ĐÁP ÁN
+ Bước 1: Lấy số lớn hơn chia cho số nhỏ hơn, ta được
217 : 124 = 1 (dư 93) (1)
+ Bước 2:
- Ta thấy phép chia (1) là phép chia có dư nên ta lấy số chia đem chia cho số dư, ta được
124 : 93 = 1 (dư 31) (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
93 : 31 = 3 (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: Số chia 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 (124, 217) = 31.
3. Một số bài tập tìm ước chung lớn nhất bằng thuật toán Euclid
Bài 1. Hãy cho biết bước tính toán đầ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ì?
- Nhân hai số a và b với nhau.
- Cộng hai số a và b với nhau.
- Chia số a cho số b.
- Trừ số a cho số b.
ĐÁP ÁN
Bước tính toán đầ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ố đó là chia số lớn hơn cho số nhỏ hơn, vì a > b, do đó ta chia số a cho số b.
Chọn đáp án C.
Bài 2. Hãy áp dụng thuật toán Euclid để tìm ước chung lớn nhất của cặp số sau đây: 2468 và 1652.
ĐÁP ÁN
+ 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:
- Ta thấy phép chia (1) là phép chia có dư nên ta lấy số chia đem chia cho số dư, ta được
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ố chia đem chia cho số dư, ta được
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ố chia đem chia cho số dư, ta được
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ố chia đem chia cho số dư, ta được
16 : 4 = 4 (dư 0) (5)
- Phép chia (5) là phép chia 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 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. Bạn Quỳnh thực hiện tìm ước chung lớn nhất của hai số 340 và 155 bằng cách áp dụ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:
- Ta thấy 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 của bạn Quỳnh như trên có đúng không? Nếu bạn Quỳnh làm sai, em hãy chỉ ra lỗi sai đó và sửa lại cho bạn Quỳnh.
ĐÁP ÁN
Trả lời: Bài làm của bạn Quỳnh là sai.
Giải thích: Ở Bước 3 bạn Quỳnh đã lấy thương trong phép chia hết cuối cùng là ước chung lớn nhất cần tìm, điều này là không đúng.
Sửa lại Bước 3: Số chia 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) = 5.
Bài 4. Để chuẩn bị cho một bữa tiệc của các bạn nhỏ tại một tòa nhà, các bác đầu bếp đã chuẩn bị nguyên liệu để làm món chiên, trong đó có 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.
ĐÁP ÁN
Việc chia 105 cánh gà và 70 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 đó là đi tìm ước chung lớn nhất của hai số 105 và 70.
Ta sẽ tìm ước chung lớn nhất của hai số 105 và 70 bằng cách sử dụng thuật toán Euclid.
+ Bước 1: Lấy số lớn hơn chia cho số nhỏ hơn, ta được
105 : 70 = 1 (dư 35) (1)
+ Bước 2:
- Ta thấy phép chia (1) là phép chia có dư nên ta lấy số chia đem chia cho số dư, ta được
70 : 35 = 2 (dư 0) (2)
- Phép chia (2) là phép chia 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 cùng chính là ước chung lớn nhất mà ta cần tìm.
Do đó, ƯCLN (105, 70) = 35.
Vậy các bác đầu bếp có thể chia số cánh gà và chân gà đó thành nhiều nhất 35 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.
Bài viết trên đã trình bày cho các em cách tìm ước chung lớn nhất của hai số bất kỳ bằng cách áp dụng thuật toán Euclid. Hy vọng qua bài viết này các em học sinh có thể áp dụng thành thạo chúng vào giải quyết các bài toán khó.
Chịu trách nhiệm nội dung: GV Nguyễn Thị Trang