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 $\geq$ b. Let u₀ = (1, a) and v₀ = (0, b). If b = 0, then our solution is (x, z) = (1, a). We compute, q₀ = [a/b] (the integer part of a/b) and set

v₁ = (v_{1, 1}, v_{1, 2}) = u - q ^. v

u₁ = (u_{1, 1}, u_{1, 2}) = v

Proceeding inductively, if v_{i, 2} = 0 then (x, z) = u_i is a solution. Otherwise, we let q_i = [u_{i, 2}/v_{i, 2}] and set

u_{i + 1} = (u_{i + 1, 1}, u_{i + 1, 2}) = v_i

v_{i + 1} = (v_{i + 1, 1}, v_{i + 1, 2}) = u_i - q_i ^. v_i

We then iterate, until v_{i, 2} = 0, which is becoming smaller at each step. Clearly, the first step is a special case for i = 0 of the remaining steps¹. 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 $\geq$ b and let u₀ = (1, a) and v₀ = (1, b). We are at the step i = 0. If v_{i, 2} = 0, then our solution is u_i. Now let x denote the leading ``digit'' of u_{i, 2} and y denote the leading digit of v_{i, 2} at the same place (as in Lehmer's algorithm). We carry through the process of Lehmer's algorithm to compute the matrix $\left(\vphantom{ \begin{smallmatrix} A_i & B_i C_i & D_i \end{smallmatrix} }\right.$$\begin{smallmatrix} A_i & B_i C_i & D_i \end{smallmatrix}$$\left.\vphantom{ \begin{smallmatrix} A_i & B_i C_i & D_i \end{smallmatrix} }\right)$. If B = 0 then we calculate q_i = [u_{i, 2}/v_{i, 2}] and set as above,

u_{i + 1} = (u_{i + 1, 1}, u_{i + 1, 2}) = v_i

v_{i + 1} = (v_{i + 1, 1}, v_{i + 1, 2}) = u_i - q_i ^. v_i

Otherwise (B $\neq$ 0) we set

u_{i + 1} = Au_i + Bv_i

v_{i + 1} = Cu_i + Dv_i

We then iterate the procedure until v_{i, 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/2^k and d = b/2^k. 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 u₁ = (1, c) and v₁ = (0, d ) at i = 1. At each stage w_i will be a pair in which the second part is even. Thus, if c is odd we put w₁ = u₁ - v₁, else (if c is even) we put w₁ = u₁.

Now we perform the following steps inductively. First of all if w_{i, 2} = 0 then (x, z) = u_i is the required pair and we exit the induction. Next we remove powers of two from w_i. For this we take z_{1, i} = w_i and induct on z_{k, i} as follows.

z_{k + 1, i} = $$% latex2html id marker 14386 \begin{cases}\frac{1}{2}\cdo... ...i,1}+d,z_{k,i,2}) &\text{~if $z_{k,i,1}$\ is odd} \end{cases}$$

Note that, by induction on k, d divides z_{k + 1, 2} - cz_{k + 1, 1} in both cases. We stop as soon as z_{k, i, 2} is odd and put z_i = z_{k, i}.

The last inductive step is the re-assignment. If z_{i, 2} is negative, then we take v_{i + 1} = - z_i and u_{i + 1} = u_i, otherwise we take u_{i + 1} = z_i and v_{i + 1} = v_i. Then we put w_{i + 1} = u_{i + 1} - v_{i + 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 = 2^kz, while if f = 1 then we have ay + bx = 2^kz. In both cases 2^kz is the GCD of a and b (this follows since the steps that we are performing on the second part of the pairs u_i and v_i are exactly the same as those for binary GCD).