Expert: Vijilant - 1/4/2005

Question
Hello:

I want to thank you for your reply. However, I need some clarification.

1. I am not familiar with this method.
In your example, you have three numbers 16, 28, and 40. If 16 is subtracted from 28, 12 remains, but how is 8 determined in 16, 12 and 8 from you example?
Also, can you demonstrate this method with 4, 8, & 16?

2. I am somewhat familiar with the method using division. For example, gcd for (84, 18): "Divide 84 by 18 to get a quotient of 4 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd."
I am curious to know whether or not this method could be used with more than two numbers, 4, 8, and 16.

I thank you for your help and reply.

-------------------------
Followup To
Question -
Hello:

Can the Euclidean Algorithm be used on more than two numbers to determine the greatest common divisor (gcd) for these numbers?

For example with two numbers (8 & 16) Euclid's algorithm will produce the greatest common divisor of 8

What about with three numbers: gcd(4,8,16) = ?

I thank you for your reply.

Answer -
There is no limit to the number of numbers.  I'll choose a better example to show how it works.
16, 28, 40.  Subtract 16's, but without reducing to zero.
16,12,8.  Now subtract 8's.
8,4,8.  Now subtract 4's.
4,4,4.  so the gcd is 4.
At each stage we subtract multiples of the smallest number but always leaving a positive remainder.  When all the numbers are equal, that is the gcd.  Your example would work in one step, so the method would not be clear.

Answer
The process of subtracting multiples of the smallest number is just the same as taking the remainder after division.  The 8 was chosen because it was the smallest number left.  I suggested that you didn't reduce to zero so that all the numbers would be equal at the end, but it is just the same if you do reduce to zero.
I'll go through it again with my example
16,28,40.  The smallest number is 16.  Divide the other numbers by 16, and just write the remainder.
16,12,8.  The smallest is now 8. Divide the others by 8 and write the remainders.
0,4,8.  The smallest non-zero is now 4.  Divide others by 4.
0,4,0.  The last divisor is 4, so that is the gcd.

4,8,16.  Divide the others by 4 writing the remaiders
4,0,0.  Gcd is 4