Chuyên đề : Thuật toán Ơclit
******************************************************
Chuyên đề :
Thuật toán Ơclit
1. Thuật toán Ơclit
Để tìm USCLN của hai số a và b ta có thể dùng cách chia liên tiếp gọi
là thuật toán Ơclit nh sau:
Bớc 1: Lấy a chia cho b
- Nếu a

b thì ƯSCLN (a, b) =b
- Nếu a

b (d r) thì làm tiếp bớc 2
Bớc 2: Lấy b chia cho số d r
- Nếu b

r thì ƯSCLN (a, b) =r
- Nếu b

r (d r
1
) thì làm tiếp bớc 3
Bớc 3: Lấy r chia cho số d r
1
- Nếu r

r
1
thì ƯSCLN (a, b) =r
1

*************************************************************
Biên soạn: Nguyễn Văn Yên THSC Phong Khê TP Bắc Ninh
Website:
4/2010
Chuyên đề : Thuật toán Ơclit
******************************************************
2. Thí dụ:
Thí dụ 1:
Tìm ƯSCLN (450; 198)
Giải
Bớc 1: Lấy 450 chia cho 198
450 : 198 = 2 (d 54)
Bớc 2: Lấy 198 chia cho số d 54
198 : 54 = 3 (d 36)
Bớc 3: Lấy 54 chia cho số d 36
54 : 36 = 1 (d 18) Số d cuối cùng khác 0
Bớc 4: Lấy 36 chia cho số d 18
36 : 18 = 2 (d 0) Số d cuối cùng bằng 0
ƯSCLN (450; 198) =18 .
Thí dụ 2:
Tìm hai số tự nhiên biết rằng ƯSCLN của nó là 15 và phép chia liên tiếp
của thuật toán Ơclit các thơng lần lợt là 2; 3; 9 .
Giải
Gọi hai số tự nhiên phải tìm là a, b (a>b)
Theo đầu bài ta có 3 phép chia liên tiếp nên số d trong phép chia thứ hai cho
ta ƯSCLN (a, b)
Ta có các phép chia sau:
a = 2b + r (1)
b = 3r + r
1