Home

> urticator.net
Search

> Domains
Glue
Stories

Computers
Driving
Games
Humor
Law
> Math
Numbers
Science

Game Theory Section
A Theorem on Finite Abelian Groups
Probability
> Miscellaneous

Commutative Diagrams
On Rectangular Tilings
 > The Euclidean Algorithm
Continued Fractions
The Twelve-Note Scale
Tesseract Model
The Pentagon Knot

## The Euclidean Algorithm

If you have two whole numbers, a and b, sometimes you'd like to find the largest number that divides evenly into both of them. That number is called the greatest common divisor, or GCD, and is usually written in symbolic form as (a,b). What the Euclidean algorithm is is an efficient way of finding GCDs.

1. Divide a by b to get a quotient q and remainder r.
2. If r = 0, the answer is b.
3. If not, start over, using b and r in place of a and b.

That's the most explicit example of a program yet! To see how it works, let's try a = 1309 and b = 2387.

 a b q r 1309 2387 0 1309 2387 1309 1 1078 1309 1078 1 231 1078 231 4 154 231 154 1 77 154 77 2 0

So, there's the answer … (1309,2387) = 77. By the way, that first step is kind of stupid, isn't it? Normally you'd avoid it by setting a to the larger number right at the start, but the algorithm works fine even if you don't.

What are GCDs good for? Well, they're pretty fundamental, so asking what they're good for is sort of like asking what addition is good for. Nevertheless, here are a few random things that come to mind.

• If you have a fraction a/b, the GCD is exactly what you need to cancel to obtain lowest terms. With 1309/2387, for example, you can divide by 77 to get 17/31.
• The case (a,b) = 1 is so important that there's special terminology for it: a and b are relatively prime.
• The numbers relatively prime to n form a lovely group under multiplication mod n. I wrote about the structure of such groups in A Theorem on Finite Abelian Groups.
• If n is relatively prime to 10, the decimal expansion of 1/n won't have any digits before the repeating part. For more about that, see Repeat Length.