Thuật toán Euclide tìm USCLN

Thuật toán Ơ-Clit (Euclid) tìm ƯSCLN

I.- Giới thiệu :
Thuật toán Euclid hay Giải thuật Euclid, là một thuật toán giúp ta tính ước số chung lớn nhất (ƯSCLN) của hai số một cách hiệu quả. Thuật toán này đã được biết đến từ khoảng năm 300 trước Công Nguyên. Nhà toán học Hy Lạp cổ Euclid đã viết giải thuật này trong cuốn sách toán nổi tiếng Elements.
II.- Bài mẫu
1./ Đề 1: Tính ước số chung lớn nhất của 91 & 287.
2./ Giải : *Trước hết lấy số lớn hơn trong 2 số đó là 287 chia cho 91:
287 = 91x3 + 14 (91 & 14 sẽ được dùng cho vòng lặp thứ nhất)
Biết rằng:
Bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - = 14.
*Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi + 14 = 287.
Do đó, ƯSCLN(91,287) = ƯSCLN(91,14).
=> Bài toán trở thành tìm ƯSCLN(91,14).
*Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:
91 = 14 x 6 + 7 (14 & 7 sẽ được dùng cho vòng lặp thứ hai)
14 = 7 x 2 (không còn số dư, không cần vòng kế tiếp nữa)
Kết luận: nhận 7 làm kết quả
Đáp số: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).
III.- Nhận xét:
- Chương trình PT ta đã biêt cách tìm ƯSCLN của 2 số A & B là: phân tích A & B ra thừa số nguyên tố (TSNT); Sau đó chọn các TSNT chung cho cả A&B với số mũ nhỏ nhất lấy làm ƯSCLN của 2 số đó . Thí dụ
1./ Đề 2: Tính ước số chung lớn nhất của 284 & 836
2./ Giải : Phân tích 284 & 836 ra TSNT ta có
Pt 284=

2³ x3x11

264
2

132
2

66
3

22
2

11
11

1


 TSNT chung A & B lấy số mũ lớn nhất là 2² x 11 = 44
ĐS: ước số chung lớn nhất của 284 & 836 là 44
-Tuy nhiên, gặp các số A & B lớn và khó phân tích ra TSNT thì nên áp dụng Thuật toán Euclid như giải tại đề 1
IV.- Bài thực hành
1./ Tính ước số chung lớn nhất của 132 & 957 bằng hai cách.
2./ Tính ước số chung lớn nhất của 481 & 949.