Thuật toán Euclid

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

Thuật toán Euclid dựa trên nguyên lý rằng ƯCLN 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. Ví dụ, 21 là ƯCLN của 252 và 105 (vì 252 = 21 × 12 và 105 = 21 × 5) cũng là ƯCLN của 105 và 252 − 105 = 147. Khi tiếp tục quá trình, hai số trong cặp ngày càng nhỏ cho đến khi chúng bằng nhau, lúc đó chúng chính là ƯCLN của hai số ban đầu. Theo cách ngược lại, ƯCLN có thể biểu diễn dưới dạng tổng của hai số hạng, mỗi số hạng là 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.

Phiên bản ban đầu của thuật toán có thể yêu cầu nhiều bước trừ để tìm ƯCLN nếu một trong hai số lớn hơn nhiều so với số còn lại. Một biến thể khác của thuật toán giúp rút ngắn số bước, thay vì trừ, sẽ thay số lớn hơn bằng số dư khi chia cho số nhỏ hơn và dừng lại khi số dư bằng không. Phiên bản này chỉ cần số bước tối đa bằng năm lần số chữ số của số nhỏ hơn trong hệ thập phân. Gabriel Lamé chứng minh đ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 nhằm nâng cao hiệu quả của thuật toán cũng đã được phát triển trong thế kỷ 20.

Thuật toán Euclid có nhiều ứng dụng quan trọng trong lý thuyết và thực tiễn. Nó không chỉ dùng để đơn giản hóa phân số và thực hiện phép chia trong số học modulo mà còn đóng vai trò quan trọng trong các giao thức mã hóa để bảo vệ kết nối Internet và phá vỡ các hệ thống mã hóa qua phân tích số nguyên. Thuật toán này còn được áp dụng trong việc giải phương trình Diophantine, như tìm số phù hợp với 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ỉ chính xác cho số thực. Cuối cùng, nó là công cụ thiết yếu trong việc chứng minh nhiều định lý trong lý thuyết số, chẳng hạn 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 thành các thừa số nguyên tố. Ban đầu, thuật toán Euclid chỉ áp dụng cho 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 trong đại số trừu tượng như miền Euclid.

Khái niệm

Thuật toán Euclid được sử dụng để tính ước chung lớn nhất (ƯCLN) của hai số tự nhiên a và b. ƯCLN g là số lớn nhất có thể chia đều cho cả a và b mà không có 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. Điều này không có nghĩa là a và b là số nguyên tố. Ví dụ, 6 và 35 không phải là số nguyên tố vì chúng có thể 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 là nguyên tố cùng nhau vì chúng không có thừa số chung nào.

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

ƯCLN có thể được hình dung như sau. Xét một hình chữ nhật kích thước a × b và một ước chung c nào đó có thể chia hết cho cả a và b. Cả hai cạnh của hình chữ nhật có thể chia thành các đoạn có độ dài c, tạo thành các hình vuông có cạnh dài c. ƯCLN g chính là giá trị lớn nhất của c để điều này có thể thực hiện. Ví dụ, một hình chữ nhật 24 × 60 có thể chia thành các hình vuông có cạnh 1, 2, 3, 4, 6 hoặc 12, trong đó 12 là ƯCLN của 24 và 60, vì nó chia được hình chữ nhật thành hai hình vuông trên cạnh 24/12 = 2 và năm hình vuông trên cạnh 60/12 = 5.

ƯCLN của hai số a và b là tích của các thừa số nguyên tố chung của chúng, với mỗi thừa số có thể xuất hiện nhiều lần, miễn là tích của các thừa số đó chia hết cho cả a và b. Ví dụ, phân tích 1386 = 2 × 3 × 3 × 7 × 11 và 3213 = 3 × 3 × 3 × 7 × 17, cho thấy ƯCLN của 1386 và 3213 là 63 = 3 × 3 × 7. Nếu hai số không có thừa số chung nào, ƯCLN của chúng là 1 (trường hợp của tích rỗng), nghĩa là chúng nguyên tố cùng nhau. Thuật toán Euclid có ưu điểm tính ƯCLN mà không cần phân tích thừa số nguyên tố, điều này rất quan trọng trong bảo mật mật mã vì phân tích số nguyên lớn rất khó khăn.

Một định nghĩa khác của ƯCLN hữu ích trong toán học nâng cao, đặc biệt là trong lý thuyết vành, là ƯCLN g của hai số a và b không bằng không là tổ hợp tuyến tính nhỏ nhất của a và b, tức là số nhỏ nhất có 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 của a và b chính là 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ữ hiện đại, ideal tạo bởi a và b là ideal tạo bởi g (ideal chủ yếu, tất cả các ideal của số nguyên đều là ideal chủ yếu). Điều này giúp nhận ra các tính chất của ƯCLN dễ dàng hơn, chẳng hạn như bất kỳ ước chung nào của a và b đều chia hết cho ƯCLN.

