The Euclidean Algorithm

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.