I came across this algorithm which may improve on Euclid's for finding
the gcd(a,b) - but I'm stuck on proving that it works...What do you
think? It looks really easy on the face of it.
First note that g.c.d.(a,b) = g.c.d.(|a|,|b|) so without loss of
generality we may suppose that a and b are positive. If a and b are both
even, set d = 2d' with d' = (a/2,b/2).
If one of the two is odd and the other (say b) is even, then set d = d'
with d' = (a,b/2).
If both are odd and they are unequal, say a>b, then set d = d' with d' =
(a-b,b).
Finally, if a=b then set d=a.
Repeat this process until you arrive at the last case (when the two
integers are equal).
Here are a couple of examples:
187,34
187,17
170,17
85,17
68,17
34,17
17,17
1300,1274 143,39
650,637 104,39
325,637 52,39
325,312 26,39
325,156 13,39
325,78 13,26
325,39 13,1
286,39
G. Hagopian
COD
****************************************************************************
* To post to the list: email mathedcc@archives.math.utk.edu *
* To unsubscribe, send mail to: majordomo@archives.math.utk.edu *
* In the mail message, enter ONLY the words: unsubscribe mathedcc *
* Words in the Subject: line are NOT processed! *
* Archives at http://archives.math.utk.edu/hypermail/mathedcc/ *
****************************************************************************