Giải thuật Euclid

Thuật toán Euclid để tìm ước chung lớn nhất (ƯCLN) của hai đoạn thẳng BA và DC, độ dài của cả hai đều là bội của một "đơn vị" độ dài chung. Vì độ dài của DC ngắn hơn nên nó được dùng để "đo" BA, nhưng chỉ được một lần do phần còn lại là đoạn EA ngắn hơn DC. Bây giờ EA lại được dùng để đo độ dài đoạn DC hai lần. Cuối cùng đoạn FC được dùng để đo độ dài đoạn EA ba lần. Vì không còn đoạn nào dư ra nên quá trình này kết thúc với FC trở thành ƯCLN. Bên phải là ví dụ của Nicomachus với hai số 49 và 21 có kết quả ƯCLN là 7.

Trong toán học, giải thuật Euclid (hay thuật toán Euclid) là một giải thuật để tính ước chung lớn nhất (ƯCLN) của hai số nguyên, là số lớn nhất có thể chia được bởi hai số nguyên đó với số dư bằng không. Giải thuật này được đặt tên theo nhà toán học người Hy Lạp cổ đại Euclid, người đã viết nó trong bộ Cơ sở của ông (khoảng năm 300 TCN). Nó là một ví dụ về thuật toán, một chuỗi các bước tính toán theo điều kiện nhất định và là một trong số những thuật toán lâu đời nhất được sử dụng rộng rãi.

Giải thuật Euclid dựa trên nguyên tắc là ước chung lớn nhất của hai số nguyên không thay đổi khi thay số lớn hơn bằng hiệu của nó với số nhỏ hơn. Chẳng hạn, 21 là ƯCLN của 252 và 105 (vì 252 = 21 × 12 và 105 = 21 × 5) và cũng là ƯCLN của 105 và 252 − 105 = 147. Khi lặp lại quá trình trên thì hai số trong cặp số ngày càng nhỏ đến khi chúng bằng nhau, và khi đó chúng là ƯCLN của hai số ban đầu. Bằng cách đảo ngược lại các bước, ƯCLN này có thể được biểu diễn thành tổng của hai số hạng, mỗi số hạng bằng một trong hai số đã cho nhân với một số nguyên dương hoặc âm (đồng nhất thức Bézout), chẳng hạn, 21 = 5 × 105 + (−2) × 252.

Dạng ban đầu của giải thuật như trên có thể tốn nhiều bước thực hiện phép trừ để tìm ƯCLN nếu một trong hai số lớn hơn rất nhiều so với số còn lại. Một dạng khác của giải thuật rút ngắn lại các bước này, thay vào đó thế số lớn hơn bằng số dư của nó khi chia cho số nhỏ hơn (dừng lại khi số dư bằng không). Dạng thuật toán này chỉ tốn số bước nhiều nhất là năm lần số chữ số của số nhỏ hơn trên hệ thập phân. Gabriel Lamé chứng minh được điều này vào năm 1844, đánh dấu sự ra đời của lý thuyết độ phức tạp tính toán. Nhiều phương pháp khác để tăng hiệu quả của thuật toán cũng đã được phát triển trong thế kỷ 20.

Giải thuật Euclid có rất nhiều ứng dụng trong lý thuyết và thực tế. Nó được dùng để rút gọn phân số về dạng tối giản và thực hiện phép chia trong số học module. Thuật toán cũng là một thành phần then chốt trong giao thức mật mã để bảo mật kết nối Internet và được dùng để phá vỡ hệ thống mật mã này qua phân tích số nguyên. Nó cũng được áp dụng để giải phương trình Diophantine, chẳng hạn như tìm một số thỏa mãn nhiều biểu thức đồng dư theo định lý số dư Trung Quốc, để xây dựng liên phân số hay tìm xấp xỉ gần đúng nhất cho số thực. Cuối cùng, nó là công cụ cơ bản để chứng minh nhiều định lý trong lý thuyết số như định lý bốn số chính phương của Lagrange và tính duy nhất của phân tích số nguyên ra thừa số nguyên tố. Thuật toán Euclid ban đầu chỉ được giới hạn về số tự nhiên và độ dài hình học (số thực), nhưng đến thế kỷ 19 đã được mở rộng cho nhiều dạng số khác như số nguyên Gauss và đa thức một biến, dẫn đến các khái niệm về đại số trừu tượng như miền Euclid.

Ý tưởng

Bài chi tiết: Ước số chung lớn nhất

Giải thuật Euclid dùng để tính ước chung lớn nhất (ƯCLN) của hai số tự nhiên a và b. Ước chung lớn nhất g là số lớn nhất chia được bởi cả a và b mà không để lại số dư và được ký hiệu là ƯCLN(a, b) hoặc (a, b).

Nếu ƯCLN(a, b) = 1 thì a và b được gọi là hai số nguyên tố cùng nhau. Tính chất này không khẳng định a và b là số nguyên tố. Chẳng hạn, 6 và 35 đều không phải là số nguyên tố vì chúng đều có thể được phân tích thành tích của các thừa số nguyên tố: 6 = 2 × 3 và 35 = 5 × 7. Tuy nhiên, 6 và 35 nguyên tố cùng nhau vì chúng không có một thừa số chung nào.

Một hình chữ nhật kích thước 24 × 60 được chia thành 10 hình vuông nhỏ cạnh 12, trong đó 12 là ƯCLN của 24 và 60. Tổng quát hơn, một hình chữ nhật kích thước a × b có thể được chia thành các hình vuông cạnh c khi và chỉ khi c là ước chung của a và b.

