How do you find the greatest common factor?

Answer 1

First Method: Clearly, one way to find the 'greatest common factor' of two or more integers would be to find all their factors, and hence all their common factors, and hence their highest common factor.

For example, find the GCF of 54 and 24:

Factors of 54: 1, 2, 3, 6, 9, 18, 27, 54.

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24.

Common factors of 54 and 24: 1, 2, 3, 6.

So the GCF of 54 and 24 is 6.

Second method: However, if we appreciate the basic properties of prime numbers, we can arrive at a rather faster method. This will be easiest to illustrate using an example. Suppose we want the GCF of 8190 and 693.

We start by writing each number as a product of primes; i.e. we find its prime factorization.

8190 = 2 x 3 x 3 x 5 x 7 x 13

693 = 3 x 3 x 7 x 11

By multiplying different combinations of the primefactors of each number we can find all of its factors. It follows that we can find our GCF by multiplying together all the primes common to each factorization.

In this case these shared prime factors are 3,3,7.

3 x 3 x 7 = 63.

So 63 is the GCF of 8190 and 693.

An Extra Example

The Greatest Common Factor (GCF) is the largest factor common to two or more numbers. For example, 34 is the GCF of 68 and 102 because it is the largest number that is a factor common to both numbers.

Factors of 68: 1 2 4 17 34 68

Factors of 102: 1 2 3 6 17 34 51 102

The GCF of 68 and 102 is 34

Prime factors of 68 are 2, 2, and 17

Prime factors of 102 are 2, 3, and 17

The GCF of 68 and 102 is 2 x 17 = 34

Greatest Cake Formula.

The Greatest Cake Formula is where you start with the two numbers on the bottom. Make the dividing line above the two numbers like so:

5___6_

5 l25 30

The greatest common factor above is 5 because there is nothing above it to multiply to find the GCF!

Division Ladders (very easy)

Division Ladders are useful for finding Greatest Common Factors, also known as Greatest Common Divisors. If your math problem is Find the GCF of 32, 24, and 40 using a Division Ladder, you would find the answer quickly and easily:

2 |32, 24, 40

, |_________

2 |16, 12, 20

, |________

2 | 8, 6, 10

, |_________

, 4, 3, 5

You would be dividing by 2 in this case, then multiply your divisors, 2x2x2 = 8. Your Greatest Common Factor for 32, 24, and 40 is 8. I used the commas for placeholders, as without them, the vertical lines don't line up.

Euclid's algorithm

1. Let the two numbers be N1 and N2

2. Divide N1 by N2 to get a quotient (which is ignored) and a remainder R;

3. If the remainder R is not zero: replace N1 by N2; replace N2 by R; Repeat from Step 2

4. The GCF is N2

Example: gcf(90, 252)

1. N1 = 90, N2 = 252

2. N1 ÷ N2 = 90 ÷ 252 = [0] R = 90

3. R is not zero: N1 = 252; N2 = 90

2. 252 ÷ 90 = [2] R = 72

3. R is not zero; N1 = 90; N2 = 72

2. 90 ÷ 72 = [1] R = 18

3. R is not zero; N1 = 72; N2 = 18

2. 72 ÷ 18 = [4] R = 0

3. R is zero

4 GCF is N2 = 18.

The prime factorization of the two numbers (in power format)

Factorize the two (or more) numbers into power format.

Multiply the lowest power of each of the common primes together to get the GCF. If there are no common primes, the GCF is 1.

Example: gcf(90, 252)

90 = 2 x 3^2 x 5

252 = 2^2 x 3^2 x 7

Common primes are 2 and 3; lowest power of 2 is 2; lowest power of 3 is 3:

gcf = 2 x 3^2 = 18
Example: 30 and 42

Factor them.

2 x 3 x 5 = 30

2 x 3 x 7 = 42

Select the common factors.

2 x 3 = 6, the GCF
Any of the following methods:

1) Trial and error (find the factors of one number, check which are factors of the other one).

2) Find the prime factors for each number. See which prime factors are in common.

3) For larger numbers, it is most efficient to use Euclid's algorithm. For example, the greatest common factor of 14 and 10 is the same as the greatest common factor of 10 and 4 - where 4 is calculated as 14 minus 10 (or better, as the remainder of the division of 14 / 10).

4) Or use Google.

Alternative Method

Divide the larger of the two numbers by the smaller one.

If there is no remainder, the dividend is the answer.

If there is a remainder, then divide the dividend by the remainder.

Repeat until there is no remainder.

Then the answer is the dividend.
Example: 30 and 42

Factor them.

2 x 3 x 5 = 30

2 x 3 x 7 = 42

Select the common factors.

2 x 3 = 6, the HCF
Example: 30 and 42

Factor them.

2 x 3 x 5 = 30

2 x 3 x 7 = 42

Select the common factors.

2 x 3 = 6, the GCF

Answer 2

The C in HCF stands for Common, so you need at least two things - numbers or expression - before you can find an HCF that is common to them.

The basic process for finding the HCF of two numbers (or expression) is as follows:

Find the prime factorisation for each number.

Select those factors that are common to both numbers.

Multiply these factors together.

The procedure is the same for three or more numbers or expressions except that the factors need to be common to each one of the numbers.

You do not need to go down to the level of prime factors. As you get more experienced, you may chose larger common factors instead.

For example, to find HCF of 60 and 72.

60 = 2*2*3*5

72 = 2*2*2*3*3

The common factors are 2, 2 and 3 so the HCF is 2*2*3 = 12.

Here's a tip for simplifying the hunt for HCF. If your starting numbers are large and you cannot work out their factors easily (or just to make life simpler for yourself), you can always subtract the smaller number from the larger and replace the larger number with this difference. You can use the process through a few loops and then go back to factorisation if that suits.

So, again starting with 60 and 72

Larger minus smaller = 72 - 60 = 12

So replace 72 by 12 and so the required answer is the HCF of 60 and 12

Now, larger minus smaller = 60 - 12 = 48

So replace 60 by 48 and so the answer is the HCF of 48 and 12

Now, larger minus smaller = 48 - 12 = 36

So replace 48 by 36 and so the answer is the HCF of 36 and 12

Now, larger minus smaller = 36 - 12 = 24

So replace 36 by 24 and so the answer is the HCF of 24 and 12

Now, larger minus smaller = 24 - 12 = 12

So replace 24 by 12 and so the answer is the HCF of 12 and 12

But the HCF of a number and itself is the number. So that's the answer. Factorisation completely replaced by subtraction!

Answer 3

-- list all factors of the first number

-- list all factors of the other number

-- find the biggest number that appears on both lists