First of all let us follow Euclid's approach. Suppose a b. Let
u_{0} = (1, a) and v_{0} = (0, b). If b = 0, then our solution is
(x, z) = (1, a).
We compute, q_{0} = [a/b] (the integer part of a/b) and set
v_{1} = (v_{1, 1}, v_{1, 2}) | = | u - q^{ . }v | |
u_{1} = (u_{1, 1}, u_{1, 2}) | = | v |
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} |
Extending Lehmer's approach is very similar. As above, suppose that
a b and let u_{0} = (1, a) and v_{0} = (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
.
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} |
u_{i + 1} | = | Au_{i} + Bv_{i} | |
v_{i + 1} | = | Cu_{i} + Dv_{i} |
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} = (1, c) and v_{1} = (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_{1} = u_{1} - v_{1}, else (if c is even) we put w_{1} = u_{1}.
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.
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^{k}z, while if f = 1 then we have ay + bx = 2^{k}z. In both cases 2^{k}z 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).