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.

á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.

     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 f₀=f, f₁=g (và giả sử f₀>f₁). Các số dư thu được sẽ kí hiệu lần lượt là f₂, f₃,..., f_n, còn thương số của các phép chia f₀ cho f₁, f₁ cho f₂,..., f_n-1 cho f_n sẽ kí hiệu là a₁, a₂,..., a_n:

f₀=a₁f₁+f₂,

f₁=a₂f₂+f₃,

...                                             (1)

f_n-2=a_n-1f_n-1+f_n,

f_n-1=a_nf_n,

trong đó, USCLN(f,g)= f_n. Số dư luôn bé hơn số chia nên f₀>f₁>f₂>... >f_n>0. Từ đó suy ra các thương số a₁, a₂,..., a_n luôn lớn hơn hoặc bằng 1.

Bổ đề 1. Với i=1, 2,..., n-2 ta luôn có f_i>2f_i+2.

Chứng minh. f_i=a_i+1f_i+1+f_i+2 >= f_i+1+f_i+2 > 2f_i+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ố f₀, f₁ không dừng sau 2k phép chia (tức là f_2k+1 >= 1). Khi đó f₁ > 2^k.

Chứng minh. Áp dụng bổ đề 1, ta thu được f₁>2f₃>4f₅>... > 2^kf_2k+1 >= 2^k.

Định lí. Số phép chia mà thuật toán Euclide yêu cầu không vượt quá 2[log₂ f₁]+2.

( [x] là kí hiệu phần nguyên của x).

Chỉ nguyên việc so sánh đồ thị của 2 hàm số y=2x và y=2log₂ x +2 đã đủ để không nghi ngờ về ưu thế của thuật toán Euclide so với thuật toán tự nhiên.

Một ưu thế nữa của thuật toán Euclide là nó có nhiều cách mở rộng và tổng quát. Một thuật toán thường gặp là thuật toán tính các số nguyên u, v sao cho

fu + gv=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(c₁um/d)+l(c₂vm/d)=m với c_j= 1, j=1, 2.

Thuật toán tìm u, v thoả mãn (2) như sau: Kí hiệu f₀=f, f₁=g và xét (1). Giả sử với số

i>= n-2 nào đó, ta đã biết f_i, f_i+1 và các thừa số p, q, s, t tương ứng sao cho

                                    f₀p+f₁q=f_i, f₀s+f₁t=f_i+1                          (4)

Khi đó chia f_i cho f_i+1 ta nhận được thương số a_i+1 và số dư f_i+2, ta có thể tính được thừa số ứng với f_i+2: vì f_i-a_i+1f_i+1=f_i+2 nên sử dụng hệ thức (4) cho f_i, f_i+1 ta thu được

f₀(p-a_i+1s)+f₁(q-a_i+1t)=f_i+2.

Như vậy, để giải bài toán (2), ta áp dụng thuật toán Euclide cho 2 số f và g, đồng thời ở mỗi bước ngoài 2 giá trị như trước, ta phả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ùng số dư, ta phải xét số dư: nếu số dư khác 0, trước khi chuyển sang bước sau, ta phả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).

Trong quá 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ây giờ 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ể đặt u=(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ên phân số, cho phép thu được một xấp xỉ rất thú vị của phân số f₀/f₁. Liên phân số (hữu hạn) là biểu thức dạng:

 (5) trong đó b₁, b₂,..., b_k là các số tự nhiên.

Liên phân số (5) thường kí hiệu ngắn gọn là [b₁, b₂,..., b_k]. Vì f₀=a₁f₁+f₂, nên ta có:   

Tiếp theo, cũng bằng cách như vậy, ta sẽ biến đổi f₂,... Cuối cùng ta thu được f₁/f₀= [a₁, a₂,..., a_n]. Xét thêm các liên phân số [a₁], [a₁, a₂],..., [a₁, a₂,..., a_n-1], giá trị của chúng được gọi là các phân số thích hợp của f₁/f₂. Kí hiệu dạng tối giản của các phân số thích hợp bằng p₁/q₁, p₂/q₂,..., p_n-1/q_n-1. Các tính chất sau đây của các xấp xỉ của f₀/f₁ được liệt kê mà không chứng minh: 

    b) Nếu với mỗi phân số u/v và phân số thích hợp p_i/q_i, 1 <= i <= n-1 ta có 

     thì v>q_i.

Không khó khăn lắm ta có thể xác định các phân số thích hợp của 15/39 (mà dạng tối giản của nó là 5/13) là 1/2, 1/3, 2/5. Hiệu của phân số ban đầu với với các phân số đó tương ứng là -3/26, 2/39 và -1/65.

Các tính chất a. và b. được sử dụng trong nhiều bài tập ứng dụng khác nhau có đòi hỏi lựa chọn một xấp xỉ cho một số thực dưới dạng một phân số với mẫu số không lớn lắm. Một ví dụ là việc tính toán hệ truyền động răng cưa gồm 2 bánh răng: Hệ số truyền phải gần với một số cho trước, trong khi số răng của mỗi bánh răng lại không được vượt quá một giới hạn cho trước.

    Thuật toán Euclide còn có nhiều cách tổng quát, mở rộng khác, chẳng hạn: xấp xỉ các số vô tỉ, tìm USCLN của các đa thức, v.v... Do đó trong thực tiễn tính toán hiện nay, thuật toán đã 2300 năm tuổi này vẫn tìm được chỗ đứng.

    Phần  kết của bài viết, đề nghị các bạn làm một số bài tập: 

m>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.