Xem mã nguồn của Giải thuật Euclid

[[Tập tin:Euclid's algorithm Book VII Proposition 2 3.png|thumb|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.|thế=|417x417px]]
Trong [[toán học]], '''giải thuật Euclid<ref group="gc">Một số sách giáo khoa như ''Topics in Algebra'' của I. N. Herstein và ''Algebra'' của Serge Lang sử dụng thuật ngữ "giải thuật Euclid" để liên hệ với [[phép chia có dư]]</ref>''' (hay '''thuật toán Euclid''') là một [[thuật toán|giải thuật]] để tính [[ước số chung lớn nhất|ướ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ở (Euclid)|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 [[Giải thuật Euclid mở rộng|đả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 ([[Bổ đề Bézout|đồng nhất thức Bézout]]), chẳng hạn, {{nowrap begin}}21 = 5 × 105 + (−2) × 252.{{nowrap end}}

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ề [[Phân số tối giản|dạng tối giản]] và thực hiện phép chia trong [[Số học mô đun|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ỉ Diophantos|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à [[Định lý cơ bản của số học|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 ==
{{Chính|Ướ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'').<ref>{{Harvnb|Stark|1978|p=16}}</ref>

Nếu ƯCLN(''a'', ''b'') = 1 thì ''a'' và ''b'' được gọi là hai số [[Số nguyên tố cùng nhau|nguyên tố cùng nhau]].<ref>{{Harvnb|Stark|1978|p=21}}</ref> Tính chất này không khẳng định ''a'' và ''b'' là [[số nguyên tố]].<ref>{{Harvnb|LeVeque|1996|p=32}}</ref> 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.
[[Tập tin:24x60.svg|nhỏ|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ỳ.<ref>{{Harvnb|LeVeque|1996|p=31}}</ref>

ƯCLN có thể được minh họa như sau.<ref>{{chú thích sách|title=Discrete Mathematics|url=https://archive.org/details/discretemathemat0000gros_a2g6|last=Grossman|first=J. W.|publisher=Macmillan|year=1990|isbn=0-02-348331-8|location=New York|page=[https://archive.org/details/discretemathemat0000gros_a2g6/page/213 213]}}</ref> 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''.<ref name="Schroeder_21">{{Harvnb|Schroeder|2005|pp=21–22}}</ref> 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ố.<ref>{{Harvnb|Schroeder|2005|p=19}}</ref><ref>{{chú thích sách|title=Excursions in number theory|url=https://archive.org/details/excursionsnumber00ogil|last1=Ogilvy|first1=C. S.|last2=Anderson|first2=J. T.|publisher=[[Oxford University Press]]|year=1966|isbn=|location=New York|pages=[https://archive.org/details/excursionsnumber00ogil/page/n30 27]–29}}</ref> Bài toán [[Phân tích số nguyê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.<ref name="Schroeder_216">{{Harvnb|Schroeder|2005|pp=216–219}}</ref>

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]].<ref name="Leveque_p33">{{Harvnb|LeVeque|1996|p=33}}</ref> Ướ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 (lý thuyết vành)|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,<ref>{{Harvnb|Stark|1978|p=25}}</ref> 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ố đó.<ref>{{Harvnb|Ore|1948|pp=47–48}}</ref> Chẳng hạn,

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

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

: <math>\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}</math>

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''<sub>0</sub> bằng không và số dư ''r''<sub>0</sub> bằng ''a''. Do đó, ''r<sub>k</sub>'' luôn nhỏ hơn ''r<sub>k</sub>''<sub>−1</sub> 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 ''r<sub>N</sub>'' phải bằng không và thuật toán dừng lại tại đó.<ref>{{Harvnb|Stark|1978|p=18}}</ref> Số dư khác không cuối cùng ''r<sub>N</sub>''<sub>−1</sub> 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''<sub>0</sub> 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.<ref>{{Harvnb|Stark|1978|pp=16–20}}</ref> Bước thứ nhất, cần chứng minh số dư khác không cuối cùng ''r<sub>N</sub>''<sub>−1</sub> chia được cả ''a'' và ''b''. Vì ''r<sub>N</sub>''<sub>−1</sub> 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<sub>N</sub>''<sub>−1</sub>; từ đó, ''g'' phải nhỏ hơn hoặc bằng ''r<sub>N</sub>''<sub>−1</sub>. Hai kết luận trên là mâu thuẫn trừ khi ''r<sub>N</sub>''<sub>−1</sub>&nbsp;=&nbsp;''g''.

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

: {{math|1=''r''<sub>''N''−2</sub> = ''q''<sub>''N''</sub> ''r''<sub>''N''−1</sub>}}

vì số dư cuối cùng ''r<sub>N</sub>'' bằng không. ''r<sub>N</sub>''<sub>−1</sub> cũng chia được số dư ''r<sub>N</sub>''<sub>−3</sub>:

: {{math|1=''r''<sub>''N''−3</sub> = ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub> + ''r''<sub>''N''−1</sub>}}

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<sub>N</sub>''<sub>−1</sub> 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<sub>N</sub>''<sub>−2</sub>, ''r<sub>N</sub>''<sub>−3</sub>,... chia bởi ''a'' và ''b'' cho số dư bằng không. Vì ''r<sub>N</sub>''<sub>−1</sub> là ước chung của ''a'' và ''b'' nên ''r<sub>N</sub>''<sub>−1</sub>&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ư ''r<sub>k</sub>''. 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ó ''r''<sub>0</sub>&nbsp;=&nbsp;''a''&nbsp;−&nbsp;''q''<sub>0</sub>''b''&nbsp;=&nbsp;''mc''&nbsp;−&nbsp;''q''<sub>0</sub>''nc''&nbsp;=&nbsp;(''m''&nbsp;−&nbsp;''q''<sub>0</sub>''n'')''c'' nên ''c'' là một ước của số dư ban đầu ''r''<sub>0</sub>. 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''<sub>1</sub>, ''r''<sub>2</sub>,... Từ đó, ước chung lớn nhất ''g'' là ước của ''r<sub>N</sub>''<sub>−1</sub> hay ''g''&nbsp;≤&nbsp;''r<sub>N</sub>''<sub>−1</sub>. Kết hợp hai kết luận thu được, ta có ''g''&nbsp;=&nbsp;''r<sub>N</sub>''<sub>−1</sub>. Vậy ''g'' là ước chung lớn nhất của tất cả cặp số liền sau:<ref>{{harvnb|Knuth|1997|p=320}}</ref><ref name="Lovasz_2003">{{chú thích sách|title=Discrete Mathematics: Elementary and Beyond|last1=Lovász|first1=L.|last2=Pelikán|first2=J.|last3=Vesztergombi|first3=K.|publisher=Springer-Verlag|year=2003|isbn=0-387-95584-4|location=New York|pages=100–101|author1-link=László Lovász}}</ref>

: {{math|1=''g'' = ƯCLN(''a'', ''b'') = ƯCLN(''b'', ''r''<sub>0</sub>) = ƯCLN(''r''<sub>0</sub>, ''r''<sub>1</sub>) = … = ƯCLN(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''r''<sub>''N''−1</sub>.}}

=== Ví dụ ===
[[Tập tin:Euclidean algorithm 1071 462.gif|nhỏ|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 &#xD7; 462 thì còn lại hình chữ nhật 462 &#xD7; 147. Tiếp tục đặt vào hình chữ nhật đó các hình vuông 147 &#xD7; 147 đến khi còn lại hình chữ nhật 21 &#xD7; 147. Cuối cùng, đặt vào phần hình còn lại đó các hình vuông 21 &#xD7; 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''&nbsp;=&nbsp;1071 và ''b'' = 462. Đầu tiên, ta trừ bội của 462 từ 1071 thì được thương ''q''<sub>0</sub>&nbsp;=&nbsp;2 và số dư là 147:

: {{math|1=1071 = 2 × 462 + 147.}}

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

: {{math|1=462 = 3 × 147 + 21.}}

Tiếp tục trừ bội của 21 từ 147 thì được thương ''q''<sub>2</sub>&nbsp;=&nbsp;7 và số dư là 0:

: {{math|1=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ố [[Giải thuật Euclid#Ý tưởng|như trên]]. Các bước được tóm tắt thành bảng sau:

{| class="wikitable" id="basic_Euclidean_algorithm" style="margin-left:auto; margin-right:auto; text-align:center"
|-
!Bước ''k''!!Phương trình!!Thương và số dư
|-
| 0 || {{math|1=1071 = ''q''<sub>0</sub> 462 + ''r''<sub>0</sub>}} || {{math|1=''q''<sub>0</sub> = 2}} và {{math|1=''r''<sub>0</sub> = 147}}
|-
| 1 || {{math|1=462 = ''q''<sub>1</sub> 147 + ''r''<sub>1</sub>}} || {{math|1=''q''<sub>1</sub> = 3}} và {{math|1=''r''<sub>1</sub> = 21}}
|-
| 2 || {{math|1=147 = ''q''<sub>2</sub> 21 + ''r''<sub>2</sub>}} || {{math|1=''q''<sub>2</sub> = 7}} và {{math|1=''r''<sub>2</sub> = 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.<ref name="Kimberling_1983">{{chú thích tạp chí|last=Kimberling|first=C.|authorlink=Clark Kimberling|year=1983|title=A Visual Euclidean Algorithm|url=https://archive.org/details/sim_mathematics-teacher_1983-02_76_2/page/108|journal=Mathematics Teacher|volume=76|pages=108–109}}</ref> 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''<sub>0</sub> với ''r''<sub>0</sub>&nbsp;<&nbsp;''b''. Tiếp theo, ta đặt các hình vuông ''r''<sub>0</sub> × ''r''<sub>0</sub> lên phần hình trống đó thì còn lại phần hình trống thứ hai ''r''<sub>1</sub> × ''r''<sub>0</sub> mà ta cần phải đặt lên đó các hình vuông ''r''<sub>1</sub> × ''r''<sub>1</sub>,... 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ư ===
{{Chính|Phép chia có dư}}
Tại mỗi bước ''k'', giải thuật Euclid tính một thương ''q<sub>k</sub>'' và số dư ''r<sub>k</sub>'' từ hai số ''r<sub>k</sub>''<sub>−1</sub> và ''r<sub>k</sub>''<sub>−2</sub>:
: {{math|1=''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}}
trong đó ''r<sub>k</sub>'' không âm và nhỏ hơn [[giá trị tuyệt đối]] của ''r<sub>k</sub>''<sub>−1</sub>. Đị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.<ref>{{chú thích sách|title=Abstract Algebra|url=https://archive.org/details/abstractalgebra00dumm_304|last=Dummit|first=David S.|last2=Foote|first2=Richard M.|publisher=John Wiley & Sons, Inc.|year=2004|isbn=978-0-471-43334-7|location=|pages=[https://archive.org/details/abstractalgebra00dumm_304/page/n283 270]-271}}</ref>

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<sub>k</sub>''<sub>−1</sub> từ ''r<sub>k</sub>''<sub>−2</sub> và lặp lại đến khi phần dư ''r<sub>k</sub>'' nhỏ hơn ''r<sub>k</sub>''<sub>−1</sub>, 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|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

: {{math|1=''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>.}}

=== 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<ref>{{harvnb|Knuth|1997|pp=319–320}}</ref>
 '''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<sub>k</sub>''<sub>−1</sub>, trong khi biến ''a'' mang giá trị số dư liền trước ''r<sub>k</sub>''<sub>−2</sub>. Bước <code>b&nbsp;:=&nbsp;a '''mod''' b</code> giống với công thức đệ quy như trên ''r<sub>k</sub>'' ≡ ''r<sub>k</sub>''<sub>−2</sub> mod ''r<sub>k</sub>''<sub>−1</sub>. [[Biến tạm thời]] ''t'' mang giá trị ''r<sub>k</sub>''<sub>−1</sub> khi tính số dư liền sau ''r<sub>k</sub>''. Cuối vòng lặp, biến ''b'' mang giá trị ''r<sub>k</sub>'', trong khi biến ''a'' mang giá trị số dư liền trước ''r<sub>k</sub>''<sub>−1</sub>.

Trong dạng phép trừ (dạng ban đầu của thuật toán), bước <code>b&nbsp;:=&nbsp;a '''mod''' b</code> được thay bằng phép trừ lặp lại.<ref>{{harvnb|Knuth|1997|pp=318–319}}</ref> 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<sub>k</sub>''<sub>−1</sub> và ''r<sub>k</sub>''<sub>−2</sub>. Giả sử ''a'' > ''b'' ở đầu một vòng lặp thì ''a'' bằng ''r<sub>k</sub>''<sub>−2</sub> vì ''r<sub>k</sub>''<sub>−2</sub> > ''r<sub>k</sub>''<sub>−1</sub>. 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<sub>k</sub>''. 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<sub>k</sub>''<sub>+1</sub>,...

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<sub>N</sub>''<sub>−1</sub>,&nbsp;0)&nbsp;=&nbsp;''r<sub>N</sub>''<sub>−1</sub>.<ref>{{Harvnb|Stillwell|1997|p=14}}</ref>
 '''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.<ref name="Ore_least_abs_remainders">{{Harvnb|Ore|1948|p=43}}</ref><ref name="Stewart_1964">{{chú thích sách|title=Theory of Numbers|url=https://archive.org/details/theorynumbers00stew|last=Stewart|first=B. M.|publisher=Macmillan|year=1964|edition=2 |location=New York|pages=[https://archive.org/details/theorynumbers00stew/page/n53 43]–44|lccn=64010964}}</ref> Điều kiện của phương trình

: {{math|1=''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}}

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

: {{math|1=''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> + 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>}}

nếu {{math|''r''<sub>''k''−1</sub>&nbsp;>&nbsp;0}} hoặc

: {{math|1=''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> &minus; 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>}}

nếu {{math|''r''<sub>''k''−1</sub>&nbsp;<&nbsp;0}}.

Nếu thay {{math|''r''<sub>''k''</sub>}} bằng {{math|''e''<sub>''k''</sub>}} với {{math|{{!}}''e''<sub>''k''</sub>{{!}}&nbsp;<&nbsp;{{!}}''r''<sub>''k''</sub>{{!}}}} thì ta có một dạng khác của giải thuật Euclid sao cho trong mỗi bước,

: {{math|{{!}}''r''<sub>''k''</sub>{{!}}&nbsp;≤&nbsp;{{!}}''r''<sub>''k''&minus;1</sub>{{!}}&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.<ref name="Ore_least_abs_remainders" /><ref name="Stewart_1964" /> 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 {{math|''q''<sub>''k''</sub>}} được chọn sao cho <math>\left |\frac{r_{k+1}}{r_k}\right |<\frac{1}{\varphi}\sim 0,618</math> với <math>\varphi</math> là [[tỷ lệ vàng]].<ref>{{chú thích tạp chí|last=Lazard|first=D.|year=1977|title=Le meilleur algorithme d'Euclide pour ''K''[''X''] et '''Z'''|journal=Comptes rendus de l'Académie des Sciences|language=fr|volume=284|pages=1–4}}</ref>

== Lịch sử phát triển ==
[[Tập tin:Euklid.jpg|nhỏ|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.<ref name="Knuth, p. 318">{{Harvnb|Knuth|1997|p=318}}</ref> Nó xuất hiện trong bộ [[Cơ sở (Euclid)|''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ở'').<ref name="Weil_1983">{{chú thích sách|title=Number Theory|last=Weil|first=A.|publisher=Birkhäuser|year=1983|isbn=0-8176-3141-0|location=Boston|pages=4–6}}</ref><ref name="Jones_1994">{{chú thích sách|title=Companion encyclopedia of the history and philosophy of the mathematical sciences|last=Jones|first=A.|publisher=Routledge|year=1994|isbn=0-415-09238-8|location=New York|pages=46–48|chapter=Greek mathematics to AD 300}}</ref> Nhà toán học và sử học [[Bartel Leendert van der Waerden|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]].<ref name="van_der_Waerden_1954">{{chú thích sách|url=https://archive.org/details/scienceawakening00waer|title=Science Awakening|last=van der Waerden|first=B. L.|publisher=P. Noordhoff Ltd|year=1954|isbn=|series=Arnold Dresden dịch|location=Groningen|pages=[https://archive.org/details/scienceawakening00waer/page/114 114–115]|authorlink=Bartel Leendert van der Waerden}}</ref> Giải thuật có thể đã được biết bởi [[Eudoxus của Cnidus]] (khoảng 375 TCN),<ref name="Knuth, p. 318" /><ref>{{chú thích tạp chí|last=von Fritz|first=K.|year=1945|title=The Discovery of Incommensurability by Hippasus of Metapontum|url=https://archive.org/details/sim_annals-of-mathematics_1945-04_46_2/page/242|journal=Annals of Mathematics|volume=46|issue=2|pages=242–264|doi=10.2307/1969021|jstor=1969021}}</ref> hoặc thậm chí có thể đã có từ trước thời của ông,<ref>{{chú thích sách|url=https://archive.org/details/mathematicsinari0000heat|title=Mathematics in Aristotle|last=Heath|first=T. L.|publisher=Oxford Press|year=1949|isbn=|location=|pages=[https://archive.org/details/mathematicsinari0000heat/page/80 80–83]}}</ref><ref>{{chú thích sách|title=The Mathematics of Plato's Academy: A New Reconstruction|url=https://archive.org/details/mathematicsofpla0000fowl_h9l3|last=Fowler|first=D. H.|publisher=Oxford University Press|year=1987|isbn=0-19-853912-6|location=Oxford|pages=[https://archive.org/details/mathematicsofpla0000fowl_h9l3/page/31 31]–66}}</ref> 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à [[Aristoteles|Aristotle]].<ref>{{chú thích tạp chí|last=Becker|first=O.|year=1933|title=Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid|journal=Quellen und Studien zur Geschichte der Mathematik B|volume=2|pages=311–333}}</ref>

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]],<ref name="Stillwell, p. 31">{{Harvnb|Stillwell|1997|p=31}}</ref> chủ yếu để giải [[Phương trình Diophantos|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",<ref name="Tattersall, p. 70">{{Harvnb|Tattersall|2005|p=70}}</ref> có thể là vì tính hiệu quả của nó trong việc [[giải phương trình]] Diophantine.<ref>{{Harvnb|Rosen|2000|pp=86–87}}</ref> 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]]'',<ref>{{Harvnb|Ore|1948|pp=247–248}}</ref> 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.<ref>{{Harvnb|Tattersall|2005|pp=72, 184–185}}</ref> 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 [[Claude Gaspar Bachet de Méziriac|Bachet]] năm 1624.<ref name="Tattersall, p. 70" /> 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ố.<ref>{{chú thích sách|url=http://www.e-rara.ch/zut/content/structure/2440626|title=The Elements of Algebra in Ten Books|last1=Saunderson|first1=Nicholas|date=1740|publisher=University of Cambridge Press|year=|isbn=|location=|pages=|access-date = ngày 6 tháng 7 năm 2020}}</ref><ref>{{Harvnb|Tattersall|2005|pp=72–76}}</ref>

Đế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 Friedrich Gauß|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.<ref name="Gauss_1832">{{chú thích tạp chí|last=Gauss|first=C. F.|authorlink=Carl Friedrich Gauss|year=1832|title=Theoria residuorum biquadraticorum|journal=Comm. Soc. Reg. Sci. Gött. Rec.|volume=4}} In lại trong {{chú thích sách|title=Werke|last=Gauss|first=C. F.|publisher=Cambridge Univ. Press|year=2011|volume=2|pages=65–92|chapter=Theoria residuorum biquadraticorum commentatio prima|doi=10.1017/CBO9781139058230.004}} và {{chú thích sách|title=Werke|last=Gauss|first=C. F.|publisher=Cambridge Univ. Press|year=2011|volume=2|pages=93–148|chapter=Theoria residuorum biquadraticorum commentatio secunda|doi=10.1017/CBO9781139058230.005}}</ref> 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ố.<ref name="Stillwell, p. 31" /> [[Johann Peter Gustav Lejeune Dirichlet|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ố.<ref>{{Harvnb|Stillwell|1997|pp=31–32}}</ref> 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.<ref>{{Harvnb|Lejeune Dirichlet|1894|pp=29–31}}</ref> 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.<ref>[[Richard Dedekind]] trong {{Harvnb|Lejeune Dirichlet|1894|loc=phụ lục XI}}</ref> Ô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 (lý thuyết vành)|ideal]].<ref>{{Harvnb|Stillwell|2003|pp=41–42}}</ref>

{| class="toccolours" style="float: left; margin-left: 1em; margin-right: 1em; font-size: 85%; color:black; width:23em; max-width: 25%;" cellspacing="5"
| style="text-align: left;" |
"[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."
|-
| style="text-align: left;" | [[Donald Knuth]], ''The Art of Computer Programming, Vol. 2: Seminumerical Algorithms'', ấn bản 2 (1981), tr.&nbsp;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, [[Jacques Charles François Sturm|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ỳ.<ref>{{chú thích tạp chí|last=Sturm|first=C.|authorlink=Jacques Charles François Sturm|year=1829|title=Mémoire sur la résolution des équations numériques|journal=Bull. des sciences de Férussac|language=fr|volume=11|pages=419–422}}</ref>

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)<ref>{{MathWorld|urlname=IntegerRelation|title=Integer Relation}}</ref> hay [[thuật toán LLL]].<ref>{{chú thích tạp chí|last=Peterson|first=I.|date=ngày 12 tháng 8 năm 2002|title=Jazzing Up Euclid's Algorithm|url=http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm|journal=ScienceNews}}</ref><ref>{{chú thích tạp chí|last=Cipra|first=Barry Arthur|date=ngày 16 tháng 5 năm 2000|title=The Best of the 20th Century: Editors Name Top 10 Algorithms|url=https://www.siam.org/pdf/news/637.pdf|journal=SIAM News|publisher=Society for Industrial and Applied Mathematics|volume=33|issue=4|pages=|archive-url=https://web.archive.org/web/20160922144038/https://www.siam.org/pdf/news/637.pdf|archive-date = ngày 22 tháng 9 năm 2016 |access-date = ngày 6 tháng 7 năm 2020 |via=}}</ref>

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''.<ref>{{chú thích tạp chí|last1=Cole|first1=A. J.|last2=Davie|first2=A. J. T.|year=1969|title=A game based on the Euclidean algorithm and a winning strategy for it|url=https://archive.org/details/sim_mathematical-gazette_1969-12_53_386/page/354|journal=Math. Gaz.|volume=53|issue=386|pages=354–357|doi=10.2307/3612461|jstor=3612461}}</ref> Trò chơi này có một chiến lược chơi tối ưu.<ref>{{chú thích tạp chí|last=Spitznagel|first=E. L.|year=1973|title=Properties of a game based on Euclid's algorithm|journal=Math. Mag.|volume=46|issue=2|pages=87–92|doi=10.2307/2689037|jstor=2689037}}</ref> 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.<ref>{{Harvnb|Rosen|2000|p=95}}</ref><ref>{{chú thích sách|url=https://archive.org/details/Elementary_00_Robe/page/1|title=Elementary Number Theory: A Problem Oriented Approach|last=Roberts|first=J.|publisher=[[MIT Press]]|year=1977|isbn=0-262-68028-9|location=Cambridge, MA|pages=[https://archive.org/details/Elementary_00_Robe/page/1 1–8]}}</ref>

== Xem thêm ==
* [[Giải thuật Euclid mở rộng]] 
== Ghi chú ==
{{tham khảo|30em|group=gc}}
==Chú thích==
{{tham khảo|30em}}

== Tham khảo ==

* {{chú thích sách|url=https://books.google.com/?id=hXGr-9l1DXcC|title=A Course in Computational Algebraic Number Theory|last=Cohen|first=H.|publisher=Springer-Verlag|year=1993|isbn=0-387-55640-0|location=New York|pages=|doi=}}
* {{chú thích sách|url=https://books.google.com/?id=yMGeElJ8M0wC|title=Advanced Number Theory|last=Cohn|first=H.|publisher=Dover|year=1962|isbn=0-486-64023-X|location=New York|doi=}}
* {{chú thích sách|url=https://books.google.com/?id=7eLkq0wQytAC|title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra|last1=Cox|first1=D.|last2=Little|first2=J.|last3=O'Shea|first3=D.|publisher=Springer-Verlag|year=1997|isbn=0-387-94680-2|edition=2 |location=|pages=|doi=}}
* {{chú thích sách|title=Prime Numbers: A Computational Perspective|url=https://archive.org/details/primenumberscomp0000cran|last1=Crandall|first1=R.|last2=Pomerance|first2=C.|publisher=Springer-Verlag|year=2001|isbn=0-387-94777-9|edition=1 |location=New York|pages=}}
* {{chú thích sách|url=https://archive.org/details/vorlesungenberz02dirigoog|title=Vorlesungen über Zahlentheorie (Lectures on Number Theory)|last=Lejeune Dirichlet|first=P. G.|publisher=Vieweg|year=1894|isbn=|editor-last=Dedekind|editor-first=Richard|editor-link=Richard Dedekind|location=Braunschweig|pages=|language=de|doi=|lccn=03005859|oclc=490186017}}
* {{chú thích sách|title=[[The Art of Computer Programming]], Volume 2: Seminumerical Algorithms|last=Knuth|first=D. E.|publisher=Addison–Wesley|year=1997|isbn=0-201-89684-2|edition=3 |author-link=Donald Knuth}}
* {{chú thích sách|title=Fundamentals of Number Theory|url=https://archive.org/details/fundamentalsofnu0000leve|last=LeVeque|first=W. J.|publisher=Dover|year=1996|isbn=0-486-68906-9|location=New York|pages=|origyear=1977}}
* {{chú thích sách|title=Fundamental Number Theory with Applications|last=Mollin|first=R. A.|publisher=Chapman & Hall/CRC|year=2008|isbn=978-1-4200-6659-3|edition=2 |location=Boca Raton}}
* {{chú thích sách|url=https://archive.org/details/numbertheoryitsh00ore|title=Number Theory and Its History|last=Ore|first=O.|publisher=McGraw–Hill|year=1948|isbn=|location=New York|pages=|doi=}}
* {{chú thích sách|title=Elementary Number Theory and its Applications|last=Rosen|first=K. H.|publisher=Addison–Wesley|year=2000|isbn=0-201-87073-8|edition=4 |location=Reading, MA|doi=}}
* {{chú thích sách|title=Number Theory in Science and Communication|last=Schroeder|first=M.|publisher=Springer-Verlag|year=2005|isbn=0-387-15800-6|edition=4 |location=|pages=|doi=}}
* {{chú thích sách|url=https://archive.org/details/introductiontonu00star_0|title=An Introduction to Number Theory|last=Stark|first=H.|publisher=MIT Press|year=1978|isbn=0-262-69060-8|location=|pages=}}
* {{chú thích sách|title=Numbers and Geometry|last=Stillwell|first=J.|publisher=Springer-Verlag|year=1997|isbn=0-387-98289-2|location=New York|pages=|doi=}}
* {{chú thích sách|title=Elements of Number Theory|last=Stillwell|first=J.|publisher=Springer-Verlag|year=2003|isbn=0-387-95587-9|location=New York|doi=}}
* {{chú thích sách|title=Elementary Number Theory in Nine Chapters|url=https://archive.org/details/elementarynumber0000jame|last=Tattersall|first=J. J.|publisher=[[Cambridge University Press]]|year=2005|isbn=978-0-521-85014-8|location=Cambridge}}

== Liên kết ngoài ==
{{thể loại Commons|Euclidean algorithm}}

* [http://people.math.sc.edu/sumner/numbertheory/euclidean/euclidean.html Demonstrations of Euclid's algorithm]
* {{MathWorld|urlname=EuclideanAlgorithm|title=Euclidean Algorithm}}
* [http://www.cut-the-knot.org/blue/Euclid.shtml Euclid's Algorithm] tại [[Cut the Knot|cut-the-knot]]
* {{PlanetMath|urlname=EuclidsAlgorithm|title=Euclid's algorithm}}
* [http://www.mathpages.com/home/kmath384.htm The Euclidean Algorithm] tại MathPages
* [https://plus.maths.org/content/os/issue40/features/wardhaugh/index Music and Euclid's algorithm] [Âm nhạc và giải thuật Euclid]
{{Kiểm soát tính nhất quán}}

[[Thể loại:Thuật toán lý thuyết số]]