Thuật toán Euclid là gì? Cách tìm ước chung lớn nhất bằng Thuật toán Euclid

Thuật toán Euclid được biết đến là một phương pháp đơn giản và hiệu quả để tìm ước chung lớn nhất của hai số nguyên dương. Với sự linh hoạt và tính chính xác, thuật toán này đã trở thành một công cụ quan trọng trong toán học và lĩnh vực liên quan. Nhưng thực sự, làm thế nào chúng ta có thể áp dụng thuật toán này để tìm ra ước chung lớn nhất? Trong bài viết này, chúng ta sẽ khám phá cách sử dụng thuật toán Euclid, cùng với một số bài tập thực hành để củng cố kiến thức. Hãy cùng nhau khám phá chi tiết trong phần dưới đây.

Thuật toán Euclid, còn được gọi là thuật toán Euclid Euclide, là một phương pháp cổ điển được sử dụng để tìm ước chung lớn nhất (Greatest Common Divisor - GCD) của hai số nguyên dương. Thuật toán này được đặt tên theo Euclid, một nhà toán học Hy Lạp cổ đại, người đã mô tả nó trong tác phẩm của mình "Các phần tắt về số" (Elements).

Ý tưởng cơ bản của thuật toán Euclid là liên tục lặp lại phép chia số lớn cho số nhỏ hơn, cho đến khi chia hết. Khi đó, số chia sẽ là ước chung lớn nhất của hai số ban đầu.

Cách tìm ước chung lớn nhất bằng Thuật toán Euclid

Thuật toán Euclid là một phương pháp cổ điển để tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương. Dưới đây là cách thực hiện thuật toán Euclid:

• Bước 1: Xác định hai số nguyên dương cần tìm ƯCLN, gọi chúng là a và b trong đó a > b.

• Bước 2: Sử dụng thuật toán chia lấy dư, thực hiện các phép chia cho đến khi dư bằng 0:

  • Chia a cho b và gán phần dư cho r.
  • Gán a = b và b = r.
  • Lặp lại quá trình cho đến khi bằng 0.

• Bước 3: Kết quả cuối cùng của a chính là ƯCLN của hai số ban đầu.

Dưới đây là một ví dụ cụ thể:

Cho hai số a = 48 và b = 18 tìm ước chung lớn nhất bằng thuật toán Euclid

• Bước 1: 48 chia cho 18, dư 12.
• Bước 2: Gán a = 18, b = 12.
• Bước 3: 18 chia cho 12, dư 6.
• Bước 4: Gán a = 12, b = 6.
• Bước 5: 12 chia cho 6, dư 0.
• Bước 6: Vì dư bằng 0, nên ƯCLN của 48 và 18 là 6.

Đây chính là thuật toán Euclid. Nó rất hiệu quả và có thể áp dụng cho bất kỳ cặp số nguyên dương nào.

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)         

Bước 2: Phép chia (1) còn dư nên lấy 1652 chia cho 816.

1652 : 816 = 2 (dư 20)             

Phép chia 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)               

Phép chia 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)                     

Phép chia  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)                       

Phép chia 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  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)        

Bước 2: Do phép chia 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)                   

Phép chia  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)                       

Phép chia 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 

Bước 2. Phép chia  còn dư nên ta lấy 70 chia 35.

70 : 35 = 2 dư 0 

Phép tính 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 

Ư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.

Lời kết

Thuật toán Euclid là một phương pháp cổ điển và hiệu quả để tìm ước chung lớn nhất của hai số nguyên dương. Được đặt tên theo nhà toán học cổ đại Euclid, thuật toán này dựa trên việc liên tục chia số lớn hơn cho số nhỏ hơn và lặp lại quá trình này cho đến khi đạt được phần dư là 0. Bằng cách này, ta có thể nhanh chóng và đáng tin cậy tìm ra ước chung lớn nhất của hai số nguyên dương bất kỳ. 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.