Next:
Rational numbers
Up:
The classical sets of
Previous:
The Euclidean algorithm
Contents
Applications of the Euclidean algorithm
Take
,
and
. Suppose we want to find all the solutions
,
of
. A necessary condition for a solution to exist is that
, so assume this.
Lemma 6.3.1
If
then
has solutions in
.
Proof
. Take
and
such that
. Then if
then if
and
,
.
Lemma 6.3.2
Any other solution is of the form
,
for
.
Proof
. These certainly work as solutions. Now suppose
and
is also a solution. Then
. Since
and
are coprime we have
and
. Say that
,
. Then
.
root 2002-06-10