Using Euclid's Algorithm with Three Numbers

Date: 11/05/2003 at 00:03:45
From: An
Subject: how do i find the gcd of 3 integers using Euclid's Algorithm

How do I find the GCD of three integers using Euclid's Algorithm?  I
know how to use it with 2 numbers but not 3.  I am not sure where you
plug the third integer into the algorithm.  What do you subtract from
the second or third integer?

Date: 11/05/2003 at 16:52:15
From: Doctor Rob
Subject: Re: how do i find the gcd of 3 integers using Euclid's Algorithm

Thanks for writing to Ask Dr. Math, An!

One approach is to first use the algorithm to find the GCD d of the
first two numbers, then use the algorithm to find the GCD of d and the
third number.

This works because GCD(x,y,z) = GCD(GCD(x,y),z).

Another approach is to start with three numbers x, y, and z.  Label
them so that z is the smallest.  Divide

   x = Q1*z + R1,  0 <= R1 < z,
   y = q1*z + r1,  0 <= r1 < z.

Then replace x and y by R1 and r1, relabel the numbers x, y, and z, so 
that the new z is the smallest nonzero number of the three, and 
repeat.  Continue until both remainders are zero.  Then the last z 
will be the GCD of all three numbers.

Example:  Find the GCD of 203, 91, and 77.

   original {x,y,z} = {203,91,77}
   203 = 2*77 + 49,
    91 = 1*77 + 14,

   new {x,y,z} = {77,49,14},
   77 = 5*14 + 7,
   49 = 3*14 + 7,

   new {x,y,z} = {14,7,7},
   14 = 2*7 + 0,
    7 = 1*7 + 0,

Both remainders are 0, so GCD = last z = 7.

GCD is 7.

Feel free to write again if I can help further.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/