My number theory class has moved on from Pythagorean triples. Lately we’ve been talking about the Euclidean algorithm. Specifically, it’s an algorithm for finding the greatest common divisor (gcd) of two numbers.

Of course, there are lots of ways finding the gcd. You could simply list all of the divisors of the first number, all of the divisors of the second number, and then compare the two lists. Let me suggest, though, that this method gets tedious in a hurry. Even for a computer it’s hopelessly inefficient.

A somewhat better way involves finding the prime factorizations of the two numbers. The gcd can then be found by looking at the intersection of the two factorizations. But this too is rather inefficient when you are dealing with large numbers.

Which brings us to the big algorithm. It is based on the idea that if *A* and *B* are the two numbers, with *A* larger, then we can divide *A* by *B* to get a quotient and a remainder:

\[

A=qB+r

\]

Though I won’t stop to do a formal proof, it is now the case that

\[

\gcd(A,B)=\gcd(B,r),

\]

which is pretty cool, since *r* is smaller than *B*. The basic idea is that in our previous equation, any divisor of two of the three terms must also divide the third term as well.

Perhaps now the strategy is clear. We just keep dividing, so that our problem involves finding the *gcd* of smaller and smaller numbers.

(For the TeX hounds in the audience, I should point out that my TeX renderer does not seem to recognize the align environment. Hence the somewhat awkward layout.)

As an example, let us take

\[

A=147 \phantom{xxx} \textrm{and} \phantom{xxx} B=114.

\]

Then we can compute:

\[

147=(1)(114)+33

\]

\[

114=(3)(33)+15

\]

\[

33=(2)(15)+3

\]

\[

15=(3)(5)

\]

We now conclude that the gcd is 3, the logic being that

\[

\gcd(147,114)=\gcd(114,33)=\gcd(33,15)=\gcd(15,3).

\]

Not a bad trick! And extremely efficient, as it happens.

But I know what you’re thinking. You’re thinking: Gosh! It sure is cool that you can find the gcd so easily. But now suppose that *A* and *B* are two integers with gcd equal to *d*. Can I use the Euclidean algorithm to find (possibly negative) integers *x* and *y* that solve the equation:

\[

Ax+By=d?

\]

Indeed you can. The trick is to work the algorithm backward. For example, if I want to find a solution to

\[

147x+114y=3,

\]

I can reason like this:

\[

3=33-(2)(15)

\]

\[

3=33-(2)(114-(3)(33))= -2(114)+7(33)

\]

\[

3= -2(114)+7(147-(1)(114))=147(7)+114(-9)

\]

which certainly does the trick. Now, I grant you that little computation might seem like it came out of left field. It turns out though, that it is just what we will need later to solve certain problems involving modular arithmetic. Don’t know what that is? Well, just stay tuned!