Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Algorithms
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search