Explaining the Euclidean AlgorithmDate: 10/27/98 at 08:49:31 From: Megan Subject: Analysis, prime factorization There is an algorithm for prime factorization called the Division Algorithm. Given integers s and t, t > 0, there exist unique integers q and r such that s = t*q + r and 0 =< r < t. We need to find the GCF of both numbers. For example, to find the GCF of 54 and 198 by the division algorithm, divide 198 by 54. Repeat the process using the divisor as the new dividend and the remainder as the new divisor: 198 = 3*54 + 36 54 = 1*36 + 18 36 = 2*18 + 0 When we get 0 as the remainder, the last divisor, here 18, is the GCF of the given integers. The procedure is called the Euclidean algorithm. I need to know why this algorithm works. What is the explanation for why these particular steps give you the GCF of the two numbers? Thanks a lot, Megan Date: 10/27/98 at 09:19:09 From: Doctor Rob Subject: Re: Analysis, prime factorization At each step, you can show that if d divides the divisor t and the dividend s, it also divides the remainder r. If d divides t, write t = d*T. If d divides s, write s = d*S. Then using the equation: r = s - q*t r = d*S - q*d*T r = d*(S - q*T) r = d*R and so d divides r, too. This shows that any common divisor of the first two numbers must also divide the last divisor, by working down the chain of equations one at a time. (You can use the Principle of Mathematical Induction on the number of steps to make this into a proof.) Similarly, if d divides the divisor t and the remainder r, it also divides the dividend s. Write t = d*T, r = d*R. Then: s = q*t + r s = q*d*T + d*R s = d*(q*T + R) s = d*S and so d divides s, too. This shows that any factor of the last divisor, including that last divisor itself, also divides both of the first numbers, by working up the chain of equations one step at a time. (You can make this into a proof using the Principle of Mathematical Induction, too.) Put these two parts together to conclude that the greatest common divisor of the two numbers equals the last divisor in the Euclidean Algorithm. - 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-2015 The Math Forum
http://mathforum.org/dr.math/