The Official Euclidean Algorithm

Date: 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/