Gọi g = ƯCLN(a, b). Vì a và b đều là bội của g nên chúng có thể được viết thành a = mg và b = ng, và không tồn tại số G > g nào để các biểu thức trên đúng. Hai số tự nhiên m và n phải nguyên tố cùng nhau vì không thể phân tích bất kỳ thừa số chung nào lớn hơn 1 từ m và n để g lớn hơn. Do đó, một số c bất kỳ được chia bởi a và b cũng được chia bởi g. Ước chung lớn nhất g của a và b là ước chung (dương) duy nhất của chúng có thể chia được bởi một ước chung c bất kỳ.

ƯCLN có thể được minh họa như sau. Xét một hình chữ nhật có kích thước là a × b và một ước chung c bất kỳ có thể chia được hết cả a và b. Cả hai cạnh của hình chữ nhật có thể được chia thành các đoạn thẳng bằng nhau có độ dài là c để chia hình chữ nhật thành các hình vuông có cạnh bằng c. Ước chung lớn nhất g chính là giá trị lớn nhất của c để điều này có thể xảy ra. Chẳng hạn, một hình chữ nhật có kích thước 24 × 60 có thể được chia thành các hình vuông có cạnh là 1, 2, 3, 4, 6 hoặc 12, nên 12 là ước chung lớn nhất của 24 và 60, tức là hình chữ nhật trên có hai hình vuông nằm trên một cạnh (24/12 = 2) và năm hình vuông nằm trên cạnh còn lại (60/12 = 5).

Ước chung lớn nhất của hai số a và b là tích của các thừa số nguyên tố chung của hai số đã cho, trong đó một thừa số có thể được nhân lên nhiều lần, chỉ khi tích của các thừa số đó chia được cả a và b. Chẳng hạn, ta phân tích được 1386 = 2 × 3 × 3 × 7 × 11 và 3213 = 3 × 3 × 3 × 7 × 17 nên ước chung lớn nhất 1386 và 3213 bằng 63 = 3 × 3 × 7 (là tích của các thừa số nguyên tố chung). Nếu hai số không có một thừa số nguyên tố chung nào thì ước chung lớn nhất của chúng bằng 1 (một trường hợp của tích rỗng), hay nói cách khác chúng nguyên tố cùng nhau. Một ưu điểm quan trọng của giải thuật Euclid là nó có thể tính được ƯCLN đó mà không cần phân tích ra thừa số nguyên tố. Bài toán phân tích các số nguyên lớn là rất khó và tính bảo mật của nhiều giao thức mật mã phổ biến được dựa trên tính chất này.

Một định nghĩa khác của ƯCLN rất hữu ích trong toán cao cấp, đặc biệt là lý thuyết vành. Ước chung lớn nhất g của hai số a và b khác không là tổ hợp tuyến tính tích phân nhỏ nhất, tức là số nhỏ nhất với dạng ua + vb với u và v là số nguyên. Tập hợp tất cả các tổ hợp tuyến tính tích phân của a và b thực chất giống với tập hợp tất cả các bội của g (mg với m là số nguyên). Trong ngôn ngữ toán học hiện đại, ideal tạo bởi a và b chính là ideal tạo bởi g (một ideal tạo bởi một phần tử duy nhất được gọi là ideal chủ yếu và tất cả ideal của số nguyên đều là ideal chủ yếu). Từ đó, một số tính chất của ƯCLN có thể được nhận ra dễ dàng hơn, ví dụ như bất kỳ ước chung nào của a và b cũng chia được bởi ƯCLN (cả hai số hạng trong ua + vb). Tính thống nhất của định nghĩa này với các định nghĩa khác được mô tả dưới đây.

ƯCLN của ba số trở lên bằng tích của các thừa số nguyên tố chung của cả ba số đã cho, nhưng nó cũng có thể được tính bằng cách tìm ƯCLN của từng cặp số trong ba số đó. Chẳng hạn,

ƯCLN(a, b, c) = ƯCLN(a, ƯCLN(b, c)) = ƯCLN(ƯCLN(a, b), c) = ƯCLN(ƯCLN(a, c), b).

Vì vậy, giải thuật Euclid, vốn dùng để tính ƯCLN của hai số nguyên cũng có thể được áp dụng để tính ƯCLN của một số lượng số nguyên bất kỳ.

Mô tả

Thuật toán

Giải thuật Euclid gồm một dãy các bước mà trong đó, đầu ra của mỗi bước là đầu vào của bước kế tiếp. Gọi k là số nguyên dùng để đếm số bước của thuật toán, bắt đầu từ số không (khi đó bước đầu tiên tương ứng với k = 0, bước tiếp theo là k = 1,...)

Mỗi bước bắt đầu với hai số dư không âm r_k−1 và r_k−2. Vì thuật toán giúp đảm bảo số dư luôn giảm dần theo từng bước nên r_k−1 nhỏ hơn r_k−2. Mục tiêu của bước thứ k là tìm thương q_k và số dư r_k thỏa mãn phương trình

$r_{k-2}=q_{k}r_{k-1}+r_{k}$

và 0 ≤ r_k < r_k−1. Nói cách khác, từ số lớn hơn r_k−2, trừ đi bội của số nhỏ hơn r_k−1 đến khi phần dư r_k nhỏ hơn r_k−1.

Ở bước đầu tiên (k = 0), số dư r₋₂ và r₋₁ bằng a và b, hai số cần tìm ƯCLN. Đến bước kế tiếp (k = 1), hai số dư lần lượt bằng b và số dư r₀ ở bước đầu tiên,... Do đó, thuật toán có thể được viết thành một dãy các phương trình

