Using Euclid's Algorithm with Three NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/