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.

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]