Highest Common Factor (H.C.F)

Sup­pose you have $24$ pen­cils and $36$ erasers and want to make iden­ti­cal gift packs with noth­ing left over. The largest num­ber of packs you can make is the High­est Com­mon Fac­tor of $24$ and $36$. The same idea helps you sim­plify frac­tions, cut rib­bons into equal lengths and tile a floor with the largest square tiles. This les­son shows three ways to find it and explains why each one works.

Fac­tors and com­mon fac­tors

A fac­tor of a num­ber goes into it exactly. It leaves noth­ing over. You have made lists of them already. The fac­tors of $6$ are $1, 2, 3$ and $6$. The fac­tors of $12$ are $1, 2, 3, 4, 6$ and $12$.

Put two lists side by side. Some num­bers turn up in both. Those are the com­mon fac­tors. This les­son is about the biggest one. It shows three ways to find it. Two of them skip the lists.

What the H.C.F is

Def­i­n­i­tion. Take two or more num­bers. Find the fac­tors they share. The biggest one is called the High­est Com­mon Fac­tor (H.C.F). It is also called the Great­est Com­mon Divi­sor (G.C.D).

The two names mean the same thing. A fac­tor is also called a divi­sor. So the names are two labels for one idea. You will meet both. Use the one you are asked for.

Two things are true before you work any­thing out. Every num­ber has $1$ as a fac­tor. So $1$ is a com­mon fac­tor of any set. That means there is always an answer.

No fac­tor of a num­ber is big­ger than the num­ber. So the H.C.F is never big­ger than the small­est num­ber you were given. The answer sits between $1$ and that small­est num­ber.

Exam­ple 1: the H.C.F of 6 and 8

1st method (By writ­ing all fac­tors)

Write out every fac­tor of each num­ber.

Now read the two lists together. $1$ is in both. $2$ is in both. $3$ is in the first list only. $4$ and $8$ are in the sec­ond list only. So the com­mon fac­tors are $1$ and $2$. The big­ger one is $2$. The H.C.F of $6$ and $8$ is $2$.

A Venn dia­gram shows the same read­ing at a glance. Each cir­cle holds the fac­tors of one num­ber, and the over­lap holds the fac­tors they share.

This method just does what H.C.F means. You write out the fac­tors. You pick the ones both num­bers share. You take the biggest of those. Noth­ing is hid­den in it. That is why it is worth learn­ing first. Its weak point is the work. A num­ber like $84$ has twelve fac­tors. Writ­ing all twelve with­out miss­ing one takes care. The next two ways need less writ­ing.

2nd method (Prime fac­tor­iza­tion method)

To prime fac­torise a num­ber is to write it as primes mul­ti­plied together. The work­ing below does that for $6$ and for $8$. Here are the steps the acad­emy gives, said in shorter sen­tences. First prime fac­torise the given num­bers. Then take out the com­mon fac­tors and mul­ti­ply them. That gives you the H.C.F of the given num­bers.

H.C.F of 6 and 8

$$\begin{aligned}6 &= 2 \times 3 \\ 8 &= 2 \times 2 \times 2 \\ \text{H.C.F} &= 2\end{aligned}$$

Count what each num­ber can spare. $6$ holds one $2$ and one $3$. $8$ holds three $2$s and no $3$. The $3$ can­not be used. $8$ has none to give. The $2$ can be used once. $6$ has only one to give. What is left is a sin­gle $2$.

Here is why that count­ing works. A com­pos­ite num­ber is one you can build by mul­ti­ply­ing smaller num­bers. $6$ and $8$ are both com­pos­ite. Every com­pos­ite num­ber breaks into primes in one way only. So any­thing that divides $6$ is built from $6$'s own primes. That means a $2$, or a $3$, or both. Any­thing that divides $8$ is built from $8$'s primes. Those are all $2$s.

So a num­ber that divides both is built from $2$s alone. But $6$ has only one $2$ to give. So it can use only one $2$. Here is the rule that comes out of that. Look at each prime the num­bers share. Count how many of it each num­ber holds. Then take it as many times as the small­est count. Do that, and you have built the biggest com­mon fac­tor there is.

3rd method (Divi­sion method)

Two words come first. The rule below turns on them. You do this method line by line. On each line you divide by some num­ber. That num­ber is the divi­sor of the line. What is left over is the remain­der. In $8 \div 6$ the divi­sor is $6$ and the remain­der is $2$.

In the rule below, a divi­sor does not have to go in exactly. $6$ is not a fac­tor of $8$. It is still the divi­sor of that line. A divi­sor of this kind is just the num­ber you divided by. That is the sense the rule uses when it talks about a divi­sor.

Here are the steps the acad­emy gives, said in shorter sen­tences. Divide the greater num­ber by the smaller one. Then divide the divi­sor by the remain­der. Go on divid­ing the divi­sor of the line above by the remain­der. Stop when the remain­der is zero. The divi­sor on that last line is the H.C.F of the given num­bers. That is what the rule calls the last divi­sor.