ƯCLN của ba số trở lên là tích của các thừa số nguyên tố chung của tất cả ba số đó, hoặc có thể tính bằng cách tìm ƯCLN của từng cặp số trong ba số đó.

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

Như vậy, thuật toán Euclid, mặc dù chỉ được thiết kế để tính ƯCLN của hai số nguyên, cũng có thể mở rộng để tính ƯCLN của bất kỳ số lượng số nguyên nào.

Mô tả

Thuật toán

Thuật toán Euclid bao gồm một chuỗi các bước liên tiếp, trong đó kết quả của mỗi bước được sử dụng làm dữ liệu đầu vào cho bước kế tiếp. Đặt k là số nguyên đếm số bước của thuật toán, bắt đầu từ 0 (với bước đầu tiên tương ứng với k = 0, bước tiếp theo là k = 1, và tiếp tục như vậy).

Mỗi bước của thuật toán bắt đầu với hai số dư không âm rk₋₁ và rk₋₂. Vì thuật toán đảm bảo rằng số dư luôn giảm dần qua từng bước, ta có rk₋₁ phải nhỏ hơn rk₋₂. Mục tiêu của bước thứ k là xác định thương qk và số dư rk sao cho thỏa mãn phương trình

$r_{k-<!--\; -\; -->2}=q_k{r}_{k-<!--\; -\; -->1}+r_k$

và 0 ≤ rk < rk₋₁. Nói cách khác, từ số dư lớn hơn rk₋₂, ta trừ bội của số dư nhỏ hơn rk₋₁ cho đến khi phần dư rk nhỏ hơn rk₋₁.

Trong bước đầu tiên (k = 0), các số dư r₋₂ và r₋₁ tương ứng với a và b, hai số cần tìm ƯCLN. Bước tiếp theo (k = 1) sẽ có số dư lần lượt là b và số dư r₀ từ bước trước,... Do đó, thuật toán có thể được diễn tả bằng một chuỗi các phương trình

Nếu a nhỏ hơn b, thuật toán sẽ hoán đổi vị trí của hai số. Ví dụ, nếu a < b, thì thương q₀ sẽ là không và số dư r₀ sẽ là a. Như vậy, số dư rk sẽ luôn nhỏ hơn rk₋₁ với mọi k ≥ 0.

Vì số dư luôn giảm dần qua từng bước và không thể trở thành số âm, số dư cuối cùng rN phải là không và thuật toán sẽ kết thúc tại đây. Số dư khác không trước đó rN₋₁ chính là ƯCLN của a và b. Số N không thể 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 chính xác

Để chứng minh tính chính xác của thuật toán Euclid, có thể thực hiện qua hai bước. Bước đầu tiên, cần chứng minh số dư khác không cuối cùng rN₋₁ chia hết cả a và b. Do rN₋₁ là một ước chung, nên nó phải nhỏ hơn hoặc bằng ƯCLN g. Bước thứ hai, chứng minh rằng bất kỳ ước chung nào của a và b, bao gồm cả g, phải chia hết cho rN₋₁, từ đó, g phải nhỏ hơn hoặc bằng rN₋₁. Hai kết luận này mâu thuẫn trừ khi rN₋₁ = g.

Để chứng minh rằng rN₋₁ chia hết cho cả a và b, cần chứng minh rằng rN₋₁ chia hết cho số dư ngay trước nó là rN₋₂:

r_N−2 = q_N r_N−1

Vì số dư cuối cùng rN là không, nên rN₋₁ cũng chia hết cho số dư rN₋₃:

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

Vì rN₋₁ chia hết cho cả hai số hạng trong vế phải của phương trình, ta có thể chứng minh tương tự rằng rN₋₁ chia hết cho tất cả số dư trước nó, bao gồm cả a và b. Không có số dư trước rN₋₂, rN₋₃,... chia hết cho a và b khi số dư là không. Do đó, vì rN₋₁ là ước chung của a và b, ta có rN₋₁ ≤ g.

Trong bước thứ hai, nếu có một số tự nhiên c chia hết cho cả a và b (tức là ước chung của a và b), thì c cũng phải chia hết cho số dư rk. Theo định nghĩa, a và b có thể được biểu diễn dưới dạng bội của c: a = mc và b = nc, với m và n là các số tự nhiên. Do đó, r₀ = a − q₀b = mc − q₀nc = (m − q₀n)c, vì vậy c là một ước của số dư ban đầu r₀. Tương tự như bước một, c cũng là ước của các số dư sau r₁, r₂,... Do đó, ƯCLN g cũng là ước của rN₋₁, tức là g ≤ rN₋₁. Kết hợp hai kết luận này, ta có g = rN₋₁. Vậy g chính là ƯCLN của tất cả các cặp số liên tiếp.

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

