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