Tài liệu Thuật toán Euclide tìm ước số chung lớn nhất

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