Ví dụ

Áp dụng thuật toán Euclid để tìm ƯCLN của a = 1071 và b = 462. Đầu tiên, ta trừ bội của 462 từ 1071 để có đượ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, ta đượ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, ta có được thương q₂ = 7 và số dư là 0:

147 = 7 × 21 + 0.

Vì số dư cuối cùng là 0, thuật toán dừng lại với 21 là ƯCLN của 1071 và 462, trùng khớp với ƯCLN tính được từ phép phân tích thừa số nguyên tố như đã trình bày trên. Các bước được tổng hợp trong bảng dưới đây:

Minh họa

Giải thuật Euclid có thể được hình dung qua bài toán lấp đầy một hình chữ nhật bằng các hình vuông. Giả sử ta có một hình chữ nhật kích thước a × b với a lớn hơn b. Đầu tiên, ta đặt các hình vuông kích thước b × b lên hình chữ nhật, phần còn lại sẽ là một hình chữ nhật b × r₀ với r₀ < b. Sau đó, ta tiếp tục đặt các hình vuông kích thước r₀ × r₀ lên phần còn lại, phần còn lại sẽ là hình chữ nhật r₁ × r₀. Quá trình này tiếp tục cho đến khi không còn phần trống. Khi đó, cạnh của hình vuông nhỏ nhất chính là ƯCLN của hai cạnh ban đầu. Ví dụ, hình vuông nhỏ nhất trong hình minh họa là 21 × 21 (màu đỏ), và 21 là ƯCLN của 1071 và 462, hai cạnh của hình chữ nhật ban đầu (màu xanh lá).

Phép chia có dư

Tại mỗi bước k, giải thuật Euclid tính toán thương qk và số dư rk dựa trên hai số rk₋₁ và rk₋₂:

r_k−2 = q_k r_k−1 + r_k

Trong đó, rk không âm và luôn nhỏ hơn giá trị tuyệt đối của rk₋₁. Định lý nền tảng cho phép chia có dư chứng minh rằng luôn tồn tại duy nhất một thương và số dư như vậy.

Trong phiên bản gốc của thuật toán, thương và số dư được xác định bằng cách thực hiện phép trừ liên tiếp: trừ rk₋₁ từ rk₋₂ và tiếp tục cho đến khi số dư rk nhỏ hơn rk₋₁. Sau đó, hoán đổi chúng và lặp lại quá trình. Phép chia có dư cho phép giảm số bước hoán đổi xuống chỉ còn một bước duy nhất. Thêm vào đó, phép chia có dư có thể được thay thế bằng phép toán modulo, chỉ trả về số dư. Như vậy, dạng lặp của thuật toán Euclid sẽ trở thành

r_k = r_k−2 mod r_k−1.

Chương trình

Thuật toán Euclid có thể được diễn đạt qua mã giả. Ví dụ, dạng phép chia của nó có thể được lập trình như sau

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

Tại mỗi vòng lặp k, biến b chứa giá trị số dư rk₋₁, còn biến a chứa số dư trước đó rk₋₂. Bước b := a mod b tương đương với công thức đệ quy rk ≡ rk₋₂ mod rk₋₁. Biến tạm thời t lưu giá trị rk₋₁ khi tính số dư tiếp theo. Cuối vòng lặp, b là giá trị của rk, và a là số dư trước đó của rk₋₁.

Trong dạng phép trừ (phiên bản gốc của thuật toán), bước b := a mod b được thay thế bằng việc thực hiện phép trừ liên tiếp. Khác với phép chia, phép trừ yêu cầu đầu vào là số nguyên dương và sẽ 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 liên tục hoán đổi giá trị của các số dư trước đó rk₋₁ và rk₋₂. Nếu a > b tại đầu mỗi vòng lặp, a bằng rk₋₂ vì rk₋₂ > rk₋₁. Trong vòng lặp, a được giảm dần bằng cách trừ đi bội của số dư b cho đến khi a nhỏ hơn b. Khi đó, a trở thành số dư kế tiếp. Sau đó, b được giảm dần bằng cách trừ đi bội của a cho đến khi nó nhỏ hơn a, và phần còn lại trở thành số dư tiếp theo, và tiếp tục như vậy.

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

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

Với dạng này, ƯCLN(1071, 462) được tính bằng ƯCLN(462, 1071 mod 462) = ƯCLN(462, 147). ƯCLN tiếp theo được tính từ ƯCLN(147, 462 mod 147) = ƯCLN(147, 21), và cuối cùng là ƯCLN(21, 147 mod 21) = ƯCLN(21, 0) = 21.

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

Trong một phiên bản khác của thuật toán Euclid, thương thu được tại mỗi bước sẽ được cộng thêm 1 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 là

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ằng

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.

