Editing Euclidean algorithm (section)

== Mathematical applications ==

=== Bézout's identity ===
{{main|Bézout's identity}}
Bézout's identity states that the greatest common divisor {{math|''g''}} of two integers {{math|''a''}} and {{math|''b''}} can be represented as a linear sum of the original two numbers {{math|''a''}} and {{math|''b''}}.<ref>{{cite book | last1 = Jones |first1=G. A. | last2 = Jones | first2 = J. M. | year = 1998 | chapter = Bezout's Identity | title = Elementary Number Theory | publisher = Springer-Verlag | location = New York | pages = 7–11}}</ref> In other words, it is always possible to find integers {{math|''s''}} and {{math|''t''}} such that {{math|1=''g'' = ''sa'' + ''tb''}}.<ref>{{Harvnb|Rosen|2000|p=81}}</ref><ref>{{Harvnb|Cohn|1980|p=104}}</ref>

The integers {{math|''s''}} and {{math|''t''}} can be calculated from the quotients {{math|''q''<sub>0</sub>}}, {{math|''q''<sub>1</sub>}}, etc. by reversing the order of equations in Euclid's algorithm.<ref>{{Harvnb|Rosen|2000|p=91}}</ref> Beginning with the next-to-last equation, {{math|''g''}} can be expressed in terms of the quotient {{math|''q''<sub>''N''−1</sub>}} and the two preceding remainders, {{math|''r''<sub>''N''−2</sub>}} and {{math|''r''<sub>''N''−3</sub>}}:
: {{math|1=''g'' = ''r''<sub>''N''−1</sub> = ''r''<sub>''N''−3</sub> − ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub>}}.

Those two remainders can be likewise expressed in terms of their quotients and preceding remainders,
: {{math|1=''r''<sub>''N''−2</sub> = ''r''<sub>''N''−4</sub> − ''q''<sub>''N''−2</sub> ''r''<sub>''N''−3</sub>}} and
: {{math|1=''r''<sub>''N''−3</sub> = ''r''<sub>''N''−5</sub> − ''q''<sub>''N''−3</sub> ''r''<sub>''N''−4</sub>}}.

Substituting these formulae for {{math|''r''<sub>''N''−2</sub>}} and {{math|''r''<sub>''N''−3</sub>}} into the first equation yields {{math|''g''}} as a linear sum of the remainders {{math|''r''<sub>''N''−4</sub>}} and {{math|''r''<sub>''N''−5</sub>}}. The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers {{math|''a''}} and {{math|''b''}} are reached:
: {{math|1=''r''<sub>2</sub> = ''r''<sub>0</sub> − ''q''<sub>2</sub> ''r''<sub>1</sub>}}
: {{math|1=''r''<sub>1</sub> = ''b'' − ''q''<sub>1</sub> ''r''<sub>0</sub>}}
: {{math|1=''r''<sub>0</sub> = ''a'' − ''q''<sub>0</sub> ''b''}}.

After all the remainders {{math|''r''<sub>0</sub>}}, {{math|''r''<sub>1</sub>}}, etc. have been substituted, the final equation expresses {{math|''g''}} as a linear sum of {{math|''a''}} and {{math|''b''}}, so that {{math|1=''g'' = ''sa'' + ''tb''}}.

The Euclidean algorithm, and thus Bézout's identity, can be generalized to the context of [[Euclidean domain]]s.

=== Principal ideals and related problems ===
Bézout's identity provides yet another definition of the greatest common divisor {{math|''g''}} of two numbers {{math|''a''}} and {{math|''b''}}.<ref name="Leveque_p33" >{{Harvnb|LeVeque|1996|p=33}}</ref> Consider the set of all numbers {{math|''ua'' + ''vb''}}, where {{math|''u''}} and {{math|''v''}} are any two integers. Since {{math|''a''}} and {{math|''b''}} are both divisible by {{math|''g''}}, every number in the set is divisible by {{math|''g''}}. In other words, every number of the set is an integer multiple of {{math|''g''}}. This is true for every common divisor of {{math|''a''}} and {{math|''b''}}. However, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosing {{math|1=''u'' = ''s''}} and {{math|1=''v'' = ''t''}} gives {{math|''g''}}. A smaller common divisor cannot be a member of the set, since every member of the set must be divisible by {{math|''g''}}. Conversely, any multiple {{math|''m''}} of {{math|''g''}} can be obtained by choosing {{math|1=''u'' = ''ms''}} and {{math|1=''v'' = ''mt''}}, where {{math|''s''}} and {{math|''t''}} are the integers of Bézout's identity. This may be seen by multiplying Bézout's identity by ''m'',
: {{math|1=''mg'' = ''msa'' + ''mtb''}}.

