Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Formula for Greatest Common Divisor


Date: 01/08/97 at 01:43:54
From: Sandra O. Follett
Subject: Formulas/equations

Is there a formula to get the greatest common factor?

Thanks, S.F.


Date: 01/08/97 at 08:40:22
From: Doctor Jerry
Subject: Re: Formulas/equations

Hi Sandra,

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/   


Date: 01/08/97 at 14:57:38
From: Follett
Subject: Re: Formulas/equations

Dear Jerry,

Thanks!  I volunteer at a local elementary school sometimes, and its 
neat to to leave them with a number trick or two.  I happen to know 
the eighth grade will be having a test on this subject soon.  You know  
that kids remember tricks and stories a lot longer than lessons and 
diagrams.

Thanks again.

Sandra
    
Associated Topics:
Elementary Division
Middle School Division
Middle School Factoring Numbers

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/