Bài 12: Ước chung. Ước chung lớn nhất

THUẬT TOÁN EUCLID

Ngoài cách phân tích ra thừa số nguyên tố, ta có thể dùng cách sau (gọi là thuật toán Euclid) để tìm ước chung lớn nhất của hai số tự nhiên \(a\) và \(b\).

Chẳng hạn, để tìm ƯCLN(450,198) ta làm như sau:

- Chia 450 cho 198 được số dư là 54.

- Lấy số 198 đem chia cho số dư 54 được số dư là 36.

- Chia 54 cho 36 được số dư là 18.

- Tiếp tục lấy 36 chia cho 18 được số dư bằng 0.

Ta có số dư cuối cùng khác 0 là 18 chính là ƯCLN phải tìm.