Find the greatest common factor (GCD)

I assume you mean the greatest common divisor of integers a and b, 
the largest integer that divides both of a and b.  It can be 
calculated using a 2300 year old method called Euclid's algorithm.

I'll explain the algorithm with an example.  Let's find the gcd of 
210 and 990.

Divide 990 by 210:  quotient 4, remainder 150; ignore quotient
Divide divisor from previous step by remainder from previous step
   divide 210 by 150: quotient 1, remainder 60; ignore quotient
Divide divisor from previous step by remainder from previous step
   divide 150 by 60: quotient 2, remainder 30; ignore quotient
Divide divisor from previous step by remainder from previous step
   divide 60 by 30: quotient 2, remainder 0.

When the remainder becomes 0, as it always will, then go to the 
previous step and choose the remainder, in this case 30.  This is the 
gcd!  Neat!

The step of dividing and ignoring the quotient can be done on many 
calculators, using the MOD operation.  For example, on my calculator 
(an HP48G), I enter 990 and 210 and press MOD.  I get 150 on the 
screen.

-Doctor Jerry,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   
Reference : http://mathforum.org/library/drmath/view/58554.html
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s