Therefore, the set of all numbers {{math|''ua'' + ''vb''}} is equivalent to the set of multiples {{math|''m''}} of {{math|''g''}}. In other words, the set of all possible sums of integer multiples of two numbers ({{math|''a''}} and {{math|''b''}}) is equivalent to the set of multiples of {{math|gcd(''a'', ''b'')}}. The GCD is said to be the generator of the [[ideal (ring theory)|ideal]] of {{math|''a''}} and {{math|''b''}}. This GCD definition led to the modern [[abstract algebra]]ic concepts of a [[principal ideal]] (an ideal generated by a single element) and a [[principal ideal domain]] (a [[domain (ring theory)|domain]] in which every ideal is a principal ideal).

Certain problems can be solved using this result.<ref>{{Harvnb|Schroeder|2005|p=23}}</ref> For example, consider two measuring cups of volume {{math|''a''}} and {{math|''b''}}. By adding/subtracting {{math|''u''}} multiples of the first cup and {{math|''v''}} multiples of the second cup, any volume {{math|''ua'' + ''vb''}} can be measured out. These volumes are all multiples of {{math|1=''g'' = gcd(''a'', ''b'')}}.

=== Extended Euclidean algorithm ===
{{Main|Extended Euclidean algorithm}}

The integers {{math|''s''}} and {{math|''t''}} of Bézout's identity can be computed efficiently using the [[extended Euclidean algorithm]]. This extension adds two recursive equations to Euclid's algorithm<ref>{{Harvnb|Rosen|2000|pp=90–93}}</ref>
: {{math|1=''s''<sub>''k''</sub> = ''s''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''s''<sub>''k''−1</sub>}}
: {{math|1=''t''<sub>''k''</sub> = ''t''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''t''<sub>''k''−1</sub>}}
with the starting values
: {{math|1=''s''<sub>−2</sub> = 1, ''t''<sub>−2</sub> = 0}}
: {{math|1=''s''<sub>−1</sub> = 0, ''t''<sub>−1</sub> = 1}}.

Using this recursion, Bézout's integers {{math|''s''}} and {{math|''t''}} are given by {{math|1=''s'' = ''s''<sub>''N''</sub>}} and {{math|1=''t'' = ''t''<sub>''N''</sub>}}, where {{math|''N'' + 1}} is the step on which the algorithm terminates with {{math|1=''r''<sub>''N''+1</sub> = 0}}.

The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to step {{math|''k'' − 1}} of the algorithm; in other words, assume that
: {{math|1=''r''<sub>''j''</sub> = ''s''<sub>''j''</sub> ''a'' + ''t''<sub>''j''</sub> ''b''}}
for all {{math|''j''}} less than {{math|''k''}}. The {{math|''k''}}th step of the algorithm gives the equation
: {{math|1=''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''r''<sub>''k''−1</sub>}}.

Since the recursion formula has been assumed to be correct for {{math|''r''<sub>''k''−2</sub>}} and {{math|''r''<sub>''k''−1</sub>}}, they may be expressed in terms of the corresponding {{math|''s''}} and {{math|''t''}} variables
: {{math|1=''r''<sub>''k''</sub> = (''s''<sub>''k''−2</sub> ''a'' + ''t''<sub>''k''−2</sub> ''b'') − ''q''<sub>''k''</sub>(''s''<sub>''k''−1</sub> ''a'' + ''t''<sub>''k''−1</sub> ''b'')}}.

Rearranging this equation yields the recursion formula for step {{math|''k''}}, as required
: {{math|1=''r''<sub>''k''</sub> = ''s''<sub>''k''</sub> ''a'' + ''t''<sub>''k''</sub> ''b'' = (''s''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''s''<sub>''k''−1</sub>) ''a'' + (''t''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''t''<sub>''k''−1</sub>) ''b''}}.

