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


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 nth 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 backtracking 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 email to k12math@k12groups.org private email to the k12.ed.math moderator: kemmoderator@k12groups.org newsgroup website: http://www.thinkspot.net/k12math/ newsgroup charter: http://www.thinkspot.net/k12math/charter.html