${\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\r_{0}&=q_{2}r_{1}+r_{2}\\r_{1}&=q_{3}r_{2}+r_{3}\\&\,\,\,\vdots \end{aligned}}$

Nếu a nhỏ hơn b thì thuật toán đảo ngược vị trí của hai số. Chẳng hạn, nếu a < b thì thương q₀ bằng không và số dư r₀ bằng a. Do đó, r_k luôn nhỏ hơn r_k−1 với mọi k ≥ 0.

Vì các số dư luôn giảm dần theo từng bước nhưng không thể là số âm nên số dư sau cùng r_N phải bằng không và thuật toán dừng lại tại đó. Số dư khác không cuối cùng r_N−1 chính là ước chung lớn nhất của a và b. Số N không thể là vô hạn vì chỉ có một số lượng hữu hạn các số nguyên dương nằm giữa số dư ban đầu r₀ và số không.

Chứng minh tính đúng đắn

Tính đúng đắn của giải thuật Euclid có thể được chứng minh qua hai bước lập luận. Bước thứ nhất, cần chứng minh số dư khác không cuối cùng r_N−1 chia được cả a và b. Vì r_N−1 là một ước chung nên nó phải nhỏ hơn hoặc bằng với ước chung lớn nhất g. Bước thứ hai, cần chứng minh rằng bất kỳ ước chung nào của a và b, trong đó có g cần phải chia được r_N−1; từ đó, g phải nhỏ hơn hoặc bằng r_N−1. Hai kết luận trên là mâu thuẫn trừ khi r_N−1 = g.

Để chứng tỏ r_N−1 chia được cả a và b, cần biết r_N−1 chia được số dư liền trước r_N−2:

r_N−2 = q_N r_N−1

vì số dư cuối cùng r_N bằng không. r_N−1 cũng chia được số dư r_N−3:

r_N−3 = q_N−1 r_N−2 + r_N−1

vì nó chia được cả hai số hạng trong vế phải của phương trình. Chứng minh tương tự, r_N−1 cũng chia được tất cả số dư liền trước nó kể cả a và b. Không có số dư liền trước r_N−2, r_N−3,... chia bởi a và b cho số dư bằng không. Vì r_N−1 là ước chung của a và b nên r_N−1 ≤ g.

Trong bước thứ hai, một số tự nhiên c bất kỳ chia được cả a và b (là ước chung của a và b) cũng chia được số dư r_k. Theo định nghĩa thì a và b có thể được viết thành bội của c: a = mc và b = nc với m và n là các số tự nhiên. Ta có r₀ = a − q₀b = mc − q₀nc = (m − q₀n)c nên c là một ước của số dư ban đầu r₀. Chứng minh như bước thứ nhất, ta thấy c cũng là ước của các số dư liền sau r₁, r₂,... Từ đó, ước chung lớn nhất g là ước của r_N−1 hay g ≤ r_N−1. Kết hợp hai kết luận thu được, ta có g = r_N−1. Vậy g là ước chung lớn nhất của tất cả cặp số liền sau:

g = ƯCLN(a, b) = ƯCLN(b, r₀) = ƯCLN(r₀, r₁) = … = ƯCLN(r_N−2, r_N−1) = r_N−1.

Ví dụ

Hình ảnh động minh họa giải thuật Euclid qua phép trừ. Hình chữ nhật ban đầu có hai cạnh a = 1071 và b = 462. Đặt vào đó các hình vuông kích thước 462 × 462 thì còn lại hình chữ nhật 462 × 147. Tiếp tục đặt vào hình chữ nhật đó các hình vuông 147 × 147 đến khi còn lại hình chữ nhật 21 × 147. Cuối cùng, đặt vào phần hình còn lại đó các hình vuông 21 × 21 thì không còn chỗ trống nào. Cạnh của hình vuông nhỏ nhất, 21, chính là ƯCLN của 1071 và 462.

Áp dụng giải thuật Euclid để tính ƯCLN của a = 1071 và b = 462. Đầu tiên, ta trừ bội của 462 từ 1071 thì được thương q₀ = 2 và số dư là 147:

1071 = 2 × 462 + 147.

Tiếp tục trừ bội của 147 từ 462 thì được thương q₁ = 3 và số dư là 21:

462 = 3 × 147 + 21.

Tiếp tục trừ bội của 21 từ 147 thì được thương q₂ = 7 và số dư là 0:

147 = 7 × 21 + 0.

Vì số dư cuối cùng bằng 0 nên thuật toán kết thúc với 21 là ƯCLN của 1071 và 462, bằng với ƯCLN có được từ phép phân tích ra thừa số nguyên tố như trên. Các bước được tóm tắt thành bảng sau:

Bước k	Phương trình	Thương và số dư
0	1071 = q0 462 + r0	q0 = 2 và r0 = 147
1	462 = q1 147 + r1	q1 = 3 và r1 = 21
2	147 = q2 21 + r2	q2 = 7 và r2 = 0; kết thúc

Minh họa

Giải thuật Euclid có thể được minh họa dựa vào bài toán hình chữ nhật tương tự như trên. Giả sử ta cần dùng hình vuông để lấp đầy một hình chữ nhật có kích thước là a × b với a là số lớn hơn. Đầu tiên, ta đặt các hình vuông b × b lên trên đó thì còn lại phần hình trống là một hình chữ nhật b × r₀ với r₀ < b. Tiếp theo, ta đặt các hình vuông r₀ × r₀ lên phần hình trống đó thì còn lại phần hình trống thứ hai r₁ × r₀ mà ta cần phải đặt lên đó các hình vuông r₁ × r₁,... Toàn bộ quá trình chỉ kết thúc khi không còn phần hình trống nào, và khi đó, độ dài cạnh hình vuông nhỏ nhất chính là ƯCLN của độ dài hai cạnh hình chữ nhật ban đầu. Chẳng hạn, hình vuông nhỏ nhất trong hình bên là 21 × 21 (màu đỏ), và 21 là ƯCLN của 1071 và 462, độ dài hai cạnh của hình chữ nhật ban đầu (màu xanh lá).

