Math Forum Discussions

Ladnor Geissinger

Posts: 313
From: University of North Carolina at Chapel Hill
Registered: 12/4/04

Extended Euclidean Algorithm
Posted: Feb 5, 2005 2:15 AM

Plain Text

I wrote this note in response to a thread (Linear diophantine equation
question) which appeared in alt.math.undergrad on 3 Feb 05. Perhaps
others who teach some elementary number theory and require their
students to use the Euclidean Algorithm will find this discussion
useful.
=============================================================
--------------------------------------------------------
On Thu, 03 Feb 2005 00:01:40 GMT, Jeff Heikkinen wrote:
(after a description of the method he finally arrived at, following
his professor's suggestion, for extending the Euclidean Algorithm)
>For the purposes of undergraduate level number theory, this method
>slices, dices, makes Julienne fries, *and* deciphers the lyrics to
>Louie Louie; it can help you with nearly any nontrivial problem, I am
told.
---------------------------------------------------------
It's nice that he is so happy about the method, but I'd like to point
out that he was very close to getting even more in a slick package
that allows for easy proofs as well as computation.

I had never heard of the Blankinship algorithm, but it seems to be
almost identical to a form of the Extended Euclidean Algorithm (EEA)
which I devised many years ago and which I have been teaching to my
students whenever the subject is elementary number theory - in a
number theory or abstract algebra or discrete math class. A brief
description of this algorithm follows.

EEA: Suppose given integers A > B > 0.
Form a sequence of triples as follows.
Initialize: first triple (A,1,0), second triple (B,0,1).
Now divide A by B and write A=Q1*B+R1 with Q1 and R1 integers, and
0<=R1<B. Then the third triple is (A,1,0)-Q1*(B,0,1)=(R1,1,-Q1).
Repeat this process until the first entry in a computed triple is 0.
(And DO compute the second and third entries in this last triple!)

To be a bit clearer about what exactly is to be done repeatedly, let's
look at some stage in this process where the previous and current
computed triples are (R,S,T) and (U,V,W). By our construction 0<=U<R.

Suppose that U is not zero. Then we will divide R by U to get R=Q*U+X
with Q and X integers and 0<=X < U.
Then the next triple will be (R,S,T)-Q*(U,V,W)=(X,Y,Z).
These triples were constructed to have the property R=S*A+T*B and
U=V*A+W*B, and it is easy to check that then also X=Y*A+Z*B. This is
a loop invariant. Notice that this property is equivalent to saying
that each triple is orthogonal to the vector (-1,A,B).
Also note that the computation in this step can be described in matrix
language as follows:
Let E=[0,1; 1,-Q], then E*[R,S,T; U,V,W]=[U,V,W; X,Y,Z]. Note that E
has determinant -1. Each previous step in the loop can be carried out
by multiplying by such a matrix, so it follows that if (U,V,W) is the
n-th computed triple, and if F is the product of all these previous
matrices like E, then det(F)=(-1)^n and
F*[A,1,0; B,0,1]= [R,S,T; U,V,W].
Which of course means that F= [S,T; V,W], so we were keeping track of
this matrix all along without noticing!

Finally, suppose that U=0. Then as usual we can easily show that R is
the greatest common divisor GCD(A,B), and we have the desired result
that GCD(A,B)=S*A+T*B from the penultimate triple. The last triple
now yields 0=V*A+W*B, and we can easily show that
|V*A|=|W*B|=LCM(A,B), that is, V=+-B/R and W=+-A/R. (see below)
Moreover, for any integers K and L such that R=K*A+L*B, it must be the
case that (K,L)=(S,T)+m*(V,W) for some integer m.

Some observations on the resulting sequence of integer triples:
1. The column of first entries is strictly decreasing and ends in 0.
2. After the initial triples, the entries in columns 2 and 3 are
nonzero, they alternate in sign, and are strictly increasing in
absolute value.
3. Suppose that we replace the first entry in each triple by the
quotient when that entry is divided by R, i.e.
newcolumn1=oldcolumn1/R. Also let A=A'*R and B=B'*R, then A' and B'
are coprime. And if we carry out our algorithm beginning with A' and
B' we will get this newcolumn1 along with the SAME old columns 2 and
3. Which means that F*[A',1,0; B',0,1]= [1,S,T; 0,V,W] at the end
(when U=0). And the inverse F^(-1)=(-1)^n*[W,-T; -V,S] so when you
multiply it on the left and check the first column you see that
(-1)^n*[W; -V]=[A'; B'].

By the way, note that this algorithm requires no confusing
back-tracking of the sort that appears in most elementary number
theory discussions in order to get the S and T such that
GCD(A,B)=S*A+T*B. Also, we really only need 6 memory locations to
store numbers used in the algorithm -- we could print out the initial
triples (so A and B are recorded), and then at each step we need only
the previous triple and the current triple to compute the next triple,
which we could then print out if we want it (maybe along with the
current quotient Q), or just wait until the
end and print out the final 2 triples. And finally, you can carry
this out easily in Excel or any other spreadsheet.

============================================================
Ladnor Geissinger, Professor of Mathematics
Mathematics Dept, CB 3250 Phillips Hall
Univ of North Carolina, Chapel Hill NC 27599 USA

--
submissions: post to k12.ed.math or e-mail to k12math@k12groups.org
private e-mail to the k12.ed.math moderator: kem-moderator@k12groups.org
newsgroup website: http://www.thinkspot.net/k12math/
newsgroup charter: http://www.thinkspot.net/k12math/charter.html