• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1820
  • Last Modified:

How to find Greatest Common Factor of whole numbers?

Please provide procedure for finding Greatest Common Factor(GCM) of whole numbers.  For example, what is the GCM of 27 and 72.
0
naseeam
Asked:
naseeam
5 Solutions
 
naseeamAuthor Commented:
In the first website above, I could not find any information on how to find Greatest Common Factor of two whole numbers.

The second website above is too advance for my needs.  I am asking a Fifth Grade Math question.
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
Infinity08Commented:
An easy way is to find the prime factors of both whole numbers. Then find all the divisors that are common for those numbers, and multiply them together - the result is the GCD or greatest common divisor.

Example for 27 and 72 :

27 = 3 * 3 * 3
72 = 2 * 2 * 2 * 3 * 3

The common divisors for 27 and 72 are thus 3 and 3 (twice), so the GCD is 3 * 3 = 9


Here's a more beginner friendly page :

        http://en.wikipedia.org/wiki/Gcd

The algorithms that ozo posted are more advanced, and are preferrable for bigger numbers. The technique I illustrated is only feasible for small numbers.
0
 
dragonjimCommented:
At the 5th grade level; your teacher is likely expecting something like Infinity08 provided.

1) List # = f1 * f2 * ... * fn (for each number)
2) simplify down to simpliest factors

         72 ----- 2 * 36
                             |------- 2 * 18
                                               |----------2 * 9
                                                                   |-------3 * 3

3) You arrive at Infinity08's approach above (2*2*2*3*3)

4) Do same for other number(s)

5) Multiply highest factor that is common to both lists (in this case 3*3 = 9)

6) For your level (5th grade)... test:
---> 27 / 9 = 3
---> 72 / 9 = 8


There are some other ways involving number layouts... I'll leave this to your teacher to show (as it often took 2 or 3 days for students to grasp when explained in class.

I'd hate to confuse you over the site.
0
 
NovaDenizenCommented:
First rule:  The GCD of 0 and any other number x is x.  GCD(0,x) = x
Second rule:  The GCD of any two nonzero numbers x and y is the same as (assuming x >= y) the GCD of (x modulo y) and y.  GCD(x,y) = GCD(x modulo y, y)

So, to solve GCD(27,72):
The second rule says that GCD(27,72) = GCD(72 modulo 27, 27)
72 modulo 27 = 18, so
GCD(27,72) = GCD(18,27)
Using the second rule again, GCD(18,27) = GCD(27 modulo 18, 18)
27 modulo 18 = 9
GCD(27,72) = GCD(18,27) = GCD (9,18) = GCD(18 modulo 9 ,9)
18 modulo 9 = 0
GCD(27,72) = GCD(18,27) = GCD (9,18) = GCD(0,9)

By the first rule, GCD(0,9) is 9.  Therefore GCD(27,72) = 9
0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now