Editing Euclidean algorithm (section)

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