Results 1 to 6 of 6

Math Help - Greatest Common Factor

  1. #1
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024

    Greatest Common Factor

    Is there an equation for the greatest common factor of two numbers?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,821
    Thanks
    317
    Awards
    1
    Quote Originally Posted by Quick View Post
    Is there an equation for the greatest common factor of two numbers?
    Equation, not that I know of. Process, yes.

    Consider the GCF of 60 and 630.

    The prime factorization of 60 is 2^2 \cdot 3 \cdot 5.
    The prime factorization of 630 is 2 \cdot 3^2 \cdot 5 \cdot 7.

    The GCF (also known as the Greatest Common Divisor, GCD) will be the number that has a prime factorization that contains the same prime factors as the combination of the lists. In other words,
    There is a factor of 2 common to each,
    there is a factor of 3 common to each,
    there is a factor of 5 common to each.

    Thus GCF(60, 630) = 2*3*5 = 30.

    If we were talking about GCF(60, 1260) then ( 1260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7):
    There are two factors of 2 common to each,
    there is a factor of 3 common to each,
    there is a factor of 5 common to each.

    Thus GCF(60, 1260) = 2^2 \cdot 3 \cdot 5 = 60.

    -Dan

    PS Now that I think of it, there is a formula, but it isn't anything direct:
    Given two numbers x and y, we know that GCF(x, y) = (x*y)/LCM(x, y), where LCM(x, y) is the "Least Common Multiple" of x and y. There is no direct formula I know of to find the LCM either.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,821
    Thanks
    317
    Awards
    1
    Quote Originally Posted by topsquark View Post
    Equation, not that I know of. Process, yes.

    Consider the GCF of 60 and 630.

    The prime factorization of 60 is 2^2 \cdot 3 \cdot 5.
    The prime factorization of 630 is 2 \cdot 3^2 \cdot 5 \cdot 7.

    The GCF (also known as the Greatest Common Divisor, GCD) will be the number that has a prime factorization that contains the same prime factors as the combination of the lists. In other words,
    There is a factor of 2 common to each,
    there is a factor of 3 common to each,
    there is a factor of 5 common to each.

    Thus GCF(60, 630) = 2*3*5 = 30.

    If we were talking about GCF(60, 1260) then ( 1260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7):
    There are two factors of 2 common to each,
    there is a factor of 3 common to each,
    there is a factor of 5 common to each.

    Thus GCF(60, 1260) = 2^2 \cdot 3 \cdot 5 = 60.

    -Dan

    PS Now that I think of it, there is a formula, but it isn't anything direct:
    Given two numbers x and y, we know that GCF(x, y) = (x*y)/LCM(x, y), where LCM(x, y) is the "Least Common Multiple" of x and y. There is no direct formula I know of to find the LCM either.
    In case you were wondering there is a simple process to find the LCM of two numbers as well. Let's take 60 and 630 again.

    The prime factorization of 60 is 2^2 \cdot 3 \cdot 5.
    The prime factorization of 630 is 2 \cdot 3^2 \cdot 5 \cdot 7.

    The Least Common Multiple will have a prime factorization that is the smallest list of prime factors that completely contains both lists. In other words:
    There are two factors of 2,
    there are two factors of 3,
    There is one factor of 5,
    There is one factor of 7.

    Thus LCM(60, 630) = 2^2 \cdot 3^2 \cdot 5 \cdot 7 = 1260.

    (And we can check the equation I gave in the Post Script of the last post:
    GCF(60, 630) = (60*630)/LCM(60, 630) = 37800/1260 = 30 as we found in the last post.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,829
    Thanks
    123
    Quote Originally Posted by topsquark View Post
    ...
    The Least Common Multiple will have a prime factorization that is the smallest list of prime factors that completely contains both lists. ...
    Hi,

    I taught my pupils an algorithm to calculate the LCM in a tabel: This method works too when you have more than two numbers (for instance when you calculate the sum of fractions). You only have to know the first 20 prime-factors :
    Attached Thumbnails Attached Thumbnails Greatest Common Factor-algorithm_lcm.gif  
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    This seems to be an excellent question for Quicklopedia, my method doth no rely on factorization. Rather on an algorithm (with amazing complexity i.e. really fast) called Euclidean algorithm. I can show it to thee.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by ThePerfectHacker View Post
    This seems to be an excellent question for Quicklopedia, my method doth no rely on factorization. Rather on an algorithm (with amazing complexity i.e. really fast) called Euclidean algorithm. I can show it to thee.
    Actually, for once I found wikipedia gave a good definition (actually, it gave a poor definition for it, but an excellent summary in the "Greatest Common Denominator" section)

    Anyway, thanks for your posts
    I'm one step closer to makeing an automatic quadratic factor thing in excel!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find the Greatest Common Factor
    Posted in the Algebra Forum
    Replies: 3
    Last Post: August 11th 2011, 11:19 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  3. greatest and least common factor
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 3rd 2010, 02:21 PM
  4. Replies: 3
    Last Post: June 4th 2010, 04:11 AM
  5. Replies: 2
    Last Post: March 14th 2009, 03:56 AM

Search Tags


/mathhelpforum @mathhelpforum