Giải thuật Euclid

với hai số 49 và 21 có kết quả ƯCLN là 7.|thế=|417x417px]]
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&nbsp;=&nbsp;21&nbsp;×&nbsp;12 và 105&nbsp;=&nbsp;21&nbsp;×&nbsp;5) và cũng là ƯCLN của 105 và 252&nbsp;−&nbsp;105&nbsp;=&nbsp;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

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&nbsp;=&nbsp;2&nbsp;×&nbsp;3 và 35&nbsp;=&nbsp;5&nbsp;×&nbsp;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.

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&nbsp;=&nbsp;2) và năm hình vuông nằm trên cạnh còn lại (60/12&nbsp;=&nbsp;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&nbsp;×&nbsp;3&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;11 và 3213 = 3&nbsp;×&nbsp;3&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;17 nên ước chung lớn nhất 1386 và 3213 bằng 63&nbsp;=&nbsp;3&nbsp;×&nbsp;3&nbsp;×&nbsp;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&nbsp;+&nbsp;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,

:

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 rk&x2212;1 và rk&x2212;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 rk&x2212;1 nhỏ hơn rk&x2212;2. Mục tiêu của bước thứ k là tìm thương qk và số dư rk thỏa mãn phương trình
: r_{k-2} = q_k r_{k-1} + r_k
và 0 ≤ rk&nbsp;k&x2212;1. Nói cách khác, từ số lớn hơn rk&x2212;2, trừ đi bội của số nhỏ hơn rk&x2212;1 đến khi phần dư rk nhỏ hơn rk&x2212;1.

Ở bước đầu tiên (k&nbsp;=&nbsp;0), số dư r−2 và r−1 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ư r0 ở 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{align}
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{align}

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 0 bằng không và số dư r0 bằng a. Do đó, rk luôn nhỏ hơn rk−1 với mọi k&nbsp;≥&nbsp;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 rN 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 rN−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 r0 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 rN−1 chia được cả a và b. Vì rN−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 rN−1; từ đó, g phải nhỏ hơn hoặc bằng rN−1. Hai kết luận trên là mâu thuẫn trừ khi rN−1&nbsp;=&nbsp;g.

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

:

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

:

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ự, rN−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 rN−2, rN−3,... chia bởi a và b cho số dư bằng không. Vì rN−1 là ước chung của a và b nên rN−1&nbsp;≤&nbsp;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ư rk. Theo định nghĩa thì a và b có thể được viết thành bội của c: a&nbsp;=&nbsp;mc và b&nbsp;=&nbsp;nc với m và n là các số tự nhiên. Ta có r0&nbsp;=&nbsp;a&nbsp;−&nbsp;q0b&nbsp;=&nbsp;mc&nbsp;−&nbsp;q0nc&nbsp;=&nbsp;(m&nbsp;−&nbsp;q0n)c nên c là một ước của số dư ban đầu r0. 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 r1, r2,... Từ đó, ước chung lớn nhất g là ước của rN−1 hay g&nbsp;≤&nbsp;rN−1. Kết hợp hai kết luận thu được, ta có g&nbsp;=&nbsp;rN−1. Vậy g là ước chung lớn nhất của tất cả cặp số liền sau:

:

Ví dụ

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

:

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

:

Tiếp tục trừ bội của 21 từ 147 thì được thương q2&nbsp;=&nbsp;7 và số dư là 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:

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 × r0 với r0&nbsp;0 × r0 lên phần hình trống đó thì còn lại phần hình trống thứ hai r1 × r0 mà ta cần phải đặt lên đó các hình vuông r1 × r1,... 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 &xD7; 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ư

Tại mỗi bước k, giải thuật Euclid tính một thương qk và số dư rk từ hai số rk−1 và rk−2:
:
trong đó rk không âm và nhỏ hơn giá trị tuyệt đối của rk−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ừ rk−1 từ rk−2 và lặp lại đến khi phần dư rk nhỏ hơn rk−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

:

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ư rk−1, trong khi biến a mang giá trị số dư liền trước rk−2. Bước b&nbsp;:=&nbsp;a mod b giống với công thức đệ quy như trên rk ≡ rk−2 mod rk−1. Biến tạm thời t mang giá trị rk−1 khi tính số dư liền sau rk. Cuối vòng lặp, biến b mang giá trị rk, trong khi biến a mang giá trị số dư liền trước rk−1.

Trong dạng phép trừ (dạng ban đầu của thuật toán), bước b&nbsp;:=&nbsp;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 rk−1 và rk−2. Giả sử a > b ở đầu một vòng lặp thì a bằng rk−2 vì rk−2 > rk−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 rk. 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ư rk+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(rN−1,&nbsp;0)&nbsp;=&nbsp;rN−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

:

là r'k−1&nbsp;>&nbsp;r'k&nbsp;>&nbsp;0}}. Tuy nhiên, có thể tính số dư âm bởi

