The Highest Common Factor

The highest common factor (HCF) of two or more numbers is the largest number that is a commo factor of the numbers.
To find it, write down the numbers as their prime factors. Then choose those factors that appear in all of the numbers.

Let’s look at some examples.

Example

Find the HCF of the numbers 15, 24 and 30.

15=3\times 5
24=2\times 2\times 2\times 3
30=2\times 2\times 5
We see that 3 is common in them all. So the HCF is 3.


Example

Find the HCF pf the numbers 16, 24, 72 and 80.

Here 16=2\times 2\times 2\times 2
124=2\times 2\times 2\times 2\times 3
72=2\times 2\times 2\times 3\times 3
80=2\times 2\times 2\times 2\times 5
We see that 2\times 2\times 2 appears in them all, hence the HCF is 8.
Even with bigger numbers we proceed in the same manner.


Example

Find the HCF of 1245 and 3000.

To find the prime factors, we use the method of long division.
3|1245
5|415
83|83
1
And
2|3000
2|2500
2|750
3|375
5|125
5|25
5|5
1
So, we have 1245=3\times 5\times 83 and
3000=2\times 2\times 2\times 3\times 5\times 5\times 5
This means 3\times 5 is common in both, therefore HCF is 3\times 5=15


Example

The next example is taken from a Cambridge past examination paper.

The numbers 168 and 324, written as the products of their prime factors are

168={ 2 }^{ 2 }\times 3\times 7

324={ 2 }^{ 2 }\times { 3 }^{ 4 }

Find:

1. \sqrt { 324 }

2. The largest integer which is a factor of both 168 and 324.

3. The smallest positive integer value of n for which 168n is a multiple of 324.

1. \sqrt { 324 } =\sqrt { { 2 }^{ 2 }\times { 3 }^{ 4 } }

{ 2 }^{ 1 }\times { 3 }^{ 2 }

=2\times 9

=18

2. We see { 2 }^{ 2 }\times 3=12

3. Compare 168={ 2 }^{ 3 }\times 3\times 7 and 324={ 2 }^{ 2 }\times { 3 }^{ 4 }

To find the smallest positive integer value of n for which 168n is a multiple of 324.

We write 168n={ 2 }^{ 3 }\times 3\times 7\times n

To be a multiple of 324={ 2 }^{ 2 }\times { 3 }^{ 4 } should be a factor of { 2 }^{ 3 }\times 3\times 7\times n and

\frac { 168n }{ 324 } \quad = a whole number,

\frac { { 2 }^{ 3 }\times 3\times 7\times n }{ { 2 }^{ 2 }\times { 3 }^{ 4 } } \quad = a whole number

\frac { 2\times 7\times n }{ { 3 }^{ 3 } } \quad = a whole number

So that, we should choose n={ 3 }^{ 2 }=27 to make the division a whole number answer.


Example

Find the H.C.F of 210,315 and 650.

We first find the prime factors of 210:

2|210

3|105

*** QuickLaTeX cannot compile formula:
5|35</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

7|7
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

1
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">Then for 315:</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

3|315
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

3|105
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

5|35
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

7|7
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

1
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">Then for 650:</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

2|650
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

5|325
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

5|65
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

13|13
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

1
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">So,</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

210=2 \times 3 \times 5 \times 7
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

315=3 \times 3 \times 5 \times 7
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

650=2 \times 5 \times 5 \times 13
*** QuickLaTeX cannot compile formula:
</span>
<span style="color: #000000;">

*** Error message:
You can't use `macro parameter character #' in math mode.
leading text: <span style="color: #

HCF of 210, 315 and 650 = 5$