Note that , , and are just the 's in the
Euclidean algorithm. The rational
is written as a
continued fraction

with all the
, for and .

Lemma 6.4.1
Every rational
with and
has exactly one
expression in this form.

Proof.
Existance follows immediately from the Euclidean algorithm. As for
uniqueness, suppose that

with the 's as before. Firstly
as both are equal to
.
Since
then

Thus and so on.

Now, suppose that given
we wish to find
equal to it. Then we work out the numbers and
as in the Euclidean algorithm. Then
by lemma (2.22).
If we stop doing this after steps we get
. The numbers
are called the ``convergents'' to
.
Using lemma (2.23), we get that
. Now the
are strictly increasing, so the gaps are getting smaller and the
signs alternate. We get