:

nếu hoặc

:

nếu .

Nếu thay bằng với e'k&nbsp;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&nbsp;≤&nbsp;r'k&minus;1&nbsp;/&nbsp;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.

Lịch sử phát triển
, 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.

Đế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ố. 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.

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

:

:

.]]
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&nbsp;+&nbsp;2. Năm 1841, Pierre Joseph Étienne Finck đã chứng minh số bước chia nhiều nhất là 2&nbsp;log2&nbsp;v&nbsp;+&nbsp;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&nbsp;(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(h2). 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(h2). 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,&nbsp;b). Nếu g là ƯCLN của a và b thì a&nbsp;=&nbsp;mg và b&nbsp;=&nbsp;ng với m và n nguyên tố cùng nhau. Khi đó

:

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,&nbsp;b&nbsp;+&nbsp;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

:

trong đó T(x, 0)&nbsp;=&nbsp;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&nbsp;>&nbsp;b&nbsp;>&nbsp;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&nbsp;>&nbsp;b, thì người ta có a&nbsp;≥&nbsp;F N +2 và b&nbsp;≥&nbsp;F N +1 . Có thể chứng minh điều này bằng quy nạp như sau. Nếu N&nbsp;=&nbsp;1, a chia hết cho b; bộ số tự nhiên nhỏ nhất để điều này đúng là b&nbsp;=&nbsp;1 và a&nbsp;=&nbsp;2, tức lần lượt là F2 và F3. Giả sử kết quả đúng với mọi giá trị của N đến M&nbsp;−&nbsp;1. Bước đầu tiên của thuật toán M bước là a&nbsp;=&nbsp;q0b&nbsp;+&nbsp;r 0 và thuật toán Euclid yêu cầu M&nbsp;−&nbsp;1 bước cho cặp b&nbsp;>&nbsp;r 0 . Theo giả thiết quy nạp, ta có b&nbsp;≥&nbsp;F'M+1 và r0&nbsp;≥&nbsp;F'M. Do đó, a&nbsp;=&nbsp;q0b&nbsp;+&nbsp;r0&nbsp;≥&nbsp;b&nbsp;+&nbsp;r0&nbsp;≥&nbsp;F'M+1&nbsp;+&nbsp;FM&nbsp;=&nbsp;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.

: T(a) = \frac 1 a \sum_{0 \leq b

Tuy nhiên, vì T(a,&nbsp;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

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/π2) 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&nbsp;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:

:

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

:

Chi phí tính toán của việc chia số h bit tỷ lệ với , 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 }} trong đó . Để 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. Để 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 log log h).}}
Xem thêm
Giải thuật Euclid mở rộng

Ghi chú

Chú thích

Tham khảo

















Liên kết ngoài

Demonstrations of Euclid's algorithm

Euclid's Algorithm tại cut-the-knot

The Euclidean Algorithm tại MathPages
Music and Euclid's algorithm [Âm nhạc và giải thuật Euclid]