Phép chia có dư

Bài chi tiết: Phép chia có dư

Tại mỗi bước k, giải thuật Euclid tính một thương q_k và số dư r_k từ hai số r_k−1 và r_k−2:

r_k−2 = q_k r_k−1 + r_k

trong đó r_k không âm và nhỏ hơn giá trị tuyệt đối của r_k−1. Định lý làm nền tảng cho phép chia có dư cho thấy luôn tồn tại duy nhất một thương và số dư như vậy.

Trong dạng ban đầu của giải thuật, thương và số dư được tìm bằng cách lặp lại phép trừ, nghĩa là trừ r_k−1 từ r_k−2 và lặp lại đến khi phần dư r_k nhỏ hơn r_k−1, sau đó hoán đổi chúng cho nhau rồi lại lặp lại quá trình này. Phép chia có dư hiệu quả hơn nhiều khi giảm đi số bước giữa hai hoán đổi còn một bước duy nhất. Hơn nữa, ta còn có thể thay phép chia có dư bằng phép toán modulo, vốn chỉ cho kết quả số dư. Như vậy, dạng lặp của giải thuật Euclid trở thành

r_k = r_k−2 mod r_k−1.

Chương trình

Giải thuật Euclid có thể được biểu diễn bằng mã giả. Chẳng hạn, dạng phép chia của nó có thể được lập trình thành

function gcd(a, b)
    while b ≠ 0
        t:= b
        b:= a mod b
        a:= t
    return a

Ở đầu vòng lặp k, biến b mang giá trị số dư r_k−1, trong khi biến a mang giá trị số dư liền trước r_k−2. Bước b := a mod b giống với công thức đệ quy như trên r_k ≡ r_k−2 mod r_k−1. Biến tạm thời t mang giá trị r_k−1 khi tính số dư liền sau r_k. Cuối vòng lặp, biến b mang giá trị r_k, trong khi biến a mang giá trị số dư liền trước r_k−1.

Trong dạng phép trừ (dạng ban đầu của thuật toán), bước b := a mod b được thay bằng phép trừ lặp lại. Trái ngược với dạng phép chia cho phép đầu vào là một số nguyên bất kỳ, dạng phép trừ chỉ cho phép đầu vào là một số nguyên dương và dừng lại khi a = b:

function gcd(a, b)
    while a ≠ b 
        if a > b
            a:= a − b
        else
            b:= b − a
    return a

Biến a và b luân phiên mang giá trị của các số dư liền trước r_k−1 và r_k−2. Giả sử a > b ở đầu một vòng lặp thì a bằng r_k−2 vì r_k−2 > r_k−1. Trong vòng lặp, a được trừ đi bởi bội của số dư liền trước b đến khi a nhỏ hơn b, khi đó a trở thành số dư liền sau r_k. Sau đó, b được trừ đi bởi bội của a đến khi nó nhỏ hơn a và phần còn lại trở thành số dư r_k+1,...

Dạng đệ quy dựa trên tính chất ƯCLN của các cặp số dư liên tiếp là bằng nhau và điều kiện dừng lại là ƯCLN(r_N−1, 0) = r_N−1.

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

Sử dụng dạng này, ƯCLN(1071, 462) được tính từ ƯCLN(462, 1071 mod 462) = ƯCLN(462, 147). ƯCLN sau cùng được tính từ ƯCLN(147, 462 mod 147) = ƯCLN(147, 21), vốn được tính từ ƯCLN(21, 147 mod 21) = ƯCLN(21, 0) = 21.

Phương pháp số dư tuyệt đối nhỏ nhất

Trong một dạng khác của giải thuật Euclid, thương thu được qua mỗi bước được tăng thêm 1 đơn vị nếu giá trị tuyệt đối của phần dư âm nhỏ hơn so với giá trị tuyệt đối của phần dư dương. Điều kiện của phương trình

r_k−2 = q_k r_k−1 + r_k

là |r_k−1| > r_k > 0. Tuy nhiên, có thể tính số dư âm e_k bởi

r_k−2 = (q_k + 1) r_k−1 + e_k

nếu r_k−1 > 0 hoặc

r_k−2 = (q_k − 1) r_k−1 + e_k

nếu r_k−1 < 0.

Nếu thay r_k bằng e_k với |e_k| < |r_k| thì ta có một dạng khác của giải thuật Euclid sao cho trong mỗi bước,

|r_k| ≤ |r_k−1| / 2.

Leopold Kronecker chứng minh được rằng dạng này tốn số bước ít nhất trong tất cả các dạng của giải thuật Euclid. Tổng quát hơn, người ta chứng minh được rằng với mọi số đầu vào a và b, số bước tính ƯCLN là nhỏ nhất khi và chỉ khi q_k được chọn sao cho $\left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0,618$ với $\varphi$ là tỷ lệ vàng.

Lịch sử phát triển

Giải thuật Euclid có thể đã xuất hiện từ trước thời của Euclid, người đang cầm com-pa trong một tranh vẽ khoảng năm 1474.

