1. ## Greatest Common Factor

Is there an equation for the greatest common factor of two numbers?

2. Originally Posted by Quick
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 $\displaystyle 2^2 \cdot 3 \cdot 5$.
The prime factorization of 630 is $\displaystyle 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 ($\displaystyle 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) = $\displaystyle 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.

3. Originally Posted by topsquark
Equation, not that I know of. Process, yes.

Consider the GCF of 60 and 630.

The prime factorization of 60 is $\displaystyle 2^2 \cdot 3 \cdot 5$.
The prime factorization of 630 is $\displaystyle 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 ($\displaystyle 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) = $\displaystyle 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 $\displaystyle 2^2 \cdot 3 \cdot 5$.
The prime factorization of 630 is $\displaystyle 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) = $\displaystyle 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

4. Originally Posted by topsquark
...
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 :

5. 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.

6. Originally Posted by ThePerfectHacker
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)