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
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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search