Giải thuật Euclid là một trong những thuật toán lâu đời nhất được sử dụng rộng rãi. Nó xuất hiện trong bộ Cơ sở của Euclid (khoảng 300 TCN), đặc biệt là ở cuốn 7 (mệnh đề 1–2) và cuốn 10 (mệnh đề 2–3). Trong cuốn 7, thuật toán được phát biểu cho số nguyên, còn trong cuốn 10, nó được phát biểu cho độ dài của đoạn thẳng. (Ngày nay, ta có thể nói thuật toán được phát biểu cho số thực. Nhưng độ dài, diện tích và thể tích, vốn được đo bằng số thực trong thời kỳ hiện đại, lại không có cùng đơn vị đo và cũng không có đơn vị đo tự nhiên nào cho chúng; người xưa lúc bấy giờ vẫn chưa hiểu rõ khái niệm số thực.) Thuật toán trong cuốn 10 mang tính hình học: ƯCLN của hai độ dài a và b là độ dài lớn nhất g có thể làm đơn vị đo chung cho a và b; nói cách khác, độ dài a và b là bội số của độ dài g.

Có lẽ giải thuật trên không phải do Euclid trực tiếp tìm ra (ông là người đã sưu tầm các công trình của các nhà toán học khác và tổng hợp lại trong bộ Cơ sở). Nhà toán học và sử học B. L. van der Waerden cho rằng cuốn 7 xuất phát từ một cuốn sách giáo khoa về lý thuyết số được viết bởi các nhà toán học trong trường của Pythagoras. Giải thuật có thể đã được biết bởi Eudoxus của Cnidus (khoảng 375 TCN), hoặc thậm chí có thể đã có từ trước thời của ông, dựa trên thuật ngữ ἀνθυφαίρεσις (anthyphairesis, phép trừ nghịch đảo) trong một số công trình của Euclid và Aristotle.

Nhiều thế kỷ sau, giải thuật Euclid được tìm ra một cách độc lập tại Ấn Độ và Trung Quốc, chủ yếu để giải phương trình Diophantine vốn nảy sinh trong thiên văn học và làm lịch chính xác. Vào cuối thế kỷ 5, nhà toán học và thiên văn người Ấn Độ Aryabhata đã gọi giải thuật là một "máy nghiền", có thể là vì tính hiệu quả của nó trong việc giải phương trình Diophantine. Mặc dù một trường hợp đặc biệt của định lý số dư Trung Quốc đã được mô tả trong cuốn Sunzi Suanjing, lời giải tổng quát được Tần Cửu Thiều xuất bản trong cuốn Shushu Jiuzhang (數書九章, Giáo trình Toán học trong 9 chương) năm 1247. Giải thuật Euclid lần đầu tiên được mô tả và truyền bá tại châu Âu trong cuốn Problèmes plaisants et délectables (ấn bản thứ hai) của Bachet năm 1624. Tại châu Âu, nó cũng được sử dụng để giải phương trình Diophantine và lập liên phân số. Giải thuật Euclid mở rộng được cho là do Roger Cotes tìm ra và được Nicholas Saunderson xuất bản như là một cách để tính nhanh liên phân số.

Đến thế kỷ 19, giải thuật Euclid đã dẫn đến sự ra đời và phát triển của các hệ thống số học mới, chẳng hạn như số nguyên Gauss và số nguyên Eisenstein. Năm 1815, Carl Gauss sử dụng giải thuật này để chứng minh tính duy nhất của sự phân tích các số nguyên Gauss, mặc dù công trình của ông chỉ được xuất bản lần đầu năm 1832. Gauss trước đó cũng từng nhắc đến giải thuật trong cuốn Disquisitiones Arithmeticae (xuất bản 1801) liên quan đến liên phân số. Peter Gustav Lejeune Dirichlet có thể là người đầu tiên mô tả giải thuật như là một cơ sở của phần lớn lý thuyết số. Lejeune Dirichlet nhận thấy rằng nhiều hệ quả của lý thuyết số là đúng với bất kỳ hệ thống số học nào mà giải thuật Euclid có thể áp dụng được. Những bài giảng của Dirichlet về lý thuyết số đã được biên tập và mở rộng bởi Richard Dedekind, người đã ứng dụng giải thuật để nghiên cứu số đại số nguyên, một dạng số tổng quát mới. Chẳng hạn, Dedekind là người đầu tiên chứng minh được định lý Fermat về tổng của hai số chính phương qua sự phân tích duy nhất số nguyên Gauss. Ông cũng định nghĩa khái niệm miền Euclid, một hệ thống số mà trong đó một dạng tổng quát của giải thuật Euclid có thể được xác định. Những năm cuối thế kỷ 19, giải thuật Euclid dần bị lu mờ bởi lý thuyết tổng quát của Dedekind về ideal.

"[Giải thuật Euclid] là cha đẻ của thuật toán, vì nó là thuật toán không tầm thường lâu đời nhất vẫn còn trụ lại được đến ngày nay."

Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, ấn bản 2 (1981), tr. 318.

Nhiều ứng dụng khác của giải thuật Euclid cũng đã được phát triển trong thế kỷ 19. Năm 1829, Charles Sturm cho thấy rằng giải thuật này có ích trong phương pháp chuỗi Sturm dùng để đếm số nghiệm thực của đa thức trong một khoảng bất kỳ.

Giải thuật Euclid là thuật toán liên hệ số nguyên đầu tiên dùng để tìm mối liên hệ số nguyên giữa các số thực tương xứng. Nhiều thuật toán khác như vậy cũng đã được phát triển, chẳng hạn như thuật toán của Helaman Ferguson và R.W. Forcade (1979) hay thuật toán LLL.

