Next: 3 Arithmetic modulo N Up: 2 Greatest common divisor Previous: 2.3 Lehmer's Algorithm

## 2.4 Extended GCD

Quite often we not only need to know the GCD of two integers a and b but also to write this GCD in the form ax + by. In other words we need to solve the equation ax + by = c when c is the GCD. In fact we can define the GCD as the smallest c that satisfies this equation. Equivalently, we can define the GCD as the smallest z such that there is a pair (x, z) so that z - ax is divisible by b. Thus we can start with some obvious'' pairs and use them to construct new ones which are smaller.

First of all let us follow Euclid's approach. Suppose a b. Let u0 = (1, a) and v0 = (0, b). If b = 0, then our solution is (x, z) = (1, a). We compute, q0 = [a/b] (the integer part of a/b) and set

 v1 = (v1, 1, v1, 2) = u - q . v u1 = (u1, 1, u1, 2) = v

Proceeding inductively, if vi, 2 = 0 then (x, z) = ui is a solution. Otherwise, we let qi = [ui, 2/vi, 2] and set
 ui + 1 = (ui + 1, 1, ui + 1, 2) = vi vi + 1 = (vi + 1, 1, vi + 1, 2) = ui - qi . vi

We then iterate, until vi, 2 = 0, which is becoming smaller at each step. Clearly, the first step is a special case for i = 0 of the remaining steps1. At the end we take y = z - ax/b. Then ax + by = z and z is the GCD of a and b.

Extending Lehmer's approach is very similar. As above, suppose that a b and let u0 = (1, a) and v0 = (1, b). We are at the step i = 0. If vi, 2 = 0, then our solution is ui. Now let x denote the leading digit'' of ui, 2 and y denote the leading digit of vi, 2 at the same place (as in Lehmer's algorithm). We carry through the process of Lehmer's algorithm to compute the matrix . If B = 0 then we calculate qi = [ui, 2/vi, 2] and set as above,

 ui + 1 = (ui + 1, 1, ui + 1, 2) = vi vi + 1 = (vi + 1, 1, vi + 1, 2) = ui - qi . vi

Otherwise (B 0) we set
 ui + 1 = Aui + Bvi vi + 1 = Cui + Dvi

We then iterate the procedure until vi, 2 becomes zero, which it must since it is decreasing at each step (this argument is as in the case of Lehmer's algorithm). At the end we take y = z - ax/b. Then ax + by = z and z is the GCD of a and b.

Finally, we turn to the binary GCD technique. As usual, if b is zero then we have the solution (x, y, z) = (1.0, a); if a is zero then we have the solution (x, y, z) = (0, 1, b). Otherwise, we take k to the minimum of the 2-adic values of a and b. Let c = a/2k and d = b/2k. Now, if d is even, then we interchange c and d and keep track of this interchange by setting a flag f to 1.

We may now assume that we have d odd and c non-zero. We will start with the pairs u1 = (1, c) and v1 = (0, d ) at i = 1. At each stage wi will be a pair in which the second part is even. Thus, if c is odd we put w1 = u1 - v1, else (if c is even) we put w1 = u1.

Now we perform the following steps inductively. First of all if wi, 2 = 0 then (x, z) = ui is the required pair and we exit the induction. Next we remove powers of two from wi. For this we take z1, i = wi and induct on zk, i as follows.

zk + 1, i =

Note that, by induction on k, d divides zk + 1, 2 - czk + 1, 1 in both cases. We stop as soon as zk, i, 2 is odd and put zi = zk, i.

The last inductive step is the re-assignment. If zi, 2 is negative, then we take vi + 1 = - zi and ui + 1 = ui, otherwise we take ui + 1 = zi and vi + 1 = vi. Then we put wi + 1 = ui + 1 - vi + 1 and induct.

When we exit the induction, we have (x, z) so that d divides z - cx, so let y = z - cx/d. If f = 0, then we have ax + by = 2kz, while if f = 1 then we have ay + bx = 2kz. In both cases 2kz is the GCD of a and b (this follows since the steps that we are performing on the second part of the pairs ui and vi are exactly the same as those for binary GCD).

Next: 3 Arithmetic modulo N Up: 2 Greatest common divisor Previous: 2.3 Lehmer's Algorithm
Kapil Hari Paranjape 2002-10-20