=== Matrix method ===

The integers {{math|''s''}} and {{math|''t''}} can also be found using an equivalent [[matrix (mathematics)|matrix]] method.<ref name="Koshy_2002">{{cite book | last = Koshy | first = T. | year = 2002 | title = Elementary Number Theory with Applications | publisher = Harcourt/Academic Press | location = Burlington, MA | isbn = 0-12-421171-2 | pages = 167–169}}</ref> The sequence of equations of Euclid's algorithm
: <math>
\begin{align}
a & = q_0 b + r_0 \\
b & = q_1 r_0 + r_1 \\
& \,\,\,\vdots \\
r_{N-2} & = q_N r_{N-1} + 0
\end{align}
</math>
can be written as a product of {{math|2×2}} quotient matrices multiplying a two-dimensional remainder vector
<!--  :<math alt="A series of equations consisting of two-dimensional vectors multiplied by an ever-increasing number of 2×2 matrices. The vector a b equals the matrix q sub zero 1 1 0 times the vector b r sub zero. It also equals the matrix q sub zero 1 1 0 times the matrix q sub one 1 1 0 times the vector r sub zero r sub one. Continuing to the last step N of the algorithm, it equals the product of all 2×2 matrices of the form q sub i 1 1 0 times the vector r sub N minus one r sub N. The index i ranges from 0 to N and the last remainder r sub N is zero."> -->
: <math>
\begin{pmatrix} a \\ b \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_0 \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \end{pmatrix} =
\cdots =
\prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} \,.
</math>

Let {{math|'''M'''}} represent the product of all the quotient matrices
<!--:<math alt="The 2×2 matrix M has four components, m sub 1 1, m sub 1 2, m sub 2 1, and m sub 2 2. It is defined as the product of all 2×2 matrices of the form q sub i 1 1 0, where the index i ranges from 0 to N.">  -->
: <math>
\mathbf{M} = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} =
\prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} q_{N} & 1 \\ 1 & 0 \end{pmatrix} \,.
</math>

This simplifies the Euclidean algorithm to the form
<!-- alt="The two-dimensional vector a b equals the matrix M times the final vector, r sub N minus one zero. The final non-zero remainder is the greatest common divisor g. Therefore, the vector a b equals the matrix M times the vector g zero."> -->
: <math> 
\begin{pmatrix} a \\ b \end{pmatrix} =
\mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} =
\mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix} \,.
</math>

To express {{math|''g''}} as a linear sum of {{math|''a''}} and {{math|''b''}}, both sides of this equation can be multiplied by the [[invertible matrix|inverse]] of the matrix {{math|'''M'''}}.<ref name="Koshy_2002" /><ref name="Bach_1996">{{cite book | last1 = Bach | first1 = E. | author1-link = Eric Bach | last2= Shallit | first2 = J. | author2-link = Jeffrey Shallit | year = 1996 | title = Algorithmic number theory | publisher = MIT Press | location = Cambridge, MA | isbn = 0-262-02405-5 | pages = 70–73}}</ref> The [[determinant]] of {{math|'''M'''}} equals {{math|(−1)<sup>''N''+1</sup>}}, since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant of {{math|'''M'''}} is never zero, the vector of the final remainders can be solved using the inverse of {{math|'''M'''}}
<!--  :<math alt="The two-dimensional vector g 0 equals the inverse of matrix M times the vector a b. This equals minus one to the Nth plus one power, times the matrix with components m sub 2 2, minus m sub 1 2, minus m sub 2 1, and m sub 1 1, times the vector a b.">-->
: <math>
\begin{pmatrix} g \\ 0 \end{pmatrix} =
\mathbf{M}^{-1} \begin{pmatrix} a \\ b \end{pmatrix} =
(-1)^{N+1} \begin{pmatrix} m_{22} & -m_{12} \\ -m_{21} & m_{11} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} \,.
</math>

Since the top equation gives
: {{math|1=''g'' = (−1)<sup>''N''+1</sup> ( ''m''<sub>22</sub> ''a'' − ''m''<sub>12</sub> ''b'')}},
the two integers of Bézout's identity are {{math|1=''s'' = (−1)<sup>''N''+1</sup>''m''<sub>22</sub>}} and {{math|1=''t'' = (−1)<sup>''N''</sup>''m''<sub>12</sub>}}. The matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.

