# How do you quickly find the Greatest Common Factor?

• Jun 4th 2010, 01:51 AM
Layman
How do you quickly find the Greatest Common Factor?
Lets say I want to reduce a fraction to it's lowest terms.

For instance

14
42
OK that one is easy, all I have to do is write out al the factors like this;

Factors of 14 = 1,2,7,14

Factors of 42 = 1,2,3,6,7,14

We can see that 14 is the greatest factor common to both thhe numerator and the denominator. I then divide the numerator and the denominator by the highest common factor like this;

14 / 14 = 1
42 / 14 = 3

Which gives me my answer. So that one was straightforward. The problem comes when I am faced with something like;

240
165

Are there any tricks that enable you to quickly find out the greatest common factor of larger numbers?
• Jun 4th 2010, 02:58 AM
Prove It
Quote:

Originally Posted by Layman
Lets say I want to reduce a fraction to it's lowest terms.

For instance

14
42
OK that one is easy, all I have to do is write out al the factors like this;

Factors of 14 = 1,2,7,14

Factors of 42 = 1,2,3,6,7,14

We can see that 14 is the greatest factor common to both thhe numerator and the denominator. I then divide the numerator and the denominator by the highest common factor like this;

14 / 14 = 1
42 / 14 = 3

Which gives me my answer. So that one was straightforward. The problem comes when I am faced with something like;

240
165

Are there any tricks that enable you to quickly find out the greatest common factor of larger numbers?

Divisibility Tests:

Divisibility rule - Wikipedia, the free encyclopedia
• Jun 4th 2010, 04:09 AM
e^(i*pi)
Quote:

Originally Posted by Layman
Lets say I want to reduce a fraction to it's lowest terms.

For instance

14
42
OK that one is easy, all I have to do is write out al the factors like this;

Factors of 14 = 1,2,7,14

Factors of 42 = 1,2,3,6,7,14

We can see that 14 is the greatest factor common to both thhe numerator and the denominator. I then divide the numerator and the denominator by the highest common factor like this;

14 / 14 = 1
42 / 14 = 3

Which gives me my answer. So that one was straightforward. The problem comes when I am faced with something like;

240
165

Are there any tricks that enable you to quickly find out the greatest common factor of larger numbers?

Test which numbers will divide.

For example 5 is a factor of 240 and 165

$\displaystyle \frac{240}{165} \div \frac{5}{5} = \frac{48}{33}$

Since 3 is a factor of 48 and 33 we get

$\displaystyle \frac{48}{33} \div \frac{3}{3} = \frac{16}{11}$

Since 11 is prime this is now in it's lowest terms. The greatest common factor is the numbers you cancelled by multiplied, in this case $\displaystyle 3 \times 5 = 15$

----------------------------------------------------

Another way is to use prime factors

$\displaystyle 240 = 2^4 \times 3 \times 5$

$\displaystyle 165 = 3 \times 5 \times 11$

The GCF is the product of each number that appears in both factorisations. In this case $\displaystyle 3 \times 5 = 15$
• Jun 4th 2010, 04:11 AM
Opalg
Quote:

Originally Posted by Layman
Are there any tricks that enable you to quickly find out the greatest common factor of larger numbers?

For large numbers, the most efficient process to use is Euclid's algorithm.