The Official Euclidean AlgorithmDate: 11/16/2000 at 12:58:25 From: Julie Subject: Euclidean Algorithm Can you state the Euclidean Algorithm? I keep getting it in other people's words, but I need the official "Euclidean Algorithm" stated correctly. Date: 11/16/2000 at 15:31:47 From: Doctor Rob Subject: Re: Euclidean Algorithm Thanks for writing to Ask Dr. Math, Julie. A translation of the original may be found in Euclid's Elements, Book VII, Propositions 1 and 2 (David Joyce). See these URLs: Book VII, Proposition 1 http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/propVII1.html Book VII, Proposition 2 http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/propVII2.html The discussion after the translation is enlightening. A framing of this in modern notation: Input: Two positive integers a and b. Output: The GCD of a and b. 1. Set x = a and y = b. 2. If x < y, exchange x and y. 3. Replace x by x - y. 4. If x = 0, output y and stop. 5. Go back to step 2. A modern version replaces repeated subtraction of the smaller number from the larger one by a division with remainder: Input: Two positive integers a and b. Output: The GCD of a and b. 1. Set r(1) = a, r(2) = b, and i = 1. 2. Find quotient q(i) and remainder r(i+2) such that r(i) = q(i)*r(i+1) + r(i+2) and 0 <= r(i+2) < r(i+1). 3. If r(i+2) = 0, output r(i+1) and stop. 4. Replace i by i+1. 5. Go to Step 2. There are many variants, including the Extended Euclidean Algorithm, the Binary Euclidean Algorithm, and so on. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/