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ư r1) thì làm tiếp bước 3
Bước 3: Lấy r chia cho số dư r1
Nếu r r1 thì ƯSCLN (a, b) =r1
Nếu r r1 (dư r2) thì làm tiếp bước 4
Bước 4: Lấy r1 chia cho số dư r2
Nếu r1 r2 thì ƯSCLN (a, b) =r2
Nếu r1 r2 (dư r3) thì làm tiếp tục như trên cho đến khi số dư bằng 0
Số dư cuối cùng khác 0 trong dãy phép chia liên tiếp như trên là ƯSCLN (a, b)











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 + r1 (trong đó r1=15) (2)
r = r1.9 (3)
Vậy r = 15.9 = 135
b = 3.135 +15 = 420
a = 2.420 + 135 = 975
Hai số cần tìm là 975 và 420 .