Năm 1969, Cole và Davie đã tạo ra một trò chơi hai người dựa trên giải thuật Euclid có tên là The Game of Euclid. Trò chơi này có một chiến lược chơi tối ưu. Mỗi người chơi bắt đầu với hai đống đá chứa a và b viên đá, lần lượt loại bỏ m bội của đống nhỏ hơn so với đống lớn hơn. Như vậy, khi a lớn hơn b thì người tiếp theo có thể giảm số lượng viên đá trong đống lớn từ a xuống a − mb viên. Người chiến thắng là người đầu tiên có một đống không còn viên đá nào.

Hiệu suất thuật toán

Số bước trong thuật toán Euclid cho gcd( x, y ). Các điểm sáng hơn (đỏ và vàng) biểu thị tương đối ít bước, trong khi các điểm tối hơn (tím và xanh lam) biểu thị nhiều bước hơn. Vùng tối lớn nhất theo đường thẳng y = Φx, trong đó Φ là tỷ lệ vàng .

r_k−2 = q_k r_k−1 + r_k.

r_k = r_k−2 − q_k r_k−1.

Số bước trong thuật toán Euclid cho gcd( x, y ). Các điểm sáng hơn (đỏ và vàng) biểu thị tương đối ít bước, trong khi các điểm tối hơn (tím và xanh lam) biểu thị nhiều bước hơn. Vùng tối lớn nhất theo đường thẳng y = Φx, trong đó Φ là tỷ lệ vàng .

Hiệu suất tính toán của thuật toán Euclid đã được nghiên cứu kỹ lưỡng. Hiệu suất này có thể được mô tả bằng số bước chia mà thuật toán yêu cầu nhân với chi phí tính toán của mỗi bước. Phân tích đầu tiên về thuật toán Euclid được ghi nhận là của Antoine André Louis Reynaud vào năm 1811. Ông đã chỉ ra rằng số bước chia trên đầu vào (u, v) bị chặn bởi v và sau đó chặt hơn là v/2 + 2. Năm 1841, Pierre Joseph Étienne Finck đã chứng minh số bước chia nhiều nhất là 2 log₂ v + 1, và do đó thuật toán Euclid chạy trong thời gian đa thức theo kích thước của đầu vào. Năm 1837, Émile Léger đã nghiên cứu trường hợp xấu nhất, là khi các đầu vào là những số Fibonacci liên tiếp. Phân tích của Finck được Gabriel Lamé tinh chỉnh vào năm 1844. Ông chỉ ra rằng số bước cần để hoàn thành không bao giờ vượt quá năm lần h, là số chữ số trong hệ thập phân của số nhỏ hơn (b).

Trong mô hình chi phí thống nhất (phù hợp để phân tích độ phức tạp tính toán ƯCLN trên các số phù hợp với một từ máy duy nhất), mỗi bước của thuật toán mất thời gian không đổi và phân tích của Lamé kéo theo tổng thời gian chạy cũng là O(h). Tuy nhiên, trong một mô hình tính toán phù hợp với các số lớn hơn, chi phí tính toán của mỗi phép tính số dư trong thuật toán có thể lên tới O(h²). Trong trường hợp này, tổng thời gian cho tất cả các bước của thuật toán có thể được phân tích bằng một chuỗi lồng nhau, từ đó chỉ ra rằng nó cũng là O(h²). Các kỹ thuật thuật toán hiện đại dựa trên thuật toán Schönhage–Strassen để nhân số nguyên nhanh có thể được sử dụng để tăng tốc quá trình này, dẫn đến các thuật toán tựa tuyến tính cho ƯCLN.

Số bước

Số bước để tính ƯCLN của hai số tự nhiên a và b có thể ký hiệu là T(a, b). Nếu g là ƯCLN của a và b thì a = mg và b = ng với m và n nguyên tố cùng nhau. Khi đó

T(a, b) = T(m, n)

như có thể thấy bằng cách chia tất cả các bước trong thuật toán Euclidean cho g. Lập luận tương tự, số bước vẫn giữ nguyên nếu nhân a và b với cùng hệ số w: T(a, b) = T(wa, wb). Do đó, số bước T có thể thay đổi đáng kể giữa các cặp số lân cận, chẳng hạn như T(a, b) và T(a, b + 1), tùy thuộc vào kích thước của hai ƯCLN.

Bản chất đệ quy của thuật toán Euclid cho ra một phương trình khác

T(a, b) = 1 + T(b, r₀) = 2 + T(r₀, r₁) = … = N + T(r_N−2, r_N−1) = N + 1

trong đó T(x, 0) = 0 theo giả định.

Trường hợp xấu nhất

Nếu thuật toán Euclid yêu cầu N bước cho một cặp số tự nhiên a > b > 0, giá trị nhỏ nhất của a và b để điều này đúng lần lượt là số Fibonacci F_{N +2} và F _{N +1}. Nói cách khác, nếu thuật toán Euclid yêu cầu N bước cho cặp a > b, thì người ta có a ≥ F _{N +2} và b ≥ F _{N +1} . Có thể chứng minh điều này bằng quy nạp như sau. Nếu N = 1, a chia hết cho b; bộ số tự nhiên nhỏ nhất để điều này đúng là b = 1 và a = 2, tức lần lượt là F₂ và F_3. Giả sử kết quả đúng với mọi giá trị của N đến M − 1. Bước đầu tiên của thuật toán M bước là a = q₀b + r ₀ và thuật toán Euclid yêu cầu M − 1 bước cho cặp b > r ₀ . Theo giả thiết quy nạp, ta có b ≥ F_M+1 và r₀ ≥ F_M. Do đó, a = q₀b + r₀ ≥ b + r₀ ≥ F_M+1 + F_M = F_M+2, đây là bất đẳng thức cần có. Chứng minh này, được Gabriel Lamé công bố năm 1844, đại diện cho sự khởi đầu của lý thuyết độ phức tạp tính toán, và cũng là ứng dụng thực tế đầu tiên của các số Fibonacci.

