Editing Euclidean algorithm (section)

=== Rational and real numbers ===
Euclid's algorithm can be applied to [[real number]]s, as described by Euclid in Book 10 of his ''[[Euclid's Elements|Elements]]''. The goal of the algorithm is to identify a real number {{mvar|g}} such that two given real numbers, {{mvar|a}} and {{mvar|b}}, are integer multiples of it: {{math|1=''a'' = ''mg''}} and {{math|1=''b'' = ''ng''}}, where {{mvar|m}} and {{mvar|n}} are [[integer]]s.<ref name="Weil_1983" /> This identification is equivalent to finding an [[integer relation algorithm|integer relation]] among the real numbers {{mvar|a}} and {{mvar|b}}; that is, it determines integers {{mvar|s}} and {{mvar|t}} such that {{math|1=''sa'' + ''tb'' = 0}}. If such an equation is possible, ''a'' and ''b'' are called commensurable lengths, otherwise they are [[Commensurability (mathematics)|incommensurable lengths]].<ref>{{cite book | last1 = Boyer | first1 = C. B. | last2 = Merzbach | first2 = U. C. | author2-link = Uta Merzbach | year = 1991 | title = A History of Mathematics | edition = 2nd | publisher = Wiley | location = New York | isbn = 0-471-54397-7 | pages = [https://archive.org/details/historyofmathema00boye/page/116 116–117] | url = https://archive.org/details/historyofmathema00boye/page/116 }}</ref><ref>{{cite book | author-link = Florian Cajori|last=Cajori|first= F | year = 1894 | title = A History of Mathematics | url = https://archive.org/details/in.ernet.dli.2015.73802| publisher = Macmillan | location = New York | page = [https://archive.org/details/in.ernet.dli.2015.73802/page/n78 70]}} Reprinted, Dover Publications, 2004, {{isbn|0-486-43874-0}}</ref>

The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders {{math|''r''<sub>''k''</sub>}} are real numbers, although the quotients {{math|''q''<sub>''k''</sub>}} are integers as before. Second, the algorithm is not guaranteed to end in a finite number {{mvar|N}} of steps. If it does, the fraction {{math|''a''/''b''}} is a rational number, i.e., the ratio of two integers
: <math>\frac{a}{b} = \frac{mg}{ng} = \frac{m}{n},</math>
and can be written as a finite continued fraction {{math|1=[''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, ..., ''q''<sub>''N''</sub>]}}. If the algorithm does not stop, the fraction {{math|''a''/''b''}} is an [[irrational number]] and can be described by an infinite continued fraction {{math|1=[''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …]}}.<ref>{{cite book|title=Algorithmic Cryptanalysis|first=Antoine|last=Joux|publisher=CRC Press|year=2009|isbn=9781420070033|url=https://books.google.com/books?id=buQajqt-_iUC&pg=PA33|page=33}}</ref> Examples of infinite continued fractions are the [[golden ratio]] {{math|1=''φ'' = [1; 1, 1, ...]}} and the [[square root of 2|square root of two]], {{math|1={{sqrt|2}} = [1; 2, 2, ...]}}.<ref>{{cite book|title=Mathematical Omnibus: Thirty Lectures on Classic Mathematics|first1=D. B.|last1=Fuks|first2=Serge|last2=Tabachnikov|author-link2=Sergei Tabachnikov|publisher=American Mathematical Society|year=2007|isbn=9780821843161|page=13|url=https://books.google.com/books?id=IiG9AwAAQBAJ&pg=PA13}}</ref> The algorithm is unlikely to stop, since [[almost all]] ratios {{math|''a''/''b''}} of two real numbers are irrational.<ref>{{cite book|title=The Universal Book of Mathematics: From Abracadabra to Zeno's Paradoxes|first=David|last=Darling|author-link=David J. Darling|publisher=John Wiley & Sons|year=2004|isbn=9780471667001|url=https://books.google.com/books?id=HrOxRdtYYaMC&pg=PA175|page=175|contribution=Khintchine's constant}}</ref>

An infinite continued fraction may be truncated at a step {{math|1=''k'' [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, ..., ''q''<sub>''k''</sub>]}} to yield an approximation to {{math|''a''/''b''}} that improves as {{mvar|k}} is increased. The approximation is described by [[Convergent (continued fraction)|convergents]] {{math|''m''<sub>''k''</sub>/''n''<sub>''k''</sub>}}; the numerator and denominators are coprime and obey the [[recurrence relation]]
: <math>\begin{align}
   m_k &= q_k m_{k-1} + m_{k-2} \\
   n_k &= q_k n_{k-1} + n_{k-2},
 \end{align}</math>
where {{math|1=''m''<sub>−1</sub> = ''n''<sub>−2</sub> = 1}} and {{math|1=''m''<sub>−2</sub> = ''n''<sub>−1</sub> = 0}} are the initial values of the recursion. The convergent {{math|''m''<sub>''k''</sub>/''n''<sub>''k''</sub>}} is the best [[rational number]] approximation to {{math|''a''/''b''}} with denominator {{math|''n''<sub>''k''</sub>}}:<ref>{{cite book|title=Explorations in Quantum Computing|first=Colin P.|last=Williams|publisher=Springer|year=2010|isbn=9781846288876|url=https://books.google.com/books?id=QE8S--WjIFwC&pg=PA277|pages=277–278}}</ref>
: <math> \left|\frac{a}{b} - \frac{m_k}{n_k}\right| < \frac{1}{n_k^2}.</math>