Khi thay thế r_k bằng e_k với |e_k| < |r_k|, ta có một phiên bản khác của thuật toán Euclid, trong đó ở mỗi bước,

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

Leopold Kronecker đã chứng minh rằng phiên bản này yêu cầu số bước tối thiểu so với tất cả các dạng khác của thuật toán Euclid. Hơn nữa, có thể chứng minh rằng với bất kỳ cặp số a và b, số bước cần để tính ƯCLN là nhỏ nhất khi và chỉ khi q_k được chọn sao cho với $\mathrm{\phi <!--\; \phi \; -->}$ là tỷ lệ vàng.

Lịch sử phát triển

Giải thuật Euclid là một trong những thuật toán cổ xưa 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à trong cuốn 7 (mệnh đề 1–2) và cuốn 10 (mệnh đề 2–3). Cuốn 7 trình bày thuật toán cho các số nguyên, trong khi cuốn 10 áp dụng cho độ dài của đoạn thẳng. (Hiện nay, chúng ta có thể nói thuật toán áp dụng 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 hiện đại, không có đơn vị đo cụ thể và tự nhiên; người xưa 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 cả hai; nói cách khác, các độ dài a và b là bội số của độ dài g.

Có thể giải thuật này không phải do Euclid trực tiếp phát minh (ông đã sưu tầm và tổng hợp các công trình của các nhà toán học khác trong bộ Cơ sở). Theo nhà toán học và sử học B. L. van der Waerden, cuốn 7 có thể bắt nguồn từ một sách giáo khoa về lý thuyết số của các học trò Pythagoras. Giải thuật có thể đã được biết đến bởi Eudoxus của Cnidus (khoảng 375 TCN), hoặc thậm chí có thể đã tồn tại 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 phát hiện độc lập ở Ấn Độ và Trung Quốc, chủ yếu để giải phương trình Diophantine 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 học Ấn Độ Aryabhata gọi giải thuật này là 'máy nghiền', có thể là do 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 được mô tả và truyền bá tại châu Âu lần đầu tiên 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ố. Phiên bản mở rộng của giải thuật Euclid được cho là do Roger Cotes phát triển và được Nicholas Saunderson xuất bản như một phương pháp tính liên phân số nhanh chóng.

Vào 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 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 đã 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à nền tảng của phần lớn lý thuyết số. Dirichlet nhận thấy rằng nhiều hệ quả của lý thuyết số đú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ác bài giảng của Dirichlet về lý thuyết số đã được Richard Dedekind biên tập và mở rộng, ứ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. Ví dụ, Dedekind là người đầu tiên chứng minh định lý Fermat về tổng của hai số chính phương qua phân tích số nguyên Gauss. Ông cũng định nghĩa khái niệm miền Euclid, một hệ thống số trong đó một dạng tổng quát của giải thuật Euclid có thể được xác định. Vào cuối thế kỷ 19, giải thuật Euclid dần bị thay thế bởi lý thuyết tổng quát của Dedekind về ideal.

Trong thế kỷ 19, nhiều ứng dụng mới của giải thuật Euclid đã được phát triển. Vào năm 1829, Charles Sturm chứng minh rằng giải thuật này có giá trị 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 nhất định.

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

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

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

Ghi chú

Chú thích

• Cohen, H. (1993). Khóa học về Lý thuyết số đại số tính toán. New York: Springer-Verlag. ISBN 0-387-55640-0.
• Cohn, H. (1962). Lý thuyết số nâng cao. New York: Dover. ISBN 0-486-64023-X.
• Cox, D.; Little, J.; O'Shea, D. (1997). Các lý thuyết, biến thể và thuật toán: Giới thiệu về Hình học đại số tính toán và Đại số giao hoán (ấn bản 2). Springer-Verlag. ISBN 0-387-94680-2.
• Crandall, R.; Pomerance, C. (2001). Các số nguyên tố: Một cái nhìn tính toán (ấn bản 1). New York: Springer-Verlag. ISBN 0-387-94777-9.
• Lejeune Dirichlet, P. G. (1894). Dedekind, Richard (biên tập). Giảng bài về Lý thuyết số (bằng tiếng Đức). Braunschweig: Vieweg. LCCN 03005859. OCLC 490186017.
• Knuth, D. E. (1997). Nghệ thuật lập trình máy tính, Tập 2: Các thuật toán bán số (ấn bản 3). Addison–Wesley. ISBN 0-201-89684-2.

Các liên kết ngoài

• Các minh họa về giải thuật Euclid
• Weisstein, Eric W., 'Giải thuật Euclid' từ MathWorld.
• Giải thuật Euclid tại cut-the-knot
• Giải thuật của Euclid tại trang PlanetMath.org.
• Giải thuật Euclid tại MathPages
• Âm nhạc và giải thuật Euclid