Greatest Common Factor

Date: 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/