AboutVijilant Expertise Most questions on number theory, divisibility, primes, Euclidean algorithm, Fermat`s theorem, Wilson`s theorem, factorisation, euclidean algorithm, diophantine equations, Chinese remainder theorem, group theory, congruences, continued fractions.
Experience Teacher of math for 48 years
Organizations ATL
Publications Journal of mathematics and its applications
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.
