China Post 3: The Euclidean algorithm
by t0rajir0u, Jul 28, 2008, 1:45 PM
Part of this post is more "textbook" than the flavor of my latest entries, especially the part dealing with continued fractions. This is largely due to the fact that it seems to me that certain facts in the basic theory are not, I think, as well-known as they deserve to be. Part of this post also rambles a lot; I think this is the longest one to date.
The basic idea of the extended Euclidean algorithm on integers is extraordinarily simple, and yet it is one of the fundamental properties of the integers that allow for unique prime factorization and its existence in an arbitrary ring of integers is still the easiest way to prove unique prime factorization there. As we will see, it has even more interesting consequences (which we will illustrate by reformulating its statement five times!) but first we shall work through a large example. (In the rest of this post the Euclidean algorithm always refers to the relatively prime case, since the case that
are not relatively prime is in theory handled by dividing by
. In practice, the Euclidean algorithm itself is used to compute
, but we ignore this issue.)
Suppose we wanted to compute solutions to
. The Euclidean algorithm dictates that we repeatedly divide, obtain a remainder, and divide by that remainder, giving






.
The next step of the extended Euclidean algorithm is to substitute expressions for each of our remainders as follows:
$ \begin{eqnarray*} 1 &=& 6 - 1 \cdot 5 \\ &=& 6 - 1 \cdot (47 - 7 \cdot 6) \\ &=& 8 \cdot 6 - 1 \cdot 47 \\ &=& 8 \cdot (570 - 12 \cdot 47) - 1 \cdot 47 \\ &=& 8 \cdot 570 - 97 \cdot 47 \\ &=& 8 \cdot 570 - 97 \cdot (617 - 1 \cdot 570) \\ &=& 105 \cdot 570 - 97 \cdot 617 \\ &=& 105 \cdot (4889 - 7 \cdot 617) - 97 \cdot 617 \\ &=& 105 \cdot 4889 - 832 \cdot 617 \\ &=& 105 \cdot 4889 - 832 (15284 - 3 \cdot 4889) \\ &=& 2601 \cdot 4889 - 832 \cdot 15284 \\ \end{eqnarray*}$.
So why does this algorithm really work? One way of motivating the Euclidean algorithm is the question of finding multiplicative inverses modulo some
. The question of finding the multiplicative inverse of
is exactly the question of solving the linear Diophantine equation

.
For example, the above calculation demonstrates that the multiplicative inverse of
is
. We interpret the equation as the question of finding a multiplicative inverse by taking it
. But why restrict ourselves? As a concrete example, to find the inverse of
we solved
.
We recover the inverse by taking
. But to solve this equation suppose we take
instead. Then

and we are finding the inverse of
instead. Note that this is exactly the first step of the first half of the Euclidean algorithm! Thus one motivation of the Euclidean algorithm is that we reduce a modular problem
(of finding the inverse of
) to the modular problem
(of finding the inverse of
), which is "smaller," and once we have reduced enough we backtrack to get a solution to the original problem (which is the content of the second half of the algorithm).
Generalizations of the Euclidean algorithm lead to the notion of a Euclidean domain, but for now let's dispense with the abstract stuff and ask ourselves, say, an algorithmic question: can we bound the number of steps required to execute the Euclidean on
as a function of
and
? In fact, we can, and very easily so! A straightforward bound is implied by
Lamé's Theorem: The pair
is the "smallest" pair of numbers requiring
steps for the Euclidean algorithm to execute. (We have added an extra step to the Euclidean algorithm here for reasons to be explained later.)
And you thought I couldn't sneak the Fibonacci numbers into this one!
We defer the proof of the above result because we wish to place this result in the proper context (although it is somewhat intuitive). To do so it is necessary first to streamline the Euclidean algorithm. The fundamental step where we replace
with
can be broken down into the two steps

