Home

> urticator.net
  Search

  About This Site
> 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.

abqr
1309238701309
2387130911078
130910781231
10782314154
231154177
1547720

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.

 

  See Also

  Continued Fractions
  Next Block, The
  Twelve-Note Scale, The

@ November (2005)