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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.