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 50 years
Organizations ATL
Publications Journal of mathematics and its applications
Education/Credentials BSc Hons Liverpool
Awards and Honors State Scholarship 1955
Past/Present Clients I taught John Birt, former Director of the BBC in 1961. His homework book was the most perfect I have ever marked. And also the most neat. I could tell he was destined for great things.
One of my classmates was the poet Roger McGough, and I have a mention in his autobiography.
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.