Read it down­wards. Eight divided by six leaves $2$. So six is divided by $2$ next. That leaves noth­ing. You stop there. The last divi­sor was $2$. The H.C.F of $6$ and $8$ is $2$. The other two meth­ods gave the same answer.

There is also a pic­ture behind the divi­sion method. Take a rec­tan­gle $8$ units wide and $6$ units tall. Cut off the largest square you can, a $6$ by $6$ one. What is left is a strip $2$ units wide, and $2$ by $2$ squares fill it exactly. Squares of side $2$ there­fore tile the whole rec­tan­gle, and no larger square can.

Here is why the shrink­ing is safe. The first line says $8 = 6 + 2$. Take $6$ away from both sides. That gives $2 = 8 - 6$. Now pick any num­ber that divides $8$ and also divides $6$. It goes into the whole $8$. It goes into the $6$ inside it. So it must go into the $2$ that is left over.

Now go the other way. Take a num­ber that divides $6$ and $2$. It divides $6 + 2 = 8$ as well. So the pair $8$ and $6$ has the same com­mon fac­tors as the pair $6$ and $2$.

Every line swaps the num­bers for smaller ones. The answer stays the same. In the end the remain­der reaches $0$. The last divi­sor then goes into the num­ber above it exactly. That divi­sor is the H.C.F.

Remem­ber. The divi­sion method never asks you to list a fac­tor. It only asks you to divide. The num­bers get smaller at every step. Reach for it when the num­bers are large.

Exam­ple 2: the H.C.F of 24, 36 and 84

1st method (By writ­ing all fac­tors)

Three lists this time. Each one is built with the pair­ing method from Mul­ti­ples and fac­tors. They are printed in full here. You read the H.C.F straight off them.

Two of those lists are not the same as the sheet's. That is worth say­ing plainly. The sheet leaves $6$ out of the fac­tors of $24$. But $6$ belongs there, as $24 \div 6 = 4$ exactly.

The sheet also prints $26$ among the fac­tors of $84$. The num­ber that belongs there is $28$. $26$ goes three times into $84$ and leaves $6$ over. And $84 \div 28 = 3$ exactly.

Look for the num­bers in all three lists. $1, 2, 3, 4, 6$ and $12$ are in all three. $8$ is in the first list but not the sec­ond. $9$ is in the sec­ond but not the first. $7$ is in the third alone. So the com­mon fac­tors are $1, 2, 3, 4, 6, 12$. The H.C.F is $12$.

Check it by divid­ing. Every divi­sion must come out exactly.

Noth­ing big­ger will do. The only fac­tor of $24$ above $12$ is $24$ itself. And $24$ does not divide $36$. It goes once into $36$ and leaves $12$ over.

2nd method (Prime fac­tor­iza­tion method)

H.C.F of 24, 36 and 84

$$\begin{aligned}24 &= 2 \times 2 \times 2 \times 3 \\ 36 &= 2 \times 2 \times 3 \times 3 \\ 84 &= 2 \times 2 \times 3 \times 7 \\ \text{H.C.F} &= 2 \times 2 \times 3 \\ &= 12\end{aligned}$$

Count the primes again. Start with the $2$s. $24$ has three, $36$ has two and $84$ has two. The small­est count is two. So two $2$s may be taken.

Now the $3$s. $24$ has one, $36$ has two and $84$ has one. The small­est count is one. So one $3$ may be taken. The $7$ is in $84$ alone. The spare $2$ in $24$ has no part­ner. Nei­ther one can be used. Mul­ti­ply what is left: $2 \times 2 \times 3 = 12$.

3rd method (Divi­sion method)

The divi­sion method works on two num­bers at a time. So start with two of them. Take $24$ and $84$. Bring the third one in after that.

The last divi­sor is $12$. Now con­sider $12$ and $36$.

The remain­der is $0$ at the first step. So the last divi­sor is $12$. The H.C.F of $24$, $36$ and $84$ is $12$.

Why may you work two at a time? The chain of remain­ders above shows it. Every num­ber that divides $24$ and $84$ divides $12$ as well. And the num­bers that divide $12$ are $1, 2, 3, 4, 6$ and $12$. There are no oth­ers.

So you do not have to ask what all three num­bers share. You may ask what $12$ and $36$ share instead. The answer comes out the same.

Remem­ber. All three meth­ods must give the same answer. If two of them dis­agree, one of your lists is short. Go back and find what you missed.

Exam­ple 3: the H.C.F of 48 and 180

This extra exam­ple uses larger num­bers, where the divi­sion method really earns its place.

Prime fac­tor­iza­tion method

$$\begin{aligned}48 &= 2 \times 2 \times 2 \times 2 \times 3 \\ 180 &= 2 \times 2 \times 3 \times 3 \times 5 \\ \text{H.C.F} &= 2 \times 2 \times 3 = 12\end{aligned}$$

$48$ has four $2$s and $180$ has two, so two are taken. Each has at least one $3$, so one is taken. The $5$ is in $180$ only.

Divi­sion method

The last divi­sor is $12$, which agrees. Check: $48 \div 12 = 4$ and $180 \div 12 = 15$, and $4$ and $15$ share no fac­tor but $1$.

