Tài liệu bồi dưỡng Toán học - Thuật toán Oclit Nguyễn Văn Yên

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 .