Euclids algorithm and Lames theorem on a microcomputer.pdfVIP

Bridgewater State University Virtual Commons - Bridgewater State University Mathemati s and Computer S ien e Fa ulty Mathemati s and Computer S ien e Department Publications 1989 Euclids algorithm and Lames theorem on a microcomputer Thomas Moore Bridgew ater State College, MO ORE@ Virtual Commons Citation Moore, Thomas (1989). Euclids algorithm and Lames theorem on a micro omputer. In Mathematics and Compu ter Science Faculty Publications. Paper 8. Available at : http://v ./math_ omps i_fac/8 This item is available as part of Virtual Commons, the open-a ess institutional repository of Bridgewater State University, Bridgewater, Massachusetts. EUCLIDT S AL GORITHM AND LAME S THEOREM ON A MICR OCOMPUTER T h o m a s E . Moore Bridgewater State College, Bridgewater, MA 02324 (Submitted July 1987) To the memory of my friend and colleague Hugo DAlarcao. 1. Introduction We denote the greatest common divisor of two nonzero integers m and n by gcd(/?7, ri) . Since it is true that gcd(m, ri) = gcd(±w, ±n) , and since gcd(m, ri) = gcd(?2,rri) ,we may assume that both 77? and n are positive and m n. The Euclidean algorithm for computing gcd(m, n) is a familiar process of iterated long division which can be written as follows: n - mql + ^i ; 0 r, m, m = ^2 72 + rz ® ^2 rl5 r p + P P r l 7 2?3 3 ° 3 2 r _ = r _