next up previous contents
Next: Applications of the Euclidean Up: The integers Previous: The Euclidean Division   Contents

The Euclidean algorithm

Suppose we want to find $ (525,231)$. We use lemmas $ \vref{prop euclidean division}$ and $ \eqref{L:toeuc}$ to obtain:

$\displaystyle 525$ $\displaystyle = 2 \times 231 + 63$    
$\displaystyle 231$ $\displaystyle = 3 \times 63 + 42$    
$\displaystyle 63$ $\displaystyle = 1 \times 42 + 21$    
$\displaystyle 42$ $\displaystyle = 2 \times 21 + 0$    

So $ (525,231) = (231,63) = (63,42) = (42,21) = 21$. In general, to find $ (a,b)$:

$\displaystyle a$ $\displaystyle = q_1 b + r_1$   with $\displaystyle 0 < r_1 < b$    
$\displaystyle b$ $\displaystyle = q_2 r_1 + r_2$   with $\displaystyle 0 < r_2 < r_1$    
$\displaystyle r_1$ $\displaystyle = q_3 r_2 + r_3$   with $\displaystyle 0 < r_3 < r_2$    
  $\displaystyle \vdots$    
$\displaystyle r_{i-2}$ $\displaystyle = q_i r_{i-1} + r_i$   with $\displaystyle 0 < r_i < r_{i-1}$    
  $\displaystyle \vdots$    
$\displaystyle r_{n-3}$ $\displaystyle = q_{n-1} r_{n-2} + r_{n-1}$   with $\displaystyle 0 < r_n < r_{n-1}$    
$\displaystyle r_{n-2}$ $\displaystyle = q_n r_{n-1} + 0.$    

This process must terminate as $ b > r_1 > r_2 > \dots > r_{n-1} > 0$. Using Lemma (2.21), $ (a,b) = (b,r_1) = \dots = (r_{n-2},r_{n-1})
= r_{n-1}$. So $ (a,b)$ is the last non-zero remainder in this process. We now wish to find $ x_0$ and $ y_0 \in \mathbb{Z}$ with $ (a,b) = a x_0 + b y_0$. We can do this by backsubstitution.

$\displaystyle 21$ $\displaystyle = 63 - 1 \times 42$    
  $\displaystyle = 63 - (231 - 3 \times 63)$    
  $\displaystyle = 4 \times 63 - 231$    
  $\displaystyle = 4 \times (525 - 2 \times 231) - 231$    
  $\displaystyle = 4 \times 525 - 9 \times 231.$    

This works in general but can be confusing and wasteful. These numbers can be calculated at the same time as $ (a,b)$ if we know we shall need them. We introduce $ A_i$ and $ B_i$. We put $ A_{-1} = B_0 = 0$ and $ A_0 = B_{-1} = 1$. We iteratively define

$\displaystyle A_i$ $\displaystyle = q_i A_{i-1} + A_{i-2}$    
$\displaystyle B_i$ $\displaystyle = q_i B_{i-1} + B_{i-2}.$    

Now consider $ a B_j - b A_j$.

Lemma 6.2.22  

$\displaystyle a B_j - b A_j = (-1)^{j+1} r_j.
$

Proof. We shall do this using strong induction. We can easily see that (2.22) holds for $ j=1$ and $ j=2$. Now assume we are at $ i \ge 2$ and we have already checked that $ r_{i-2} = (-1)^{i-1} (a B_{i-2} - b A_{i-2})$ and $ r_{i-i} = (-1)^i (a B_{i-1} - b A_{i-1})$. Now

$\displaystyle r_i$ $\displaystyle = r_{i-2} - q_i r_{i-1}$    
  $\displaystyle = (-1)^{i-1} (a B_{i-2} - b A_{i-2}) - q_i (-1)^i (a B_{i-1} - b A_{i-1})$    
  $\displaystyle = (-1)^{i+1} (a B_i - b A_i)$, using the definition of $ A_i$ and $ B_i$.    

$ \qedsymbol$

Lemma 6.2.23  

$\displaystyle A_i B_{i+1} - A_{i+1} B_i = (-1)^i$    

Proof. This is done by backsubstitution and using the definition of $ A_i$ and $ B_i$. $ \qedsymbol$

An immediate corollary of this is that $ (A_i,B_i) = 1$.

Lemma 6.2.24  

$\displaystyle A_n = \frac{a}{(a,b)} \qquad B_n = \frac{b}{(a,b)}.$    

Proof. (2.22) For $ i=n$ gives $ a B_n = b A_n$. Therefore $ \frac{a}{(a,b)} B_n = \frac{b}{(a,b)} A_n$. Now $ \frac{a}{(a,b)}$ and $ \frac{b}{(a,b)}$ are coprime. $ A_n$ and $ B_n$ are coprime and thus this lemma is therefore an immediate consequence of the following theorem. $ \qedsymbol$

Theorem 6.2.25   If $ d \mid ce$ and $ (c,d) = 1$ then $ d \mid e$.

Proof. Since $ (c,d) = 1$ we can write $ 1 = cx + dy$ for some $ x$, $ y \in \mathbb{Z}$. Then $ e = ecx + edy$ and $ d \mid e$. $ \qedsymbol$

Definition 6.2.26   The least common multiple (lcm) of $ a$ and $ b$ (written $ [a,b]$) is the integer $ l$ such that
  1. $ a \mid l$ and $ b \mid l$,
  2. if $ a \mid l'$ and $ b \mid l'$ then $ l \mid l'$.

It is easy to show that $ [a,b] = \frac{ab}{(a,b)}$.
next up previous contents
Next: Applications of the Euclidean Up: The integers Previous: The Euclidean Division   Contents
root 2002-06-10