Devised by Euclid, the Euclidean Algorithm is a method for finding
the greatest common divisor of two numbers.
Here's the algorithm:
- Let a and b be your starting numbers
- Compute q and r such that a=qb+r and 0<=r<b
- Copy b into a and r into b.
- Repeat until r=0.
The value in b is now the /gcd/ of the original a and *b*.
As an example, consider 429 and 2002.
a | = | q | * | b | + | r |
2002 | = | 4 | * | 429 | + | 286 |
429 | = | 1 | * | 286 | + | 143 |
286 | = | 2 | * | 143 | + | 0 |
Here we can see that gcd(429,2002) is 143.
Enrichment Task
You should check that:
- this is an algorithm in the technical sense
- the result always divides the original a and b
- every divisor of both a and b will divide the result.
Extras
More if anyone asks.
Links to this page /
Page history /
Last change to this page
Recent changes /
Edit this page (with sufficient authority)
All pages /
Search /
Change password /
Logout