Greatest Common FactorDate: 03/28/97 at 01:09:08 From: Andy Subject: Greatest Common Factor How do you find the greatest common factor? Date: 04/01/97 at 19:02:55 From: Doctor Steven Subject: Re: Greatest Common Factor Donald Knuth has come up with an extremely easy to understand algorithm to compute the greatest common factor of two numbers. It goes like this: First, the symbol for the greatest common factor of two numbers, M and N, is: gcd(M, N) Now say you want to find the greatest common factor of two numbers M and N: If M is an even number and N is an even number then: gcd(M, N) = 2 * gcd( M/2, N/2 ) If M is an even number and N is an odd number then: gcd(M, N) = gcd( M/2, N ) If M is an odd number and N is an even number then: gcd(M, N) = gcd( M, N/2 ) If both M and N are odd then: gcd(M, N) = gcd( (M-N)/2, N) Iterating these properties will give you the greatest common factor. Let's use this method on these two numbers: 44305, and 42355 gcd( 44305, 42355 ) = gcd( (44305 - 42355)/2, 42355 ) = gcd( 975, 42355 ) = gcd( 975, (42355 - 975)/2 ) = gcd( 975, 20690 ) = gcd( 975, 10345 ) = gcd( 975, (10345 - 975)/2 ) = gcd( 975, 4685 ) = gcd( 975, (4685 - 975)/2 ) = gcd( 975, 1855 ) = gcd( 975, (1855 - 975)/2 ) = gcd( 975, 440 ) = gcd( 975, 220 ) = gcd( 975, 110 ) = gcd( 975, 55 ) = gcd( 920/2, 55 ) = gcd( 460, 55 ) = gcd( 230, 55 ) = gcd( 115, 55 ) = gcd( 60/2, 55 ) = gcd( 30, 55 ) = gcd( 15, 55 ) = gcd( 15, 40/2 ) = gcd( 15, 20 ) = gcd(15, 10) = gcd(15, 5) = gcd( 5, 5 ) = 5. So 5 is the greatest common factor of these two numbers. Unfortunately this method can take a long while to do even though it is very easy, so this next method takes fewer steps: Say we have two numbers M and N, with M larger than N. Then create the chain like this: M = q_1*N + r_1 N = q_2*r_1 + r_2 r_1 = q_3*r_2 + r_3 . . . . r_(i-1) = r_i*q_(i+1) In this the r_i's are the remainders of the left side when divided by r_(i-1), and q_i is the quotient of the left side divided by r_(i-1). Lets try this method on the numbers above: 44305, 42355. 44305 = 1*42355 + 1950 42355 = 21*1950 + 1405 1950 = 1*1405 + 545 1405 = 2*545 + 315 545 = 1*315 + 230 315 = 1*230 + 85 230 = 2*85 + 60 85 = 1*60 + 25 60 = 2*25 + 10 25 = 2*10 + 5 10 = 2*5 So 5 is the greatest common factor. Hope this helps. -Doctor Steven, The Math Forum Check out our web site! 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/