Bây giờ chúng ta hãy bắt đầu hoạt động của thuật toán Euclid này.

Thuật toán bổ đề chia Euclid

Xét hai số 78 và 980 và chúng ta cần tìm HCF của các số này. Để làm điều này, chúng ta chọn số nguyên lớn nhất trước, tức là 980 và sau đó theo Bổ đề Phân chia Euclid, a = bq + r trong đó 0 ≤ r  <  b ;

980 = 78 × 12 + 44

Bây giờ, ở đây a = 980, b = 78, q = 12 và r = 44.

Bây giờ xét số chia 78 và số dư 44, áp dụng bổ đề phép chia Euclid một lần nữa.

78 = 44 × 1 + 34

Tương tự, xét số chia 44 và số dư 34, áp dụng bổ đề phép chia Euclid cho 44 và 34.

44 = 34 × 1 + 10

Theo quy trình tương tự một lần nữa,

34 = 10 × 3 + 4

10 = 4 × 2 + 2

4 = 2 × 2 + 0

Như chúng ta thấy rằng phần còn lại đã trở thành 0, do đó, không thể tiếp tục tiếp tục. Do đó, HCF là ước số b còn lại trong bước cuối cùng. Chúng ta có thể kết luận rằng HCF của 980 và 78 là 2.

Chúng ta hãy thử một ví dụ khác để tìm HCF của hai số 250 và 75. Ở đây, số nguyên càng lớn 250, do đó, bằng cách áp dụng Bổ đề Phân chia Euclid a = bq + r trong đó 0 ≤ r <b , chúng ta có

a = 250 và b = 75

⇒ 250 = 75 × 3 + 25

Bằng cách áp dụng Thuật toán chia Euclid cho 75 và 25, chúng ta có:

75 = 25 × 3 + 0

Khi phần còn lại trở thành 0, chúng tôi không thể tiếp tục. Theo thuật toán, trong trường hợp này, số chia là 25. Do đó, HCF của 250 và 75 là 25.

Thí dụ

Ví dụ: Tìm HCF của 81 và 675 bằng cách sử dụng thuật toán chia Euclide.

Lời giải: Số nguyên lớn hơn là 675, do đó, bằng cách áp dụng Bổ đề chia a = bq + r trong đó 0 ≤ r <b , chúng ta có

a = 675 và b = 81

⇒ 675 = 81 × 8 + 27

Bằng cách áp dụng lại Thuật toán phân chia Euclid, chúng ta có

81 = 27 × 3 + 0

Chúng tôi không thể tiếp tục vì phần còn lại trở thành 0. Theo thuật toán, trong trường hợp này, số chia là 27. Do đó, HCF của 675 và 81 là 27.

Xem thêm: