Proving the validity of a more efficient algorithm than the extended euclidean algorithm for relative primes

Question

I read in a book that there is a more efficient algorithm (which uses less storage in computers) than the extended euclidean algorithm in the case of relative primes.

As it appears in the attached photo, I could prove that if P_t = a and Q_t = b, then it would be a valid algorithm. But, unfortunately, I can't prove that this recursion will eventually yield "a" and "b". So, anyone can tell me why it works??

Answer 1

This is what you get by applying continued fractions to finding $\gcd(a,b) $ and producing a Bezout identity $ax+by = \gcd(a,b) .$ Consecutive convergents in a continued fraction have the little 2 by 2 cross product equal to $\pm 1 $

On page 18 they find the gcd of 73 and 25:

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ \gcd( 73, 25 ) = ??? $$

$$ \frac{ 73 }{ 25 } = 2 + \frac{ 23 }{ 25 } $$ $$ \frac{ 25 }{ 23 } = 1 + \frac{ 2 }{ 23 } $$ $$ \frac{ 23 }{ 2 } = 11 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 2 & & 1 & & 11 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 1 } & & \frac{ 35 }{ 12 } & & \frac{ 73 }{ 25 } \end{array} $$ $$ $$ $$ 73 \cdot 12 - 25 \cdot 35 = 1 $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ \gcd( 100, 67 ) = ??? $$

$$ \frac{ 100 }{ 67 } = 1 + \frac{ 33 }{ 67 } $$ $$ \frac{ 67 }{ 33 } = 2 + \frac{ 1 }{ 33 } $$ $$ \frac{ 33 }{ 1 } = 33 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccc} & & 1 & & 2 & & 33 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 100 }{ 67 } \end{array} $$ $$ $$ $$ 100 \cdot 2 - 67 \cdot 3 = -1 $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ \gcd( 1001, 43 ) = ??? $$

$$ \frac{ 1001 }{ 43 } = 23 + \frac{ 12 }{ 43 } $$ $$ \frac{ 43 }{ 12 } = 3 + \frac{ 7 }{ 12 } $$ $$ \frac{ 12 }{ 7 } = 1 + \frac{ 5 }{ 7 } $$ $$ \frac{ 7 }{ 5 } = 1 + \frac{ 2 }{ 5 } $$ $$ \frac{ 5 }{ 2 } = 2 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccc} & & 23 & & 3 & & 1 & & 1 & & 2 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 23 }{ 1 } & & \frac{ 70 }{ 3 } & & \frac{ 93 }{ 4 } & & \frac{ 163 }{ 7 } & & \frac{ 419 }{ 18 } & & \frac{ 1001 }{ 43 } \end{array} $$ $$ $$ $$ 1001 \cdot 18 - 43 \cdot 419 = 1 $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

The most steps for $a,b$ of a given size happens with consecutive Fibonacci numbers

$$ \gcd( 144, 89 ) = ??? $$

$$ \frac{ 144 }{ 89 } = 1 + \frac{ 55 }{ 89 } $$ $$ \frac{ 89 }{ 55 } = 1 + \frac{ 34 }{ 55 } $$ $$ \frac{ 55 }{ 34 } = 1 + \frac{ 21 }{ 34 } $$ $$ \frac{ 34 }{ 21 } = 1 + \frac{ 13 }{ 21 } $$ $$ \frac{ 21 }{ 13 } = 1 + \frac{ 8 }{ 13 } $$ $$ \frac{ 13 }{ 8 } = 1 + \frac{ 5 }{ 8 } $$ $$ \frac{ 8 }{ 5 } = 1 + \frac{ 3 }{ 5 } $$ $$ \frac{ 5 }{ 3 } = 1 + \frac{ 2 }{ 3 } $$ $$ \frac{ 3 }{ 2 } = 1 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccc} & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 5 }{ 3 } & & \frac{ 8 }{ 5 } & & \frac{ 13 }{ 8 } & & \frac{ 21 }{ 13 } & & \frac{ 34 }{ 21 } & & \frac{ 55 }{ 34 } & & \frac{ 144 }{ 89 } \end{array} $$ $$ $$ $$ 144 \cdot 34 - 89 \cdot 55 = 1 $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

If there was a common factor, this is divided out in a specific way:

$$ \gcd( 1043, 1001 ) = ??? $$

$$ \frac{ 1043 }{ 1001 } = 1 + \frac{ 42 }{ 1001 } $$ $$ \frac{ 1001 }{ 42 } = 23 + \frac{ 35 }{ 42 } $$ $$ \frac{ 42 }{ 35 } = 1 + \frac{ 7 }{ 35 } $$ $$ \frac{ 35 }{ 7 } = 5 + \frac{ 0 }{ 7 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 1 & & 23 & & 1 & & 5 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 24 }{ 23 } & & \frac{ 25 }{ 24 } & & \frac{ 149 }{ 143 } \end{array} $$ $$ $$ $$ 149 \cdot 24 - 143 \cdot 25 = 1 $$

$$ \gcd( 1043, 1001 ) = 7 $$
$$ 1043 \cdot 24 - 1001 \cdot 25 = 7 $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$