Back to the gift packs from the start of the les­son: the H.C.F of $24$ and $36$ is $12$, so you can make $12$ packs, each with $2$ pen­cils and $3$ erasers.

When the H.C.F is 1

$4$ and $5$ are coprimes. So are $2$ and $3$. Those two pairs have a sec­ond name as well. You may also call them rel­a­tively prime. Both names are taught in Per­fect num­bers, coprimes and twin primes.

Their H.C.F can only be $1$. The fac­tor lists show why.

The only num­ber in both lists is $1$. The divi­sion method lands in the same place.

There is a short way to write an H.C.F. You put the num­bers in brack­ets, like this: $\text{H.C.F}(4, 5) = 1$. You read it aloud as "the H.C.F of $4$ and $5$ is $1$".

The acad­emy closes its H.C.F part in let­ters. It says $a$ and $b$ are rel­a­tively prime, or coprimes. And it says the G.C.D of $(a, b)$ is $1$. In the short way above, that is $\text{G.C.D}(a, b) = 1$.

A let­ter stands for a num­ber you have not been told. Let­ters that stand for num­bers sets that out. So $a$ and $b$ are any two num­bers you pick. That one line cov­ers every coprime pair at once. The two lines above cover only $4$ and $5$ and $2$ and $3$.

An H.C.F of $1$ is not a fail­ure. It is not a sign that you went wrong. It is the answer. And it tells you some­thing worth know­ing. The two num­bers share noth­ing at all.

Remem­ber. Two num­bers that are coprime — rel­a­tively prime — have an H.C.F of $1$. In let­ters, $\text{G.C.D}(a, b) = 1$.

Your turn

Do the first two by all three meth­ods. Watch them agree. For the rest, the divi­sion method is quick­est.

From the sheet

1. Find the H.C.F of 52 and 48
2. Find the H.C.F of 15 and 35
3. Find the H.C.F of 36, 48 and 52
4. Find the H.C.F of 60, 128 and 180

Extra prac­tice, beyond the sheet

The acad­e­my's sheet does not set these. They are more ques­tions of the same kind. Use them when you want more drill. Find the H.C.F of each pair.

When you have an answer, check it before you move on. Divide each of the given num­bers by it. Every divi­sion must come out exactly. Noth­ing may be left over. And if a big­ger num­ber does the same, your answer was not the high­est.

Com­mon mis­takes

• Miss­ing a fac­tor when list­ing, as the sheet itself did with $6$ for $24$. Pair the fac­tors to make sure none is lost.
• Tak­ing the largest count of a prime instead of the small­est. That builds the L.C.M, not the H.C.F.
• Stop­ping the divi­sion method too early, before the remain­der is $0$.
• Giv­ing the last remain­der instead of the last divi­sor. The remain­der at the end is always $0$.
• Giv­ing an answer big­ger than the small­est given num­ber. The H.C.F can never be larger than that.
• Think­ing an H.C.F of $1$ means a mis­take. Coprime num­bers have H.C.F $1$.

Key terms

Fac­tor (divi­sor)

A num­ber that goes into another exactly, leav­ing noth­ing over.

Com­mon fac­tor

A fac­tor shared by two or more num­bers.

H.C.F (G.C.D)

The biggest com­mon fac­tor of the given num­bers.

Prime fac­tori­sa­tion

Writ­ing a num­ber as primes mul­ti­plied together.

Remain­der

What is left over after a divi­sion.

Coprimes (rel­a­tively prime)

Num­bers whose H.C.F is $1$.

Answers

From the sheet

1. $4$. Fac­tors: $52$ has $1, 2, 4, 13, 26, 52$; $48$ has $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$; the com­mon ones are $1, 2, 4$. Primes: $52 = 2 \times 2 \times 13$ and $48 = 2 \times 2 \times 2 \times 2 \times 3$, shar­ing $2 \times 2$. Divi­sion: $52 \div 48$ leaves $4$, and $48 \div 4$ leaves $0$.
2. $5$. Fac­tors: $15$ has $1, 3, 5, 15$; $35$ has $1, 5, 7, 35$. Primes: $15 = 3 \times 5$, $35 = 5 \times 7$. Divi­sion: $35 \div 15$ leaves $5$, and $15 \div 5$ leaves $0$.
3. $4$. $48 \div 36$ leaves $12$, $36 \div 12$ leaves $0$; then $52 \div 12$ leaves $4$, $12 \div 4$ leaves $0$.
4. $4$. $128 \div 60$ leaves $8$, $60 \div 8$ leaves $4$, $8 \div 4$ leaves $0$; and $180 \div 4 = 45$ exactly.

Extra prac­tice

1. $6$
2. $15$
3. $24$
4. $7$ ($154 \div 105$ leaves $49$, $105 \div 49$ leaves $7$, $49 \div 7$ leaves $0$)
5. $1$, so $8$ and $15$ are coprime
6. $1$, so $21$ and $22$ are coprime
7. $8$
8. $9$
9. $13$