How to find Greatest Common Factor of whole numbers?

Posted on 2007-07-24
Last Modified: 2012-05-05
Please provide procedure for finding Greatest Common Factor(GCM) of whole numbers.  For example, what is the GCM of 27 and 72.
Question by:naseeam
    LVL 84

    Expert Comment

    LVL 84

    Expert Comment


    Author Comment

    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.
    LVL 53

    Accepted Solution

    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 :


    The algorithms that ozo posted are more advanced, and are preferrable for bigger numbers. The technique I illustrated is only feasible for small numbers.
    LVL 10

    Assisted Solution

    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.
    LVL 84

    Assisted Solution

    LVL 84

    Assisted Solution

    LVL 22

    Assisted Solution

    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

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Threat Intelligence Starter Resources

    Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

    Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! How to Know You are Making a Difference at EE In August, 2013, one …
    Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
    This video discusses moving either the default database or any database to a new volume.
    In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

    758 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    10 Experts available now in Live!

    Get 1:1 Help Now