Một thuật toán nổi tiếng
La Trí Dũng
Thuật toán Euclide
Để đưa ra được thuật toán, trước hết Euclide nhận xét:
Giả sử f và g không đồng thời bằng không là 2 số nguyên không âm và f ge; g. Khi đó:
- Nếu g=0 thì USCLN(f,g)=f.
- Nếu g ≠ 0 thì ta có hệ thức USCLN (f,g)= USCLN( g,r) với r là số dư trong phép chia của
f cho g.
Các bạn có thể hoàn toàn chứng minh được kết luận trên,chỉ cần lưu ý rằng với mọi a, các
số f và g có ước số chung, giống hệt các ướcsố chung của g và f-ag. Trong khi đó, số dư r
cũng có dạng f-ag.
Từ những nhận xét trên, Euclide đã đưa ra thuật toán sauđể tìm USCLN của hai số nguyên
không âm:
Cho 2 số nguyên không âm, để tìm USCLN của chúng ta thực hiện các bước sau:
Bước 1: So sánh số thứ hai với 0.
Nếu số thứ hai bằng 0 thì dừng lại, kết luận USCLN chính là số thứ nhất.
Nếu số thứ hai khác 0 thì tính số dư trong phép chia số thứ nhất cho số thứ hai.
Chuyển sang bước 2.
Bước 2: Thay số thứ nhất bằng số thứ hai, số thứ hai bằng số dư vừa tính được, rồi quay lại
bước 1.
Các bạn lưu ý: Số dư luôn bé hơn số chia, và một dãy giảm các số nguyên không âm không
thể vô hạn. Do đó, thuật toán Euclide chắc chắn sẽ dừng tại một bước nào đó, khi số dư
bằng 0.
Ví dụ: Tìm USCLN(39,15).
áp dụng thuật toán này, ta được các cặp số có thứ tự:
(39,15), (15,9), (9,6), (6,3), (3,0).
Như vậy cuối cùng ta thu được USCLN(39,15)=3.
Tính ưu việt của thuật toán Euclide
Trong thực tiễn tính toán, đa phần các thuật toán cổ dần bị thay thế bởi cácthuật toán mới.
Thuật toán Euclide thoát khỏi số phận đó trước hết là nhờ tínhtiết kiệm của nó. Giá trị
USCLN(f,g) có thể tính được theo nhiều cách khácnhau, ví dụ có thể tính theo thuật toán tự

fugv=USCLN(f,g) (2)
Nó cũng chính là cách giải phương trình kx+ly=m, với k, l, m là các số nguyên sao cho k, l
không đồng thời bằng 0, còn m chia hết cho USCLN( |k|, |l| ). Giả sử|k|u| + |l|v = d, khi đó |
k|um/d + |l|vm/d = m, suy ra k (c1 um/d)+ l(c2 vm/d)=mvới cj = 1, j=1, 2.
Thuật toán tìm u, v thoả mãn (2) như sau: Kí hiệu f0 = f, f1 = g và xét (1). Giả sử với số
i ≥ n-2 nào đó, ta đã biết fi, fi+1 và các thừa số p, q, s, t tương ứng sao cho
f0 p + f1 q = fi,f0s + f1t = fi+1 (4)
Khi đó chia fi cho fi+1 ta nhận được thương số ai+1 và số dư fi+2, ta có thể tính được thừa
số ứng với fi+2:vì fi-ai+1fi+1 = fi+2 nên sử dụng hệ thức (4) cho fi, fi+1 ta thu được
f0 (p-ai+1 s) + f1 (q-a i+1 t) = fi+2.
Như vậy, để giải bài toán (2), ta áp dụng thuật toánEuclide cho 2 số f và g, đồng thời ở mỗi
bước ngoài 2 giá trị như trước, taphải xem xét các thừa số p, q và s, t tương ứng với chúng.
ở bước đầu tiên, các thừa số tương ứng với f, g ta sẽlấy là 1, 0 và 0, 1. Sau khi thực hiện
phép chia và nhận được thương số a cùngsố dư, ta phải xét số dư: nếu số dư khác 0, trước
khi chuyển sang bước sau, taphải tính các thừa số tương ứng với số dư nhận được theo
công thức p-as vàq-at. số dư khác 0 cuối cùng và các thừa số u và v tương ứng với nó sẽ
thoả mãn(2).
Trongquá trình áp dụng thuật toán trên với f=39 và g=15 ta thu được dãy các số dưlần lượt
là 9, 6, 3, 0 và các thừa số tương ứng với 3 số dư đầu là 1, -2; -1,3; 2, -5. Như vậy,
39.2+15.(-5)=3=USCLN(39, 15).
Bâygiờ ta nhận thấy rằng, thuật toán có thể biến đổi sao cho số các thao tác mà nóyêu cầu
giảm đi gần một lần rưỡi: từ 2 số u và v ta chỉ cần tính v, sau đó xácđịnh u theo công thức
u=(USCLN(f,g)-gv)/f. Với f=39, g=15 ta có thể đặtu=(3-15.(-5))/39=2.
Dãy các phép chia có dư theo sơ đồ (1) cũng là cơ sở của của thuật toán liênphân số, cho
phép thu được một xấp xỉ rất thú vị của phân số f0/f1.Liên phân số (hữu hạn) là biểu thức
dạng
(5)
trongđó b1, b2,..., bk là các số tự nhiên.
Liên phân số (5) thường kí hiệu ngắn gọn là [b1, b2,..., bk].Vì f0 = a1 f1 + f2, nên ta có
Tiếptheo, cũng bằng cách như vậy, ta sẽ biến đổi f2,... Cuối cùng tathu được f1/f0 =[a1,

tìm một nghiệm.
Bài tập 6. Một năm thiên văn trên tráiđất dài 365,242199 ngày đêm. Hãy tìm các phân số
thích hợp của số242199/1000000. Phân số nào trong chúng được dùng làm chuẩn để tính
năm nhuận trong dương lịch hiện tại
Bài tập 7. Hãy lập chương trình bằng mộtngôn ngữ bậc cao thể hiện các thuật toán:
a. Thuật toán tự nhiên tính USCLN(f,g).
b. Thuật toán Euclide tính USCLN(f,g).
c. Thuật toán giải phương trình kx+ly=m.
d. Thuật toán biểu diễn f/g thành liên phân số.