next up previous contents
Next: Rational numbers Up: The classical sets of Previous: The Euclidean algorithm   Contents

Applications of the Euclidean algorithm

Take $ a$, $ b$ and $ c \in \mathbb{Z}$. Suppose we want to find all the solutions $ x$, $ y \in \mathbb{Z}$ of $ a x + b y = c$. A necessary condition for a solution to exist is that $ (a,b) \mid c$, so assume this.

Lemma 6.3.1   If $ (a,b) \mid c$ then $ a x + b y = c$ has solutions in $ \mathbb{Z}$.

Proof. Take $ x'$ and $ y' \in \mathbb{Z}$ such that $ a x' + b y' = (a,b)$. Then if $ c = q (a,b)$ then if $ x_0 = q x'$ and $ y_0 = q y'$, $ a x_0 + b y_0 = c$. $ \qedsymbol$

Lemma 6.3.2   Any other solution is of the form $ x = x_0 + \frac{b k}{(a,b)}$, $ y = y_0 - \frac{a k}{(a,b)}$ for $ k \in \mathbb{Z}$.

Proof. These certainly work as solutions. Now suppose $ x_1$ and $ y_1$ is also a solution. Then $ \frac{a}{(a,b)}(x_0 - x_1) = \frac{b}{(a,b)}(y_0 - y_1)$. Since $ \frac{a}{(a,b)}$ and $ \frac{b}{(a,b)}$ are coprime we have $ \frac{a}{(a,b)} \mid (y_0 - y_1)$ and $ \frac{b}{(a,b)} \mid (x_0 - x_1)$. Say that $ y_1 = y_0 - \frac{a k}{(a,b)}$, $ k \in \mathbb{Z}$. Then $ x_1 = x_0 + \frac{b k}{(a,b)}$. $ \qedsymbol$



root 2002-06-10