Editing Euclidean algorithm (section)

== Historical development ==
[[File:Euklid.jpg|thumb|upright|alt="Depiction of Euclid as a bearded man holding a pair of dividers to a tablet."|The Euclidean algorithm was probably invented before [[Euclid]], depicted here holding a [[Compass (drawing tool)|compass]] in a painting of about 1474.]]

The Euclidean algorithm is one of the oldest algorithms in common use.<ref name="Knuth, p. 318">{{harvnb|Knuth|1997}}, p. 318</ref> It appears in [[Euclid's Elements|Euclid's ''Elements'']] (c.&nbsp;300&nbsp;BC), specifically in Book&nbsp;7 (Propositions 1–2) and Book&nbsp;10 (Propositions 2–3). In Book&nbsp;7, the algorithm is formulated for integers, whereas in Book&nbsp;10, it is formulated for lengths of line segments. (In modern usage, one would say it was formulated there for [[real number]]s. But lengths, areas, and volumes, represented as real numbers in modern usage, are not measured in the same units and there is no natural unit of length, area, or volume; the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengths {{math|''a''}} and {{math|''b''}} corresponds to the greatest length {{math|''g''}} that measures {{math|''a''}} and {{math|''b''}} evenly; in other words, the lengths {{math|''a''}} and {{math|''b''}} are both integer multiples of the length {{math|''g''}}.

The algorithm was probably not discovered by [[Euclid]], who compiled results from earlier mathematicians in his ''Elements''.<ref name="Weil_1983">{{cite book | author-link = André Weil|last=Weil|first=A. | year = 1983 | title = Number Theory | publisher = Birkhäuser | location = Boston | isbn = 0-8176-3141-0 | pages = 4–6}}</ref><ref name="Jones_1994">{{cite book | last = Jones|first= A. | year = 1994 | chapter = Greek mathematics to AD 300 | title = Companion encyclopedia of the history and philosophy of the mathematical sciences | publisher = Routledge | location = New York | isbn = 0-415-09238-8 | pages = 46–48}}</ref> The mathematician and historian [[Bartel Leendert van der Waerden|B. L. van der Waerden]] suggests that Book VII derives from a textbook on [[number theory]] written by mathematicians in the school of [[Pythagoras]].<ref name="van_der_Waerden_1954">{{cite book | author-link = Bartel Leendert van der Waerden|last=van der Waerden|first= B. L. | year = 1954 | title = Science Awakening | url = https://archive.org/details/scienceawakening00waer| url-access = registration| series = translated by Arnold Dresden | publisher = P. Noordhoff Ltd | location = Groningen | pages = [https://archive.org/details/scienceawakening00waer/page/114 114–115]}}</ref> The algorithm was probably known by [[Eudoxus of Cnidus]] (about 375 BC).<ref name="Knuth, p. 318"/><ref>{{cite journal | last = von Fritz|first= K. | year = 1945 | title = The Discovery of Incommensurability by Hippasus of Metapontum | journal = Annals of Mathematics | volume = 46 | pages = 242–264 | doi = 10.2307/1969021 | jstor = 1969021 | issue = 2}}</ref> The algorithm may even pre-date Eudoxus,<ref>{{cite book | author-link = T. L. Heath | last = Heath |first = T. L. | year = 1949 | title = Mathematics in Aristotle | url = https://archive.org/details/mathematicsinari0000heat | url-access = registration | publisher = Oxford Press | pages = [https://archive.org/details/mathematicsinari0000heat/page/80 80–83]}}</ref><ref>{{cite book | author-link = David Fowler (mathematician)|last=Fowler|first=D. H. | year = 1987 | title = The Mathematics of Plato's Academy: A New Reconstruction | publisher = Oxford University Press | location = Oxford | isbn = 0-19-853912-6 | pages = 31–66}}</ref> judging from the use of the technical term ἀνθυφαίρεσις (''anthyphairesis'', reciprocal subtraction) in works by Euclid and [[Aristotle]].<ref>{{cite journal | last = Becker | first = O. | year = 1933 | title = Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid | volume = 2 | pages = 311–333 | journal = Quellen und Studien zur Geschichte der Mathematik B}}</ref> Claude Brezinski, following remarks by [[Pappus of Alexandria]], credits the algorithm to [[Theaetetus (mathematician)|Theaetetus]] (c. 417 – c. 369 BC).<ref>{{cite book
 | last = Brezinski | first = Claude
 | doi = 10.1007/978-3-642-58169-4
 | isbn = 3-540-15286-5
 | mr = 1083352
 | page = [https://books.google.com/books?id=rxzsCAAAQBAJ&pg=PA6 6]
 | publisher = Springer-Verlag, Berlin
 | series = Springer Series in Computational Mathematics
 | title = History of continued fractions and Padé approximants
 | volume = 12
 | year = 1991
}}</ref>

Centuries later, Euclid's algorithm was discovered independently both in India and in China,<ref name="Stillwell, p. 31">{{Harvnb|Stillwell|1997|p=31}}</ref> primarily to solve [[Diophantine equation]]s that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomer [[Aryabhata]] described the algorithm as the "pulverizer",<ref name="Tattersall, p. 70">{{Harvnb|Tattersall|2005|p=70}}</ref> perhaps because of its effectiveness in solving Diophantine equations.<ref>{{Harvnb|Rosen|2000|pp=86–87}}</ref> Although a special case of the [[Chinese remainder theorem]] had already been described in the Chinese book ''[[Sunzi Suanjing]]'',<ref>{{Harvnb|Ore|1948|pp=247–248}}</ref> the general solution was published by [[Qin Jiushao]] in his 1247 book ''Shushu Jiuzhang'' (數書九章 ''[[Mathematical Treatise in Nine Sections]]'').<ref>{{Harvnb|Tattersall|2005|pp=72, 184–185}}</ref> The Euclidean algorithm was first described ''numerically'' and popularized in Europe in the second edition of [[Claude Gaspard Bachet de Méziriac|Bachet's]] ''Problèmes plaisants et délectables'' (''Pleasant and enjoyable problems'', 1624).<ref name="Tattersall, p. 70"/> In Europe, it was likewise used to solve Diophantine equations and in developing [[simple continued fraction|continued fraction]]s. The [[extended Euclidean algorithm]] was published by the English mathematician [[Nicholas Saunderson]],<ref>{{cite book|last1=Saunderson|first1=Nicholas|title=The Elements of Algebra in Ten Books|date=1740|publisher=University of Cambridge Press|url=http://www.e-rara.ch/zut/content/structure/2440626|access-date=1 November 2016}}</ref> who attributed it to [[Roger Cotes]] as a method for computing continued fractions efficiently.<ref>{{Harvnb|Tattersall|2005|pp=72–76}}</ref>

In the 19th century, the Euclidean algorithm led to the development of new number systems, such as [[Gaussian integer]]s and [[Eisenstein integer]]s. In 1815, [[Carl Friedrich Gauss|Carl Gauss]] used the Euclidean algorithm to demonstrate unique factorization of [[Gaussian integer]]s, although his work was first published in 1832.<ref name="Gauss_1832" /> Gauss mentioned the algorithm in his ''[[Disquisitiones Arithmeticae]]'' (published 1801), but only as a method for [[continued fraction]]s.<ref name="Stillwell, p. 31"/> [[Peter Gustav Lejeune Dirichlet]] seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory.<ref>{{Harvnb|Stillwell|1997|pp=31–32}}</ref> Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied.<ref>{{Harvnb|Lejeune Dirichlet|1894|pp=29–31}}</ref> Lejeune Dirichlet's lectures on number theory were edited and extended by [[Richard Dedekind]], who used Euclid's algorithm to study [[algebraic integer]]s, a new general type of number. For example, Dedekind was the first to prove [[Fermat's theorem on sums of two squares|Fermat's two-square theorem]] using the unique factorization of Gaussian integers.<ref>[[Richard Dedekind]] in {{Harvnb|Lejeune Dirichlet|1894|loc=Supplement XI}}</ref> Dedekind also defined the concept of a [[Euclidean domain]], a number system in which a generalized version of the Euclidean algorithm can be defined (as described [[#Euclidean domains|below]]). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of [[ideal (ring theory)|ideals]].<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;" |
"[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day."
|-
| style="text-align: left;" | [[Donald Knuth]], ''The Art of Computer Programming, Vol. 2: Seminumerical Algorithms'', 2nd edition (1981), p.&nbsp;318.
|}

Other applications of Euclid's algorithm were developed in the 19th century. In 1829, [[Jacques Charles François Sturm|Charles Sturm]] showed that the algorithm was useful in the [[Sturm's theorem|Sturm chain]] method for counting the real roots of polynomials in any given interval.<ref>{{cite journal | last = Sturm |first = C. | author-link = Jacques Charles François Sturm | year = 1829 | title = Mémoire sur la résolution des équations numériques |language=fr | journal = Bull. Des sciences de Férussac | volume = 11 | pages = 419–422}}</ref>

The Euclidean algorithm was the first [[integer relation algorithm]], which is a method for finding integer relations between commensurate real numbers. Several novel [[integer relation algorithm]]s have been developed, such as the algorithm of [[Helaman Ferguson]] and R.W. Forcade (1979)<ref>
{{cite journal
 | last1 = Ferguson | first1 = H. R. P. | author1-link = Helaman Ferguson
 | last2 = Forcade | first2 = R. W.
 | doi = 10.1090/S0273-0979-1979-14691-3
 | issue = 6
 | journal = Bulletin of the American Mathematical Society
 | mr = 546316
 | pages = 912–914
 | series = New Series
 | title = Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two
 | volume = 1
 | year = 1979| doi-access = free
}}</ref> and the [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|LLL algorithm]].<ref>{{cite journal | last = Peterson |first = I. | date = 12 August 2002 | title = Jazzing Up Euclid's Algorithm | journal = ScienceNews | url=http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm}}</ref><ref>{{cite journal | last = Cipra | first = Barry Arthur |author-link=Barry Arthur Cipra | title = The Best of the 20th Century: Editors Name Top 10 Algorithms | journal = SIAM News | volume = 33 | date = 16 May 2000 | publisher = [[Society for Industrial and Applied Mathematics]] | issue = 4 | url = https://www.siam.org/pdf/news/637.pdf | access-date = 19 July 2016 | archive-url = https://web.archive.org/web/20160922144038/https://www.siam.org/pdf/news/637.pdf | archive-date = 22 September 2016 | url-status = dead | df = dmy-all }}</ref>

In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called ''The Game of Euclid'',<ref>{{cite journal | 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 | journal = Math. Gaz. | volume = 53 | pages = 354–357 | doi = 10.2307/3612461 | jstor = 3612461 | issue = 386| s2cid = 125164797 }}</ref> which has an optimal strategy.<ref>{{cite journal | doi = 10.2307/2689037 | last = Spitznagel | first = E. L. | year = 1973 | title = Properties of a game based on Euclid's algorithm | jstor = 2689037 | journal = Math. Mag. | volume = 46 | issue = 2 | pages = 87–92}}</ref> The players begin with two piles of {{math|''a''}} and {{math|''b''}} stones. The players take turns removing {{math|''m''}} multiples of the smaller pile from the larger. Thus, if the two piles consist of {{math|''x''}} and {{math|''y''}} stones, where {{math|''x''}} is larger than {{math|''y''}}, the next player can reduce the larger pile from {{math|''x''}} stones to {{math|''x'' − ''my''}} stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.<ref>{{Harvnb|Rosen|2000|p=95}}</ref><ref>{{cite book | last = Roberts | first = J. | year = 1977 | title = Elementary Number Theory: A Problem Oriented Approach | publisher = [[MIT Press]] | location = Cambridge, MA | isbn = 0-262-68028-9 | pages = [https://archive.org/details/Elementary_00_Robe/page/1 1–8] | url = https://archive.org/details/Elementary_00_Robe/page/1 }}</ref>