The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

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   

Book VII, Proposition 2   

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   
Associated Topics:
College Algorithms
College Discrete Math
College Number Theory
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.