=== Euclid's lemma and unique factorization ===
Bézout's identity is essential to many applications of Euclid's algorithm, such as demonstrating the [[Fundamental theorem of arithmetic|unique factorization]] of numbers into prime factors.<ref>{{Harvnb|Stark|1978|pp=26–36}}</ref> To illustrate this, suppose that a number {{math|''L''}} can be written as a product of two factors {{math|''u''}} and {{math|''v''}}, that is, {{math|1=''L'' = ''uv''}}. If another number {{math|''w''}} also divides {{math|''L''}} but is coprime with {{math|''u''}}, then {{math|''w''}} must divide {{math|''v''}}, by the following argument: If the greatest common divisor of {{math|''u''}} and {{math|''w''}} is {{math|1}}, then integers {{math|''s''}} and {{math|''t''}} can be found such that
: {{math|1=1 = ''su'' + ''tw''}}
by Bézout's identity. Multiplying both sides by {{math|''v''}} gives the relation:
: {{math|1=''v'' = ''suv'' + ''twv'' = ''sL'' + ''twv''}}

Since {{math|''w''}} divides both terms on the right-hand side, it must also divide the left-hand side, {{math|''v''}}. This result is known as [[Euclid's lemma]].<ref name="Ore, p. 44">{{Harvnb|Ore|1948|p=44}}</ref> Specifically, if a prime number divides {{math|''L''}}, then it must divide at least one factor of {{math|''L''}}. Conversely, if a number {{math|''w''}} is coprime to each of a series of numbers {{math|''a''<sub>1</sub>}}, {{math|''a''<sub>2</sub>}}, ..., {{math|''a''<sub>''n''</sub>}}, then {{math|''w''}} is also coprime to their product, {{math|''a''<sub>1</sub> × ''a''<sub>2</sub> × ... × ''a''<sub>''n''</sub>}}.<ref name="Ore, p. 44"/>

Euclid's lemma suffices to prove that every number has a unique factorization into prime numbers.<ref>{{Harvnb|Stark|1978|pp=281–292}}</ref> To see this, assume the contrary, that there are two independent factorizations of {{math|''L''}} into {{math|''m''}} and {{math|''n''}} prime factors, respectively
: {{math|1=''L'' = ''p''<sub>1</sub>''p''<sub>2</sub>...''p''<sub>''m''</sub> = ''q''<sub>1</sub>''q''<sub>2</sub>...''q''<sub>''n''</sub>&nbsp;}}.

Since each prime {{math|''p''}} divides {{math|''L''}} by assumption, it must also divide one of the {{math|''q''}} factors; since each {{math|''q''}} is prime as well, it must be that {{math|1=''p'' = ''q''}}. Iteratively dividing by the {{math|''p''}} factors shows that each {{math|''p''}} has an equal counterpart {{math|''q''}}; the two prime factorizations are identical except for their order. The unique factorization of numbers into primes has many applications in mathematical proofs, as shown below.

=== Linear Diophantine equations ===
[[File:Diophante Bezout.svg|thumb|alt="A diagonal line running from the upper left corner to the lower right. Fifteen circles are spaced at regular intervals along the line. Perpendicular x-y coordinate axes have their origin in the lower left corner; the line crossed the y-axis at the upper left and crosse the x-axis at the lower right."|Plot of a linear [[Diophantine equation]], {{math|1=9''x'' + 12''y'' = 483}}. The solutions are shown as blue circles.]]

[[Diophantine equation]]s are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematician [[Diophantus]].<ref>{{Harvnb|Rosen|2000|pp=119–125}}</ref> A typical ''linear'' Diophantine equation seeks integers {{math|''x''}} and {{math|''y''}} such that<ref>{{Harvnb|Schroeder|2005|pp=106–107}}</ref>
: {{math|1=''ax'' + ''by'' = ''c''}}
where {{math|''a''}}, {{math|''b''}} and {{math|''c''}} are given integers. This can be written as an equation for {{math|''x''}} in [[modular arithmetic]]:
: {{math|1=''ax'' &equiv; ''c'' mod ''b''}}.

Let {{math|''g''}} be the greatest common divisor of {{math|''a''}} and {{math|''b''}}. Both terms in {{math|''ax'' + ''by''}} are divisible by {{math|''g''}}; therefore, {{math|''c''}} must also be divisible by {{math|''g''}}, or the equation has no solutions. By dividing both sides by {{math|''c''/''g''}}, the equation can be reduced to Bezout's identity
: {{math|1=''sa'' + ''tb'' = ''g''}},
where {{math|''s''}} and {{math|''t''}} can be found by the [[extended Euclidean algorithm]].<ref>{{Harvnb|Schroeder|2005|pp=108–109}}</ref> This provides one solution to the Diophantine equation, {{math|1=''x''<sub>1</sub> = ''s'' (''c''/''g'')}} and {{math|1=''y''<sub>1</sub> = ''t'' (''c''/''g'')}}.

In general, a linear Diophantine equation has no solutions, or an infinite number of solutions.<ref>{{Harvnb|Rosen|2000|pp=120–121}}</ref> To find the latter, consider two solutions, {{math|(''x''<sub>1</sub>, ''y''<sub>1</sub>)}} and {{math|(''x''<sub>2</sub>, ''y''<sub>2</sub>)}}, where
: {{math|1=''ax''<sub>1</sub> + ''by''<sub>1</sub> = ''c'' = ''ax''<sub>2</sub> + ''by''<sub>2</sub>}}
or equivalently
: {{math|1=''a''(''x''<sub>1</sub> − ''x''<sub>2</sub>) = ''b''(''y''<sub>2</sub> − ''y''<sub>1</sub>)}}.

Therefore, the smallest difference between two {{math|''x''}} solutions is {{math|''b''/''g''}}, whereas the smallest difference between two {{math|''y''}} solutions is {{math|''a''/''g''}}. Thus, the solutions may be expressed as
: {{math|1=''x'' = ''x''<sub>1</sub> − ''bu''/''g''}}
: {{math|1=''y'' = ''y''<sub>1</sub> + ''au''/''g''}}.

By allowing {{math|''u''}} to vary over all possible integers, an infinite family of solutions can be generated from a single solution {{math|(''x''<sub>1</sub>, ''y''<sub>1</sub>)}}. If the solutions are required to be ''positive'' integers {{math|(''x'' > 0, ''y'' > 0)}}, only a finite number of solutions may be possible. This restriction on the acceptable solutions allows some systems of Diophantine equations with more unknowns than equations to have a finite number of solutions;<ref>{{Harvnb|Stark|1978|p=47}}</ref> this is impossible for a [[system of linear equations]] when the solutions can be any [[real number]] (see [[Underdetermined system]]).

=== Multiplicative inverses and the RSA algorithm ===
A [[finite field]] is a set of numbers with four generalized operations. The operations are called addition, subtraction, multiplication and division and have their usual properties, such as [[commutativity]], [[associativity]] and [[distributivity]]. An example of a finite field is the set of 13 numbers {{math|{{mset|0,&nbsp;1,&nbsp;2,&nbsp;...,&nbsp;12}}}} using [[modular arithmetic]]. In this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced [[modulo operation|modulo]] {{math|13}}; that is, multiples of {{math|13}} are added or subtracted until the result is brought within the range {{math|0}}–{{math|12}}. For example, the result of {{math|1=5 × 7 = 35 mod 13 = 9}}. Such finite fields can be defined for any prime {{math|''p''}}; using more sophisticated definitions, they can also be defined for any power {{math|''m''}} of a prime {{math|''p''<sup>''m''</sup>}}. Finite fields are often called [[Évariste Galois|Galois]] fields, and are abbreviated as {{math|GF(''p'')}} or {{math|GF(''p''<sup>''m''</sup>}}).

In such a field with {{math|''m''}} numbers, every nonzero element {{math|''a''}} has a unique [[modular multiplicative inverse]], {{math|''a''<sup>−1</sup>}} such that {{math|1=''aa''<sup>−1</sup> = ''a''<sup>−1</sup>''a'' ≡ 1 mod ''m''}}. This inverse can be found by solving the congruence equation {{math|''ax'' ≡ 1 mod ''m''}},<ref>{{Harvnb|Schroeder|2005|pp=107–109}}</ref> or the equivalent linear Diophantine equation<ref>{{Harvnb|Stillwell|1997|pp=186–187}}</ref>
: {{math|1=''ax'' + ''my'' = 1}}.

This equation can be solved by the Euclidean algorithm, as described [[#Linear Diophantine equations|above]]. Finding multiplicative inverses is an essential step in the [[RSA algorithm]], which is widely used in [[electronic commerce]]; specifically, the equation determines the integer used to decrypt the message.<ref>{{Harvnb|Schroeder|2005|p=134}}</ref> Although the RSA algorithm uses [[ring (mathematics)|rings]] rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists. The Euclidean algorithm also has other applications in [[error-correcting code]]s; for example, it can be used as an alternative to the [[Berlekamp–Massey algorithm]] for decoding [[BCH code|BCH]] and [[Reed–Solomon code]]s, which are based on Galois fields.<ref>{{cite book|title=Error Correction Coding: Mathematical Methods and Algorithms|page=266|first=T. K.|last=Moon|publisher=John Wiley and Sons|year=2005|isbn=0-471-64800-0}}</ref>

=== Chinese remainder theorem ===
Euclid's algorithm can also be used to solve multiple linear Diophantine equations.<ref>{{Harvnb|Rosen|2000|pp=143–170}}</ref> Such equations arise in the [[Chinese remainder theorem]], which describes a novel method to represent an integer ''x''. Instead of representing an integer by its digits, it may be represented by its remainders ''x''<sub>''i''</sub> modulo a set of ''N'' coprime numbers ''m''<sub>''i''</sub>:<ref>{{Harvnb|Schroeder|2005|pp=194–195}}</ref>
: <math>
\begin{align}
x_1 & \equiv x \pmod {m_1} \\
x_2 & \equiv x \pmod {m_2} \\
& \,\,\,\vdots \\
x_N & \equiv x \pmod {m_N} \,.
\end{align}
</math>

The goal is to determine ''x'' from its ''N'' remainders ''x''<sub>''i''</sub>. The solution is to combine the multiple equations into a single linear Diophantine equation with a much larger modulus ''M'' that is the product of all the individual moduli ''m''<sub>''i''</sub>, and define ''M''<sub>''i''</sub> as
: <math> M_i = \frac M {m_i}. </math>

Thus, each ''M''<sub>''i''</sub> is the product of all the moduli ''except'' ''m''<sub>''i''</sub>. The solution depends on finding ''N'' new numbers ''h''<sub>''i''</sub> such that
: <math> M_i h_i \equiv 1 \pmod {m_i} \,. </math>

With these numbers ''h''<sub>''i''</sub>, any integer ''x'' can be reconstructed from its remainders ''x''<sub>''i''</sub> by the equation
: <math> x \equiv (x_1 M_1 h_1 + x_2 M_2 h_2 + \cdots + x_N M_N h_N) \pmod M \,.</math>

Since these numbers ''h''<sub>''i''</sub> are the multiplicative inverses of the ''M''<sub>''i''</sub>, they may be found using Euclid's algorithm as described in the previous subsection.

=== Stern–Brocot tree ===
{{main|Stern–Brocot tree}}
The Euclidean algorithm can be used to arrange the set of all positive [[rational number]]s into an infinite [[binary search tree]], called the [[Stern–Brocot tree]].
The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other number ''a''/''b'' can be found by computing gcd(''a'',''b'') using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whether ''a''/''b'' is given in lowest terms, and forms a path from the root to a node containing the number ''a''/''b''.<ref>{{cite book|title=Concrete mathematics|page=123|author1-link=Ronald Graham|last1=Graham|first1=R.|author2-link=Donald Knuth|last2=Knuth|first2=D. E.|author3-link=Oren Patashnik|last3=Patashnik|first3=O.|publisher=Addison-Wesley|year=1989}}</ref> This fact can be used to prove that each positive rational number appears exactly once in this tree.

For example, 3/4 can be found by starting at the root, going to the left once, then to the right twice:
[[Image:SternBrocotTree.svg|thumb|400px|The Stern–Brocot tree, and the Stern–Brocot sequences of order ''i'' for ''i'' = 1, 2, 3, 4]]
: <math> 
\begin{align}
 & \gcd(3,4) & \leftarrow \\
= {} & \gcd(3,1) & \rightarrow \\
= {} & \gcd(2,1) & \rightarrow \\
= {} & \gcd(1,1).
\end{align}
</math>

The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the [[Calkin–Wilf tree]]. The difference is that the path is reversed: instead of producing a path from the root of the tree to a target, it produces a path from the target to the root.

=== Continued fractions ===
The Euclidean algorithm has a close relationship with [[continued fraction]]s.<ref name="Vinogradov_1954">{{cite book | author-link = Ivan Matveyevich Vinogradov | last=Vinogradov | first= I. M. | year = 1954 | title = Elements of Number Theory | url = https://archive.org/details/elementsofnumber0000vino | url-access = registration | publisher = Dover | location = New York | pages = [https://archive.org/details/elementsofnumber0000vino/page/3 3–13]}}</ref> The sequence of equations can be written in the form
: <math>
\begin{align}
\frac a b &= q_0 + \frac{r_0} b \\
\frac b {r_0} &= q_1 + \frac{r_1}{r_0} \\
\frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\
& \,\,\, \vdots \\
\frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\
& \,\,\,  \vdots \\
\frac{r_{N-2}}{r_{N-1}} &= q_N\,.
\end{align}
</math>

The last term on the right-hand side always equals the inverse of the left-hand side of the next equation. Thus, the first two equations may be combined to form
: <math>\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac{r_1}{r_0}} \,.</math>

The third equation may be used to substitute the denominator term ''r''<sub>1</sub>/''r''<sub>0</sub>, yielding
: <math>\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac 1 {q_2 + \cfrac{r_2}{r_1}}}\,. </math>

The final ratio of remainders ''r''<sub>''k''</sub>/''r''<sub>''k''−1</sub> can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction
: <math>\frac a b = q_0 + \cfrac 1 {q_1 + \cfrac 1 {q_2 + \cfrac{1}{\ddots + \cfrac 1 {q_N}}}} = [ q_0; q_1, q_2, \ldots , q_N ] \,.</math>

In the worked example [[#Worked example|above]], the gcd(1071, 462) was calculated, and the quotients ''q''<sub>''k''</sub> were 2, 3 and 7, respectively. Therefore, the fraction 1071/462 may be written
: <math>\frac{1071}{462} = 2 + \cfrac 1 {3 + \cfrac 1 7} = [2; 3, 7]</math>
as can be confirmed by calculation.

=== Factorization algorithms ===
Calculating a greatest common divisor is an essential step in several [[integer factorization]] algorithms,<ref>{{harvnb|Crandall|Pomerance|2001}}, pp.  225–349</ref> such as [[Pollard's rho algorithm]],<ref>{{harvnb|Knuth|1997}}, pp. 369–371</ref> [[Shor's algorithm]],<ref>{{cite journal | author-link = Peter Shor|last=Shor |first=P. W. | year = 1997 | title = Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer | journal = SIAM Journal on Scientific and Statistical Computing | volume = 26 |issue=5 | pages = 1484–1509 | doi=10.1137/s0097539795293172|arxiv=quant-ph/9508027 | bibcode = 1995quant.ph..8027S|s2cid=2337707 }}</ref> [[Dixon's factorization method]]<ref>{{cite journal | last = Dixon |first= J. D. | year = 1981 | title = Asymptotically fast factorization of integers | journal = Math. Comput. | volume = 36 | pages = 255–260 | doi = 10.2307/2007743 | jstor = 2007743 | issue = 153| doi-access = free }}</ref> and the [[Lenstra elliptic curve factorization]].<ref>{{cite journal | author-link = Hendrik Lenstra|last=Lenstra|first=H. W. Jr. | year = 1987 | title = Factoring integers with elliptic curves | journal = Annals of Mathematics | volume = 126 | pages = 649–673 | doi = 10.2307/1971363 | jstor = 1971363 | issue = 3| hdl = 1887/2140 | hdl-access = free }}</ref> The Euclidean algorithm may be used to find this GCD efficiently. [[Continued fraction factorization]] uses continued fractions, which are determined using Euclid's algorithm.<ref>{{harvnb|Knuth|1997}}, pp. 380–384</ref>