or
.
In running the algorithm we merely always keep the larger of the two numbers on the right until we get the ordered pair
(equivalently, we could stop at
or even at
). The advantage of working with these steps is that they can be easily represented by the matrices
![$ \mathbf{A} = \left[ \begin{array}{cc} 1 & -1 \\ 0 & 1 \end{array} \right]$](//latex.artofproblemsolving.com/0/7/2/0723d6a0274bce7910d55a2749ef4e43ca83cd25.png)
![$ \mathbf{J} = \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right]$](//latex.artofproblemsolving.com/5/c/5/5c529956659d02ee23fc0c29b2e9147f59d2180b.png)
(where we have identified the ordered pair
with the column matrix
for later convenience.) The Euclidean algorithm can then be formulated as follows.
Theorem (the Euclidean algorithm): Given two relatively prime integers
, there exists a unique finite sequence of natural numbers
such that
.
is precisely the sequence of quotients in the presentation of the Euclidean algorithm above. ("Unique" has to be understood in the proper sense because we can end the Euclidean algorithm in a few slightly different ways; we could choose to continue so that the last quotient is always
, for example, but this is not really necessary.)
It is then natural to ask what the nature of the matrix
is. The answer is also a direct consequence of the Euclidean algorithm. In particular, the following theorem occurs (with different notation) in the problem sets of 18.701 at MIT:
Theorem (the Euclidean algorithm, take 2): The special linear group
of integer matrices with determinant
is generated by
and
. (Note that
is its own inverse and transpose and that it has determinant
.)
Proof. The additional step necessary to execute the Euclidean algorithm on negative integers is
when
have opposite signs, which is just the matrix
.
is the step
, and it (and its inverse) can be taken as a replacement for the switching step (that is, depending on whichever of
is greater we subtract the smaller from the greater at each step). In other words, we now have four cases and four possible steps:
-
-
-
-
Now, given
(hence with
), repeatedly apply the four transformations above, as in the first theorem, to to
$ \mathbf{M} \left[ \begin{array}{c} 1 & 0 \end{array} \right] = \left[ \begin{array}{c} b & a \end{array} \right]$.
We get an expression of the form
$ (\text{Some As and Js}) \mathbf{M} \left[ \begin{array}{c} 1 & 0 \end{array} \right] = \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]$.
(Note that even without an explicit switching step
it is still possible to ensure that we end at
by running the algorithm until
is reached.)
is therefore a matrix with left column
. Because it still has determinant
(since
, and their inverses all have determinant
), its right column must be of the form
for some integer
. But this matrix is just
. Inverting gives the desired result.
Note that this is a slightly more general statement than the ordinary Euclidean algorithm because we have made no assumptions about the signs of the integers involved. The members of
generated by non-negative powers of
and
(where we take no inverses) form a semigroup, and these are the matrices that appear in our first formulation of the Euclidean algorithm. It is convenient at this point to adopt the notation
, in which case we can reword Take 1 into the following
Theorem (the Euclidean algorithm, take 3): Given relatively prime positive integers
, there exists a unique finite sequence of natural numbers
such that
.
Consequently,
is generated by
and
.
The use of the letter
was intentional -
is precisely the Fibonacci matrix! This observation leads to a quick and intuitive
Proof of Lamé's Theorem. In counting the number of steps in the Euclidean algorithm, we should be specific: we are counting the number of steps of the form
where
is the reduction of
. This is precisely the number of quotients
that occur in the process of running the Euclidean algorithm. We also need to be specific about what we mean by "size." Given two relatively prime integers
, simply define the size of the ordered pair to be
.
It is now straightforward that
strictly increases the size of a pair of relatively prime positive integers and
does nothing, and therefore that the smallest pair of relatively prime positive integers requiring
steps in the Euclidean algorithm is
![$ \left( \mathbf{F}_1 \right)^n \left[ \begin{array}{c} 1 \\ 0 \end{array} \right] = \left[ \begin{array}{c} F_{n+1} \\ F_n \end{array} \right]$](//latex.artofproblemsolving.com/7/9/5/795f0aa0897183eebd53e4cb6cb5015acbb66493.png)
exactly as desired. Beautiful!
There is a fascinating sense in which the Euclidean algorithm generalizes to irrational numbers. Suppose we interpreted the intermediate steps
in the Euclidean algorithm as points (particularly, lattice points) in the plane. When
are relatively prime (which is always the case here), we lose no information in identifying a point with its slope
. A linear transformation
(of the type we studied above) then becomes a fractional linear transformation (or Möbius transformation)
of the corresponding slope. A succinct description of the Euclidean algorithm is now possible as follows: one "step" in the Euclidean algorithm is the transformation

(where
is clearly the quotient in the division). The above discussion demonstrates that the set of fractional linear transformations satisfying
behaves under composition essentially like matrix multiplication. The group we get here is called the modular group
and the above discussion shows that it is isomorphic to
, the projective special linear group with integer coefficients (essentially
once we identify every transformation with its negative). The modular group is a rather fascinating group that shows up unexpectedly all over the place (this being one of those places!).
The transformation above is associated with the matrix
exactly as expected (since this is how we implemented the Euclidean algorithm). Here
corresponds to the subtraction step and
corresponds to the map
. The fractional linear transformation
(which has matrix
, again as expected) is the inverse map of the above; applying the Euclidean algorithm on
and then inverting each step gives

(where
), which we can write quite beautifully as
.
This is known as the (simple) continued fraction of
and is usually abbreviated
. For example, the continued fraction of
is
(precisely the sequence of quotients in the Euclidean algorithm). In other words, we have the following
Theorem (the Euclidean algorithm, take 4): Every rational number has a unique terminating continued fraction expansion.
(Again, unique has to be understood in the proper sense because
. The convention we are using, therefore, is that
.) Continued fraction representation is really exactly Take 3 of the theorems above once we identify
with
. Because of the way we defined fractional linear transformations, the point
at which we chose to end the algorithm is now essentially the point at infinity and corresponds to our use of
above. The definition of the convergents of
is now perhaps more natural. They are given by the slopes of the points corresponding to the vectors
.
Since the computation of successive convergents is just "inserted" multiplication by a matrix, it is also not suprising that the calculation of convergents can be done by recurrences known as the fundamental recurrence formulas (which have a very obvious interpretation in terms of matrix multiplication). Simply note that
![$ \mathbf{F}_{q_{k+1}} \left[ \begin{array}{c} 1 \\ 0 \end{array} \right] = \left[ \begin{array}{c} q_{k+1} \\ 1 \end{array} \right] \implies$](//latex.artofproblemsolving.com/7/b/7/7b73d4fecc71db1dbaf42391d3049ed32e24c39e.png)
.
Denoting the LHS by
, it is now immediate that

and that
; in other words, we have the identities


.
In particular, because the last convergent of a rational number is itself, the third identity tells us that the second-to-last convergent is the solution to
that we wanted in the first place! Thus the second-to-last convergent of
is
. These seemingly simple identities have other deep implications. Note, for example, their use in my solution to IMO 2008 #3. But first: now that we have recast the Euclidean algorithm in terms of the map
, we no longer have to restrict ourselves to rational
. The simple continued fraction of an irrational number
can be defined as the infinite result of applying the Euclidean algorithm. Perhaps the most beautiful example of such a fraction is

which satisfies
(and therefore
.) The convergents to
are therefore precisely the ratios of consecutive Fibonacci numbers
. (This is obvious from the matrix computation and from the recursions given above.) This provides an immediate proof of the identity
(which, as you'll recall, we proved by matrix methods alone before) and also an even more natural interpretation of Distinguishing Result 1: the number of steps required to run the Euclidean algorithm on a rational number
is the number of terms in its continued fraction representation, so to minimize the "size" (here a quantity known as height) of the corresponding fraction we want to make each term as small as possible, that is,
.
You may take some pleasure from the fact that after all of the effort that has been expended on this blog finding ways to express the Fibonacci numbers in terms of
we now have an extraordinary framework in which we found a way to express
in terms of the Fibonacci numbers.
The identities given above can be interpreted in terms of what is sometimes called the geometry of numbers. If a real number
has convergents
, the observation that
is really the observation that
,
which tells us that
and
are quite close together, and moreover that the sequence
is alternately increasing and decreasing. Since the absolute value of the first differences is strictly increasing it then follows that
is alternately above and below
(which is also straightforward by observing what happens when you delete and add terms "deep down" in a simple continued fraction). We interpret this as follows:
Draw the line
. The lattice points
are very close to each other and alternate between different sides of the line. Moreover, by Pick's theorem we conclude that the triangle
contains no lattice points. Any possible lattice points within the interior of the above triangle correspond to a point whose slope is closer to the value of
than
, but we now know that this does not occur. We are therefore led to the conclusion that
The convergents to a real number determine its best rational approximations.
As Practice Problem 2 shows, this has important implications for the solution of certain Diophantine equations. The observation that
is an extremely good approximation to
can therefore be explained by the fact that it is a convergent, and moreover, it turns out that the next quotient in the continued fraction is quite large (which means
). We can even estimate the error in the approximation:
,
so in other words, the error is approximately the square of the denominator, which is quite good, and if
is significantly larger than
it is a lot better. How much better this estimate can get in general is discussed in Practice Problem 3. In any case, if I have not convinced you of anything else you should note the power of Pick's Theorem, which is so mighty it is one of the lemmas used in a proof of quadratic reciprocity (but that's another story).
Note that the action of the elements of the modular group we described above takes each convergent to a better convergent which has "almost" the same slope - in other words, as lattice points the convergents (and therefore
) are "almost" eigenvectors. The actual eigenvectors of
correspond to the slopes
, a clear generalization of the situation with the Fibonacci sequence, where
is the exact eigenvector. Thus the action of repeated applications of
can be seen to be an expression of the principle of the dominant eigenvalue. Generally, the action of
for each of the quotients in a continued fraction expansion can be thought to "average" out in some sense to
. (It is perhaps less surprising, now, if I tell you that the quotients in the continued fraction of almost any real have the same geometric mean.)
This notion generalizes slightly as follows: if we take
for a fixed constant
, we obtain the sequence of rational functions

where
is the Fibonacci polynomial of order
. This is a straightforward generalization of Binet's formula; the recurrence that describes these polynomials is just
, with
.
Excursion: It turns out that
(by induction, for example), which gives in particular
, a rather beautiful identity begging for a combinatorial interpretation. Recalling that
counts the number of paths of length
that can be taken by steps of length
or
, this is reasonably straightforward: a path of length
with
steps of length
has
total steps, and given a set of
steps we pick
of them to "lengthen."
Now the general Fibonacci polynomial (for a positive integer
) can be understood as counting the number ways in which a
rectangle can be tiled by
tiles of
different colors and
tiles of one color (a situation where a recurrence can be written whose characteristic polynomial is precisely
), and the corresponding combinatorial proof is along exactly the same lines as above. This general situation can also be interpreted as the powers of the adjacency matrix of a graph on two variables in which a vertex
connects to a vertex
with
loops. We can also consider the situation where the
tiles are of
different colors (the general second-order recurrence), but this recurrence is not as easy to translate back into the language of simple continued fractions. (The appropriate generalization is the subject of Practice Problem 1.)
Back on topic, we would like to ask whether
is a "generalization" of the convergents to
. In other words,
Does there exist a function
such that
in an appropriate sense?
We might expect this function to be
. Since the two roots above are the roots of the polynomial
, the negative root has small absolute value (for real
) and so has negligible contribution to asymptotic behavior. Indeed, within this context the above calculation can be considered (at least for integer
) to be the process of simultaneously computing the continued fraction of a large class of rationals where, at each step, we remark that it is always the case that
. We might now ask whether this notion generalizes; in other words,
Does there exist a notion of continued fraction expansion for some large class of functions?
Rational functions have an obvious choice of terminating simple continued fraction given by the corresponding Euclidean algorithm on polynomials (although it is no longer true that substituting integers will get us a valid simple continued fraction of a rational number; some quotients may be negative). This is an interesting perspective: the Euclidean algorithm then allows one to decompose rational functions uniquely into the composition of fractional linear transformations of the form
for polynomial coefficients
. If the notion of "functional" continued fraction exists for polynomial quotients, rational functions will be its convergents. Part of the question we're asking, therefore, is the question of what class of functions can be appropriately approximated by sequences of rational functions.
This should remind you of the notion of a Taylor series, which essentially asks the question of what class of functions can be appropriately approximated by sequences of polynomials. Indeed, it is possible to ask the same kind of convergence questions for infinite continued fractions as it is for power series, although these questions are much harder to answer. (This appears to be a current area of active research.) A partial answer is provided by Euler's continued fraction formula, a rather beautiful identity which translates an infinite series into an infinite continued fraction and therefore allows a partial translation in the other direction, and it is here that I am, once again, out of details (although my hunch that hypergeometric functions are part of the answer appears to be correct.)
In closing, one application of the modular group is its use in verifying identities involving a fascinating set of functions called modular forms, which are functions that satisfy a "modular symmetry"; in other words, the modular group acts on them in a very specific way (as described in the article). This condition can be broken down into two conditions by looking at two generators of the modular group (which, we must stress, are not unique), and indeed this is the way a function is usually proven modular. A major application of this idea is to prove that two functions are identical by proving that they are both modular with the same value of
(called the weight of the function). Without getting into all that, ideas from the application of the modular group to complex analysis provide a proof of the Euclidean algorithm which is at once familiar and novel, and relies on the fact that the modular group has a natural group action on the upper half plane
(and in fact forms a subgroup of
, the full automorphism group of
).
First, we will need a few definitions. We say that
if there exists an element
of the modular group such that
. (Verify that this is an equivalence relation.) Let
denote the equivalence class of all such
for a particular
. Let
denote the fundamental domain in the upper half-plane.
Theorem (the Euclidean algorithm, take 5): For a given
, there exists either exactly one element of
in the interior of
or two elements of
on its boundary. Consequently, the modular group is generated by
and
.
The proof is left as an exercise. (Note that
is a translation and
is a reflection through the
-axis followed by an inversion about the circle immediately below
.) Suffice it to say that the sequence of steps that translates a complex number in
into
is the complex-numerical analogue of the Euclidean algorithm and implies that the values of a modular function are uniquely determined by its values in
. Therefore, if two modular functions of the same weight agree on
then they are identical. This seemingly straightforward principle leads to a number of highly nontrivial results, but this is also another story.
Practice Problem 0: Prove that
by expanding the Binet-like formula.
Practice Problem 1: Prove that a simple continued fraction is (eventually) periodic if and only if it is the real root of a quadratic polynomial with integer coefficients.
Practice Problem 2: Prove that if
is a solution to the Pell's equation
, then
is a convergent of
.
Practice Problem 3: What is the best constant
such that
for infinitely many convergents
of
, where
is an arbitrary irrational? (Hint: Look at
again. This result is closely related, in spirit, to Lamé's Theorem.)
Practice Problem 4: Prove Take 5.
The basic idea of the extended Euclidean algorithm on integers is extraordinarily simple, and yet it is one of the fundamental properties of the integers that allow for unique prime factorization and its existence in an arbitrary ring of integers is still the easiest way to prove unique prime factorization there. As we will see, it has even more interesting consequences (which we will illustrate by reformulating its statement five times!) but first we shall work through a large example. (In the rest of this post the Euclidean algorithm always refers to the relatively prime case, since the case that



Suppose we wanted to compute solutions to








The next step of the extended Euclidean algorithm is to substitute expressions for each of our remainders as follows:
$ \begin{eqnarray*} 1 &=& 6 - 1 \cdot 5 \\ &=& 6 - 1 \cdot (47 - 7 \cdot 6) \\ &=& 8 \cdot 6 - 1 \cdot 47 \\ &=& 8 \cdot (570 - 12 \cdot 47) - 1 \cdot 47 \\ &=& 8 \cdot 570 - 97 \cdot 47 \\ &=& 8 \cdot 570 - 97 \cdot (617 - 1 \cdot 570) \\ &=& 105 \cdot 570 - 97 \cdot 617 \\ &=& 105 \cdot (4889 - 7 \cdot 617) - 97 \cdot 617 \\ &=& 105 \cdot 4889 - 832 \cdot 617 \\ &=& 105 \cdot 4889 - 832 (15284 - 3 \cdot 4889) \\ &=& 2601 \cdot 4889 - 832 \cdot 15284 \\ \end{eqnarray*}$.
So why does this algorithm really work? One way of motivating the Euclidean algorithm is the question of finding multiplicative inverses modulo some




For example, the above calculation demonstrates that the multiplicative inverse of





We recover the inverse by taking



and we are finding the inverse of





Generalizations of the Euclidean algorithm lead to the notion of a Euclidean domain, but for now let's dispense with the abstract stuff and ask ourselves, say, an algorithmic question: can we bound the number of steps required to execute the Euclidean on



Lamé's Theorem: The pair


And you thought I couldn't sneak the Fibonacci numbers into this one!
We defer the proof of the above result because we wish to place this result in the proper context (although it is somewhat intuitive). To do so it is necessary first to streamline the Euclidean algorithm. The fundamental step where we replace



or

In running the algorithm we merely always keep the larger of the two numbers on the right until we get the ordered pair



![$ \mathbf{A} = \left[ \begin{array}{cc} 1 & -1 \\ 0 & 1 \end{array} \right]$](http://latex.artofproblemsolving.com/0/7/2/0723d6a0274bce7910d55a2749ef4e43ca83cd25.png)
![$ \mathbf{J} = \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right]$](http://latex.artofproblemsolving.com/5/c/5/5c529956659d02ee23fc0c29b2e9147f59d2180b.png)
(where we have identified the ordered pair

![$ \left[ \begin{array}{c} b \\ a \end{array} \right]$](http://latex.artofproblemsolving.com/e/4/c/e4cbb26555c9085fe0cff8086db4bf975e91a253.png)
Theorem (the Euclidean algorithm): Given two relatively prime integers


![$ \mathbf{J} \mathbf{A}^{q_n} ... \mathbf{J} \mathbf{A}^{q_0} \left[ \begin{array}{c} b \\ a \end{array} \right] = \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]$](http://latex.artofproblemsolving.com/6/e/4/6e478a603ee3eff5f86e30abdcca2bc933def984.png)


It is then natural to ask what the nature of the matrix

Theorem (the Euclidean algorithm, take 2): The special linear group






Proof. The additional step necessary to execute the Euclidean algorithm on negative integers is






-

-

-

-

Now, given
![$ \mathbf{M} = \left[ \begin{array}{cc} b & x \\ a & y \end{array} \right] \in SL_2(\mathbb{Z})$](http://latex.artofproblemsolving.com/0/9/e/09e56e59c8ddaed666c0820b6a4442d9c914f0e7.png)

$ \mathbf{M} \left[ \begin{array}{c} 1 & 0 \end{array} \right] = \left[ \begin{array}{c} b & a \end{array} \right]$.
We get an expression of the form
$ (\text{Some As and Js}) \mathbf{M} \left[ \begin{array}{c} 1 & 0 \end{array} \right] = \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]$.
(Note that even without an explicit switching step




![$ \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]$](http://latex.artofproblemsolving.com/1/6/f/16f46d1343e425c8bfb134a99e1a35b5bcf808db.png)



![$ \left[ \begin{array}{c} x' \\ 1 \end{array} \right]$](http://latex.artofproblemsolving.com/2/d/2/2d2473217a777e827804a7eeadb91925452f1ffd.png)


Note that this is a slightly more general statement than the ordinary Euclidean algorithm because we have made no assumptions about the signs of the integers involved. The members of



![$ \mathbf{F}_q = \mathbf{A}^{-q} \mathbf{J} = \left[ \begin{array}{cc} q & 1 \\ 1 & 0 \end{array} \right]$](http://latex.artofproblemsolving.com/b/1/3/b131b9f9a92a9c47893c33d7fc9e912fe7fd4d9d.png)
Theorem (the Euclidean algorithm, take 3): Given relatively prime positive integers


![$ \left[ \begin{array}{c} b \\ a \end{array} \right] = \mathbf{F}_{q_0} \mathbf{F}_{q_1} ... \mathbf{F}_{q_n} \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]$](http://latex.artofproblemsolving.com/f/c/5/fc5001a0dc72af67b3ea678bb54218fc2c36013d.png)
Consequently,



The use of the letter


Proof of Lamé's Theorem. In counting the number of steps in the Euclidean algorithm, we should be specific: we are counting the number of steps of the form






It is now straightforward that



![$ \left( \mathbf{F}_1 \right)^n \left[ \begin{array}{c} 1 \\ 0 \end{array} \right] = \left[ \begin{array}{c} F_{n+1} \\ F_n \end{array} \right]$](http://latex.artofproblemsolving.com/7/9/5/795f0aa0897183eebd53e4cb6cb5015acbb66493.png)
exactly as desired. Beautiful!
There is a fascinating sense in which the Euclidean algorithm generalizes to irrational numbers. Suppose we interpreted the intermediate steps






(where





The transformation above is associated with the matrix








(where


This is known as the (simple) continued fraction of

![$ [q_0 ; q_1, q_2, ... q_n]$](http://latex.artofproblemsolving.com/5/d/8/5d88d445b9ac7943c194f4c4dd6610ab4afa285f.png)

![$ [3; 7, 1, 12, 7, 1, 5]$](http://latex.artofproblemsolving.com/7/4/8/748b60df7b99b73d60e6394bef109eed9fd602f2.png)
Theorem (the Euclidean algorithm, take 4): Every rational number has a unique terminating continued fraction expansion.
(Again, unique has to be understood in the proper sense because
![$ [q_0 ; q_1, q_2, ... q_n] = [q_0 ; q_1, q_2, ... q_n - 1, 1]$](http://latex.artofproblemsolving.com/d/3/5/d3579fe419c898f30b898137bd012b50521761cd.png)






![$ \mathbf{p}_k = \left[ \begin{array}{c} r_k \\ s_k \end{array} \right] = \mathbf{F}_{q_0} \mathbf{F}_{q_1} ... \mathbf{F}_{q_k} \left[ \begin{array}{c} 1 \\ 0 \end{array} \right], k \le n$](http://latex.artofproblemsolving.com/2/9/b/29bac83692e1e1102b5a99e4a5ef882160a9d329.png)
Since the computation of successive convergents is just "inserted" multiplication by a matrix, it is also not suprising that the calculation of convergents can be done by recurrences known as the fundamental recurrence formulas (which have a very obvious interpretation in terms of matrix multiplication). Simply note that
![$ \mathbf{F}_{q_{k+1}} \left[ \begin{array}{c} 1 \\ 0 \end{array} \right] = \left[ \begin{array}{c} q_{k+1} \\ 1 \end{array} \right] \implies$](http://latex.artofproblemsolving.com/7/b/7/7b73d4fecc71db1dbaf42391d3049ed32e24c39e.png)
![$ \left[ \begin{array}{cc} r_{k+1} & r_k \\ s_{k+1} & s_k \end{array} \right] = \mathbf{F}_{q_0}... \mathbf{F}_{q_k} \mathbf{F}_{q_{k+1}}$](http://latex.artofproblemsolving.com/f/6/4/f64000178c28bb5db3014faf5e4b24b588fc1cfd.png)
Denoting the LHS by


and that




In particular, because the last convergent of a rational number is itself, the third identity tells us that the second-to-last convergent is the solution to







which satisfies







You may take some pleasure from the fact that after all of the effort that has been expended on this blog finding ways to express the Fibonacci numbers in terms of


The identities given above can be interpreted in terms of what is sometimes called the geometry of numbers. If a real number




which tells us that





Draw the line





The convergents to a real number determine its best rational approximations.
As Practice Problem 2 shows, this has important implications for the solution of certain Diophantine equations. The observation that




so in other words, the error is approximately the square of the denominator, which is quite good, and if


Note that the action of the elements of the modular group we described above takes each convergent to a better convergent which has "almost" the same slope - in other words, as lattice points the convergents (and therefore







This notion generalizes slightly as follows: if we take



where




Excursion: It turns out that












Now the general Fibonacci polynomial (for a positive integer











Back on topic, we would like to ask whether


Does there exist a function


We might expect this function to be





Does there exist a notion of continued fraction expansion for some large class of functions?
Rational functions have an obvious choice of terminating simple continued fraction given by the corresponding Euclidean algorithm on polynomials (although it is no longer true that substituting integers will get us a valid simple continued fraction of a rational number; some quotients may be negative). This is an interesting perspective: the Euclidean algorithm then allows one to decompose rational functions uniquely into the composition of fractional linear transformations of the form


This should remind you of the notion of a Taylor series, which essentially asks the question of what class of functions can be appropriately approximated by sequences of polynomials. Indeed, it is possible to ask the same kind of convergence questions for infinite continued fractions as it is for power series, although these questions are much harder to answer. (This appears to be a current area of active research.) A partial answer is provided by Euler's continued fraction formula, a rather beautiful identity which translates an infinite series into an infinite continued fraction and therefore allows a partial translation in the other direction, and it is here that I am, once again, out of details (although my hunch that hypergeometric functions are part of the answer appears to be correct.)
In closing, one application of the modular group is its use in verifying identities involving a fascinating set of functions called modular forms, which are functions that satisfy a "modular symmetry"; in other words, the modular group acts on them in a very specific way (as described in the article). This condition can be broken down into two conditions by looking at two generators of the modular group (which, we must stress, are not unique), and indeed this is the way a function is usually proven modular. A major application of this idea is to prove that two functions are identical by proving that they are both modular with the same value of




First, we will need a few definitions. We say that







Theorem (the Euclidean algorithm, take 5): For a given






The proof is left as an exercise. (Note that








Practice Problem 0: Prove that

Practice Problem 1: Prove that a simple continued fraction is (eventually) periodic if and only if it is the real root of a quadratic polynomial with integer coefficients.
Practice Problem 2: Prove that if




Practice Problem 3: What is the best constant






Practice Problem 4: Prove Take 5.