Monday Math: The Euclidean Algorithm

Posted by jrosenhouse on February 7, 2011
(9)
More »

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!

(9)
More »

Comments

  1. #1 Donald Knooth
    February 8, 2011

    All real texers know to use \gcd to get the right font. gcd, like sin, cos, etc. should always appear in the roman font.

  2. #2 Jason Rosenhouse
    February 8, 2011

    Fixed! Sorry I offended your TeX sensibilities.

  3. #3 Stephen Lucas
    February 8, 2011

    Something to amuse: Jason hasn’t explicitly stated it here, but the gcd algorithm in pretty much every book out there that mentions it requires that the remainder be positive. A variant of the algorithm allows you to choose the reminder negative if it makes the magnitude smaller. For example, given 423 and 107, the classic algorithm would use 423 = 3 * 107 + 102 so gcd(423,107)=gcd(107,102). The alternative is 423 = 4 * 107 – 5 so gcd(423,107)=gcd(107,5).

    It’s been proven that this approach will sometimes take the same number of steps to find the gcd, will usually take less steps, but never takes more. I have no idea why the insistence that the remainder be positive…

  4. #4 phayes
    February 8, 2011

    “the gcd algorithm in pretty much every book out there that mentions it requires that the remainder be positive. A variant of the algorithm allows you to choose the reminder negative”

    Interesting. I didn’t know it’s computationally more efficient but I do remember being led to discover it by a problem in a textbook’s (Niven, Zuckerman, Montgomery) section on divisibility and the Euclidean algorithm:

    “Let a and b be positive integers such that (1 + ab)|(a² + b²). Show that the integer (a² + b²)/(1 + ab) must be a perfect square.”

    Something else to amuse. :)

  5. #5 g
    February 8, 2011

    phayes, that’s cruel.

    (That problem was Q6 in the 1988 International Mathematical Olympiad, and is still notorious for having been very difficult by the already rather tough standards of the IMO.)

  6. #6 Jason Rosenhouse
    February 8, 2011

    Stephen –

    Thanks for the comment. I knew you had done some work on the Euclidean algorithm, but I didn’t remember specifically what you had looked at.

  7. #7 phayes
    February 8, 2011

    @g Notoriously difficult eh? :-D I suppose so and I expect that’s why I remembered it.

  8. #8 Jon Wharf
    February 17, 2011

    phayes, an interesting problem…

    A little numerical exploration inspired the following solution using an infinite descent proof:

    a=b clearly implies a=b=1.

    Take some general solution a a^2 + b^2 = k(1 + ab) = k + kab

    (Note that ab < b^2 therefore k > 1)

    If b = ka, clearly k = a^2 (and b = a^3). This is a solution for all values of a.

    b >= ka+1 is impossible because b^2 >= b(1+ka) = b + kab > k + kab

    Otherwise, b < ka
    Note that k + b^2 < k + kab = a^2 + b^2
    and so k < a^2

    We can descend to a smaller solution (c,a) with the same divisor k by setting c=ka-b:

    c^2 + a^2
    = (ka-b)^2 + a^2
    = (ka)^2 - 2kab + b^2 + a^2
    = ka.ka - 2kab + k + kab
    = ka.ka - kab + k
    = ka(ka-b) + k
    = k(1 + ac)
    as requred. Also note that
    a^2 + b^2 = k + kab
    a^2 - k = kab - b^2
    a^2 > b(ka – b)
    therefore since b>a, c=(ka-b)

    Only those solutions which reduce via descent to the form b=ka can exist. Therefore k is always a square.

  9. #9 Jon Wharf
    February 17, 2011

    Ha ha, curse you html!

    Reposted with suitable protection and of course preview followed by re-pasting:

    phayes, an interesting problem…

    A little numerical exploration inspired the following solution using an

    infinite descent proof:

    a=b clearly implies a=b=1.

    Take some general solution a<b with divisor k.
    a^2 + b^2 = k(1 + ab) = k + kab

    (Note that ab < b^2 therefore k > 1)

    If b = ka, clearly k = a^2 (and b = a^3). This is a solution for all values

    of a.

    b >= ka+1 is impossible because b^2 >= b(1+ka) = b + kab > k + kab

    Otherwise, b < ka
    Note that k + b^2 < k + kab = a^2 + b^2
    and so k < a^2

    We can descend to a smaller solution (c,a) with the same divisor k by setting

    c=ka-b:

    c^2 + a^2
    = (ka-b)^2 + a^2
    = (ka)^2 – 2kab + b^2 + a^2
    = ka.ka – 2kab + k + kab
    = ka.ka – kab + k
    = ka(ka-b) + k
    = k(1 + ac)
    as requred. Also note that
    a^2 + b^2 = k + kab
    a^2 – k = kab – b^2
    a^2 > b(ka – b)
    therefore since b>a, c=(ka-b)<a

    Only those solutions which reduce via descent to the form b=ka can exist.

    Therefore k is always a square.