I had quite a difficult time getting myself to fully understand how it works. I jumped between Wikipedia, my data structures textbook (don't buy it), a YouTube video, and this excellent number theory class lecture.The lecture is the best, though I think there may be a typographical error in the recursive formula.
The basic idea uses recursion with an easy base step. We call Euclid(a,b) with a ≥ b:
- The base case is when b is 0. The GCD of x and 0 is always x, and the coefficients to produce a GCD of 0 are 1 and 0 (or anything else): 1*x + 0(or anything)*0 = x. So the base case returns (1,0)
- Any other step starts by recursively calling Euclid(b, a mod b). We know that the GCD of a and b is the same as the GCD of b and a mod b (lemma 12 in the lecture). This recursive call is guaranteed to eventually get to the base case of b = 0.
- After finding the coefficients for producing the GCD from b and a mod b, we can calculate the ones for producing the GCD from a and b, because a mod b can be put in terms of a and b (see the code comments for the formulas).
To really help myself understand the whole thing, I wrote a Perl script to illustrate it. I put in lots of comments as I worked my way through it.
use strict;
use strict;
use warnings;
use 5.010;
#start with a >= b
my @nums = sort {$b <=> $a} @ARGV;
gcd(@nums);
#input: two numbers (a,b) a >= b > 0
#output: the coefficients which which yield their GCD;
sub gcd {
my ($a, $b) = @_;
#base case; the GCD of x and 0 always x;
#and the coefficients will always be 1 and 0 (or anything) because#1*x + 0*0 = xif($b == 0){ say "GCD is $a"; say "(a,b) = ($a,$b), coefficients = (1,0)"; say "1x$a + 0x$b = $a"; return (1, 0); } #otherwise, we evaluate u and v for k = ub + vr, where r is a mod b #gcd(b, a%b) gives the same value my $remainder = $a % $b; my ($u, $v) = gcd($b, $remainder); #now we can find k in terms of a and b because we know r in terms a and b #r = a - bq, where q = the whole part of a/b #k = ub + vr = ub + v(a - bq) = va + b(u-qv) #so the coefficient on a is v, and the coefficient on b is 1-qv my $x = $v; my $q = int(($a/$b)); my $y = $u - $q*$x; say "(a,b) = ($a,$b), coefficients are ($x,$y)"; say "${x}x$a + ${y}x$b = " . ($x*$a + $y*$b); return ($x, $y); }
Feel free to leave a comment if you think that something could be stated more clearly. I hope it helps anyone else trying to learn how the extended Euclidian algorithm works.