Kết quả này đủ để chứng minh số bước trong thuật toán Euclid không bao giờ vượt quá năm lần số chữ số của nó (cơ số 10). Vì nếu thuật toán yêu cầu N bước, thì b lớn hơn hoặc bằng F _{N +1,} mà số này lớn hơn hoặc bằng φ ^{N −1}, trong đó φ là tỷ lệ vàng. Vì b ≥ φ ^{N −1} nên N − 1 ≤ log _φ b . Vì log ₁₀ φ > 1/5, ( N − 1)/5 < log_10φ log_φ b = log ₁₀ b . Do đó, N ≤ 5 log ₁₀ b . Như vậy, thuật toán Euclid luôn cần ít hơn O(h) phép chia, trong đó h là số chữ số của số nhỏ hơn

(b).

Trung bình

Số bước trung bình thuật toán Euclid thực hiện có ba định nghĩa khác nhau. Định nghĩa đầu tiên là thời gian trung bình T(a) cần để tính ƯCLN của một số a cho trước và một số tự nhiên bé hơn b được chọn ngẫu nhiên từ các số nguyên từ 0 đến a − 1:

$T(a)={\frac {1}{a}}\sum _{0\leq b<a}T(a,b).$

Tuy nhiên, vì T(a, b) dao động mạnh theo ƯCLN của hai số, hàm trung bình T(a) cũng "nhiễu".

Để giảm độ nhiễu này, một giá trị trung bình thứ hai τ(a) được lấy trên tất cả các số nguyên tố cùng nhau với a

$\tau (a)={\frac {1}{\varphi (a)}}\sum _{\begin{smallmatrix}0\leq b<a\\\gcd(a,b)=1\end{smallmatrix}}T(a,b).$

Có φ(a) số nguyên tố cùng nhau với a và nhỏ hơn a, trong đó φ là hàm toàn phần Euler. Trung bình tau này tăng đều theo a:

$\tau (a)={\frac {12}{\pi ^{2}}}\ln 2\ln a+C+O(a^{-1/6-\varepsilon })$

với sai số dư có cấp a^{−(1/6)+ ε}, trong đó ε vô cùng nhỏ . Hằng số C trong công thức này được gọi là hằng số Porter và bằng

$C=-{\frac {1}{2}}+{\frac {6\ln 2}{\pi ^{2}}}\left(4\gamma -{\frac {24}{\pi ^{2}}}\zeta '(2)+3\ln 2-2\right)\approx 1.467$

trong đó γ là hằng số Euler–Mascheroni và ζ′ là đạo hàm của hàm zeta Riemann. Hệ số (12/π²) ln2 được xác định bằng hai phương pháp độc lập.

Vì trung bình đầu tiên có thể được tính từ trung bình tau bằng cách cộng các ước số d của a:

$T(a)={\frac {1}{a}}\sum _{d\mid a}\varphi (d)\tau (d)$,

nó có thể được xấp xỉ bằng công thức

$T(a)\approx C+{\frac {12}{\pi ^{2}}}\ln 2\,{\biggl (}{\ln a}-\sum _{d\mid a}{\frac {\Lambda (d)}{d}}{\biggr )}$

trong đó Λ( d ) là hàm von Mangoldt .

Trung bình thứ ba Y(n) được định nghĩa là số bước trung bình cần thiết khi chọn ngẫu nhiên cả a và b (với phân phối đều) từ 1 đến n:

$Y(n)={\frac {1}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a).$

Thay công thức gần đúng cho T(a) vào phương trình này sẽ thu được ước tính cho Y(n):

$Y(n)\approx {\frac {12}{\pi ^{2}}}\ln 2\ln n+0.06.$

Chi phí tính toán cho mỗi bước

Trong mỗi bước k của thuật toán Euclid, thương số q_k và số dư r_k được tính cho một cặp số nguyên r_k−2 và r_k−1 cho trước:

r_k−2 = q_k r_k−1 + r_k.

Chi phí tính toán cho mỗi bước chủ yếu liên quan đến việc tìm q_k, vì số dư r_k có thể tính nhanh từ r_k−2, r_k−1 và q_k

r_k = r_k−2 − q_k r_k−1.

Chi phí tính toán của việc chia số h bit tỷ lệ với O(h(ℓ + 1)), trong đó ℓ là độ dài của thương số.

Để so sánh, thuật toán gốc dựa trên phép trừ của Euclid có thể chậm hơn nhiều. Một phép chia số nguyên duy nhất tương đương với q phép trừ (q là thương). Nếu tỷ lệ giữa a và b rất lớn thì thương lớn, dẫn đến cần nhiều phép trừ. Mặt khác, người ta đã chỉ ra rằng thương có khả năng cao là số nguyên nhỏ. Xác suất của một thương số q cho trước xấp xỉ bằng ln | u/(u − 1) | trong đó u = (q + 1)². Để minh họa, xác suất để thương là 1, 2, 3, 4 lần lượt xấp xỉ 41,5%, 17,0%, 9,3%, 5,9%. Vì phép trừ nhanh hơn phép chia, đặc biệt là đối với các số lớn, thuật toán Euclid dựa trên phép trừ có hiệu suất ngang ngửa phiên bản dựa trên phép chia. Điều này được khai thác trong phiên bản nhị phân của thuật toán Euclid.

Kết hợp số bước ước tính với chi phí tính toán ước tính mỗi bước cho thấy thuật toán Euclid tăng theo bậc hai (h²) với h là số chữ số trung bình của hai số ban đầu a và b. Gọi h₀, h₁, ..., h_N−1 h₀, h₁, ..., h_N−1 là số chữ số của các số dư liên tiếp r₀, r₁, ..., r_N−1 r₀, r₁, ..., r_N−1. Do số bước N tăng tuyến tính theo h, thời gian chạy bị chặn bởi

$O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).$

