Một thuật toán nổi tiếng (Euclide)

Một thuật toán nổi tiếng Euclide
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 >= 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 ước số 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ác thuật toán mới. Thuật toán Euclide thoát khỏi số phận đó trước hết là nhờ tính tiết kiệm của nó. Giá trị USCLN(f,g) có thể tính được theo nhiều cách khác nhau, ví dụ có thể tính theo thuật toán tự nhiên như sau: Nếu g=0 thì lấy USCLN(f,g)=f, nếu không thì chọn trong dãy số g, g-1, g-2,..., 1 số đầu tiên mà phép chia của f và g cho số đó cùng cho số dư là 0. Nhưng cũng như các thuật toán khác, thuật toán này quá lãng phí. Chẳng hạn trong trường hợp f và g nguyên tố cùng nhau, nó yêu cầu tới 2g phép chia.
Bây giờ ta sẽ đi nghiên cứu số phép chia mà thuật toán Euclide yêu cầu và chỉ ra rằng với g đủ lớn thì nó nhỏ hơn hẳn 2g. Ta sẽ xét dãy các số dư thu được trong quá trình thực hiện thuật toán Euclide. Để thuận tiện, ta kí hiệu f0=f, f1=g (và giả sử f0>f1). Các số dư thu được sẽ kí hiệu lần lượt là f2, f3,..., fn, còn thương số của các phép chia f0 cho f1, f1 cho f2,..., fn-1 cho fn sẽ kí hiệu là a1, a2,..., an:
f0=a1f1+f2,
f1=a2f2+f3,
...                                             (1)
fn-2=an-1fn-1+fn,
fn-1=anfn,
trong đó, USCLN(f,g)= fn. Số dư luôn bé hơn số chia nên f0>f1>f2>... >fn>0. Từ đó suy ra các thương số a1, a2,..., an luôn lớn hơn hoặc bằng 1.
Bổ đề 1. Với i=1, 2,..., n-2 ta luôn có fi>2fi+2.
Chứng minh. fi=ai+1fi+1+fi+2 >= fi+1+fi+2 > 2fi+2.
Bổ đề 2. Giả sử k là một số tự nhiên sao cho thuật toán Euclide áp dụng cho 2 số f0, f1 không dừng sau 2k phép chia (tức là f2k+1 >= 1). Khi đó f1 > 2k.
Chứng minh. Áp dụng bổ đề 1, ta thu được f1>2f3>4f5>... > 2kf2k+1 >= 2k.
Định lí. Số phép chia mà thuật toán Euclide yêu cầu không vượt quá 2[log2 f1]+2.
( [x] là kí hiệu phần nguyên của x).
Chứng minh. Từ bổ đề 2 ta suy ra nếu k là số tự nhiên sao cho f1 <= 2k thì số phép chia mà thuật toán Euclide yêu cầu không vượt quá 2k. Nên