Ta xét 2 trường hợp sau:
a) Nếu b là ước của a thì (a, b) = b
b) Nếu b không là ước của a, giả sử a = bp + c thì (a, b) = (b, c). Thuật toán:
a = bp + r1; 0 < r1 < b
b = r1.p1 + r2; 0 < r2 < r1
r1 = r2.p2 + r3; 0 < r3 < r2
r2 = r3.p3 + r4; 0 < r4 < r3
...
rn - 2 = rn - 1.pn - 1 + rn; 0 < rn < rn - 1
rn - 1 = rn.pn + 0
Thuật toán Euclide phải kết thúc bằng một dư là 0
Trong trường hợp b) này ta có, (a, b) = (b, r1) = (r1, r2) = ... = (rn - 1, rn) = rn
Vậy ƯCLN của a và b là rn, là số dư cuối cùng khác 0 trong thuật toán Euclide.
Các bạn vào đây này, đó là một bài mình đã Post lên diễn đàn, bạn Pirates đã vận dụng thuật toán euclide để giải đấy.
Bài viết đã được chỉnh sửa nội dung bởi Đỗ Quang Duy: 07-01-2010 - 21:53