Các phương pháp thay thế

Thuật toán Euclid được sử dụng rộng rãi trong thực tế, đặc biệt là đối với các số nhỏ, do tính đơn giản của nó. Để so sánh, có thể xác định hiệu suất của các phương pháp thay thế thuật toán Euclid.

Một cách tiếp cận không hiệu quả để tìm ƯCLN của hai số tự nhiên a và b là tính tất cả các ước chung của chúng; khi đó số lớn nhất là ƯCLN. Có thể tìm ước chung bằng cách chia cả hai số cho các số nguyên liên tiếp từ 2 đến số nhỏ hơn (b). Số bước của cách tiếp cận này tăng tuyến tính theo b hoặc theo cấp số nhân theo số chữ số. Một cách tiếp cận không hiệu quả khác là tìm các ước nguyên tố của một hoặc cả hai số. Như đã lưu ý ở trên, ƯCLN bằng tích các ước nguyên tố chung của hai số a và b. Các phương pháp phân tích thành thừa số nguyên tố hiện tại cũng không hiệu quả; nhiều hệ thống mật mã hiện đại thậm chí còn dựa vào sự kém hiệu quả đó.

Thuật toán ƯCLN nhị phân là một phương pháp hiệu quả, thay thế phép chia bằng các phép toán nhanh hơn qua việc khai thác biểu diễn nhị phân được máy tính sử dụng. Tuy nhiên, phương pháp thay thế này cũng tỷ lệ với O(h²) . Nhìn chung, nó nhanh hơn thuật toán Euclid trên máy tính thực, mặc dù nó tỷ lệ theo cùng một cách. Có thể tăng hiệu suất bằng cách chỉ kiểm tra các chữ số đầu của hai số a và b. Thuật toán nhị phân có thể được mở rộng sang các cơ số khác (thuật toán cơ số k), với tốc độ tăng lên đến gấp năm lần. Thuật toán ƯCLN Lehmer sử dụng cùng một nguyên tắc chung như thuật toán nhị phân để tăng tốc các phép tính ƯCLN trong cơ số tùy ý.

Một cách tiếp cận đệ quy cho các số nguyên rất lớn (với hơn 25.000 chữ số) dẫn đến các thuật toán ƯCLN số nguyên tựa tuyến tính, chẳng hạn như các thuật toán của Schönhage, hay của Stehlé và Zimmermann. Các thuật toán này khai thác dạng ma trận 2×2 của thuật toán Euclid được đưa ra ở trên. Các phương pháp tựa tuyến tính này thường tỷ lệ với O(h log h² log log h).

Xem thêm

• Giải thuật Euclid mở rộng

Tham khảo

• Cohen, H. (1993). A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. ISBN 0-387-55640-0.
• Cohn, H. (1962). Advanced Number Theory. New York: Dover. ISBN 0-486-64023-X.
• Cox, D.; Little, J.; O'Shea, D. (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (ấn bản thứ 2). Springer-Verlag. ISBN 0-387-94680-2.
• Crandall, R.; Pomerance, C. (2001). Prime Numbers: A Computational Perspective (ấn bản thứ 1). New York: Springer-Verlag. ISBN 0-387-94777-9.
• Lejeune Dirichlet, P. G. (1894). Dedekind, Richard (biên tập). Vorlesungen über Zahlentheorie (Lectures on Number Theory) (bằng tiếng Đức). Braunschweig: Vieweg. LCCN 03005859. OCLC 490186017.
• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (ấn bản thứ 3). Addison–Wesley. ISBN 0-201-89684-2.
• LeVeque, W. J. (1996) [1977]. Fundamentals of Number Theory. New York: Dover. ISBN 0-486-68906-9.
• Mollin, R. A. (2008). Fundamental Number Theory with Applications (ấn bản thứ 2). Boca Raton: Chapman & Hall/CRC. ISBN 978-1-4200-6659-3.
• Ore, O. (1948). Number Theory and Its History. New York: McGraw–Hill.
• Rosen, K. H. (2000). Elementary Number Theory and its Applications (ấn bản thứ 4). Reading, MA: Addison–Wesley. ISBN 0-201-87073-8.
• Schroeder, M. (2005). Number Theory in Science and Communication (ấn bản thứ 4). Springer-Verlag. ISBN 0-387-15800-6.
• Stark, H. (1978). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8.
• Stillwell, J. (1997). Numbers and Geometry. New York: Springer-Verlag. ISBN 0-387-98289-2.
• Stillwell, J. (2003). Elements of Number Theory. New York: Springer-Verlag. ISBN 0-387-95587-9.
• Tattersall, J. J. (2005). Elementary Number Theory in Nine Chapters. Cambridge: Cambridge University Press. ISBN 978-0-521-85014-8.

Liên kết ngoài

• Demonstrations of Euclid's algorithm
• Weisstein, Eric W., "Euclidean Algorithm" từ MathWorld.
• Euclid's Algorithm tại cut-the-knot
• Euclid's algorithm tại trang PlanetMath.org.
• The Euclidean Algorithm tại MathPages
• Music and Euclid's algorithm [Âm nhạc và giải thuật Euclid]