Complements #9 LCM and HCF

With the exception perhaps of the quadratic formula, it seems to me that the method for finding the highest common factor and the lowest common multiple is the best (worst) example of really long methodology with zero understanding behind it. At least for students… and maybe for teachers too! So let’s take a closer look…

Lowest Common Multiple

The term itself means the first integer that your numbers will ‘go into’. In other words, the first integer to appear on what would be the times tables of each of your starting numbers. One might say this number is in fact… a common multiple (duh duh duuuuuh!)

You can of course just multiply the starting numbers together, and you will find *a* multiple of both of them, however it isn’t necessarily *the lowest* multiple.

Take 9 and 12 for example, 9 x 12 = 108. 108 is therefore a multiple of both 9 and 12, however the lowest multiple is 36 (9 x 4, or 12 x 3). You can rearrange both of those multiplication sums to make it clearer : 9 x 4 = 3 x 3 x 4, 12 x 3 = 3 x 4 x 3 = 3 x 3 x 4.

So the most laborious way to find the lowest common multiple would be to write out the times tables of both (or more than two if you’re feeling particularly ambitious) numbers until you find a matching answer. Bingo! But… that can be a long, long process, and mathematicians can be cleverer than that. We’ll come to a better method in a little while.

Highest Common Factor

Factors are numbers that you can multiply together to get your starting number. For example, if I start with 10, 5 x 2 = 10, so 5 and 2 are factors. Hence 10 appears in the times tables of both 5 and 2.

A Common Factor is a factor that is… errr… common to two (or more) starting numbers. For example, 2 is a common factor of both 4 and 10. In fact 2 is the Highest Common Factor (HCF) of both 4 and 10, because there is no greater integer that is a factor of both of these numbers.

We can write “2 is a factor of 10” as 2|10 … but we don’t in GCSE maths. But we do in the real world. “2 is a factor of 10” is also exactly the same as saying “2 is a divisor of 10”. In fact, Euclid called it a ‘common measure’. Bloody Euclid. Always different. Legend.

Students often get confused between the meaning of Highest Common Factor and Lowest Common Multiple, and often switch the terminology and think of the Highest Common Multiple and Lowest Common Factor. This is pretty daft in fairness, as there are infinite common multiples of any two (or more) numbers, and so Highest Common Multiple has no answer. Furthermore the Lowest Common Factor of any number is technically 1, which seems fairly pointless to work out if it’s *always* 1 (don’t get fussy on me with negatives and decimals).

Now that I’ve mentioned negatives, it’s a bit dangerous to ask “how many factors of 6 are there?” as instinct suggests these : 1 x 6, 2 x 3, thus 1, 2, 3 and 6 are factors.

However… -1 x -6, -2 x -3 also make 6, so they’re factors too. Or are they? It depends on who you talk to. Generally we only accept positive integers as factors, but some hardcore mathematicians argue negatives should be included.

So where do we draw the line? If we accept decimals as factors, then there are infinite factors for every integer. So… we don’t.

Algebraically, often we factorise which in essence is the process of creating a pair (or more!) of factors of an algebraic term:

x2 + 4x + 3 = (x + 3)(x + 1)

So (x + 3) and (x + 1) are both factors of x2 + 4x + 3, because they multiple together to equal it.

Ok let’s confuse things further with Prime Factors!

Prime Factors

Prime Factors are, confusingly, not really related much to factors. If you think back to Complements #4: Prime Numbers – you read that right? 😉 Then you’ll recall that every single integer is made up of prime numbers multiplied together. They’re the building blocks of other composite numbers.

So in essence, every number has a unique combination of prime numbers multiplied together as its mathematical DNA.

For example, 15 = 3 x 5. No other number has the DNA of 3 x 5. 16 = 2 x 2 x 2 x 2 etc.

So if any pair of numbers has a Common Factor… then that Common Factor’s DNA (prime factors) must appear *within* the DNA of both of our original numbers. I think it needs a diagram:

hcf

From the picture above, you can see that 9 is a common factor of 27 and 36, and that it is made up of the prime factors 3 and … well, another 3. Those 3’s also appear in the composition of the other two numbers. They are common prime factors.

Every common factor will always be made solely from prime factors that are common to both of your original numbers. From above, 3 is also a common factor, which again is made from a common prime factor within 27 and 36.

The Highest Common Factor is made from the maximum amount of common prime factors from your original numbers. In the case above, 9 is both a common factor AND the highest common factor.

These shared common factors are represented nicely in a Venn diagram – hence why we use them in schools to find the HCF:

cpf

Now this handy Venn serves a second purpose. We can find the Lowest Common Multiple from it too!

First, appreciate that the lowest common multiple of any two prime numbers, is those two numbers multiplied together (LCM of 3 and 5 is 15, LCM of 7 and 2 is 14 etc). So because we’ve already separated the common prime factors in our Venn Diagram, we’re left with the uncommon ones (the 3 on the left, and two 2’s on the right). They’re the problem. By multiplying them together we’ll get their lowest common multiple. However, we must also multiply by the *common* prime factors too as they are part of the DNA of our originals.  Our original numbers are essentially going to become factors of this new multiple, and so must be made up *only* of prime factors included in the multiple.

3 x 2 x 2 is just the common multiple of our uncommon prime factors. Confusing.

Whereas (3 x 2 x 2) x (3 x 3) will get us our lowest common multiple of 27 and 36.

So LCM = HCF (the product of the common prime factors) x the product of the uncommon prime factors.

Phew! There are other ways of course too…

We’ve stuck so long with the example of 27 and 36, so we’ll continue. Back to the Venn first of all…

cpf

So the HCF is 3 x 3 = 9, and the LCM is (3 x 3) x (3 x 2 x 2) = 108.

Now 108 is also 27 x 2 x 2, and it’s also 36 x 3. So if you wanted, rather than multiplying everything in the Venn together for LCM, you could just multiply one of your original numbers by the other original’s uncommon prime factors. You’re essentially just doing the same thing in a different way.

In fact, prime factorisation has other uses too. You can check (and find) whether a number has an integer square / cube root from its prime factors. Consider 441. If you break it down as a product of its prime factors, you get 3 x 3 x 7 x 7. There are two pairs with nothing left over. The square root of 3 x 3 is 3, and of 7 x 7 is 7.
The square root of (3 x 7) x (3 x 7) must also be 3 x 7, which is 21. So the square root of 441 is 21. Similarly if you don’t ONLY have pairs of prime factors (or, I suppose, any multiple of 2 of each prime factor), then you will not get an integer as the square root.

You can use exactly the same idea to find cube roots (you would need every prime factor to be in triplet). How clever!

Then there’s Euclid’s Algorithm… Told you he was a legend.

We don’t teach Euclid’s Algorithm, probably because its awesomeness would make heads explode, and nobody wants that. Nobody wants that.

It’s a real shame we don’t teach it, because it fits nicely with primary school division, where we get remainders and keep them and love them and cherish them.

Secondary comes along and we BANISH them, and BEAT THEM UNTIL THEY DIE. The remainders that is, not the children.

Here’s how Euclid’s Algorithm works:

Example: Find the HCF of  50604 and 10206.

Now those two numbers are big and hideous. Using our Factor Tree / Venn thing could take a while.

Euclid’s Algorithm goes like this:

50604 / 10206 = 4(10206) r. 9780

Euclid proved that the HCF of, say 50604 and 10206 is in fact the same as the HCF of 10206 and 9780 (obviously using the example above). The proof can be found here if you’re nerdy.

So the same rule still applies, so we do it all again:

10206 / 9780 = 1(9780) r. 426

or 10206 = 1(9780) + 426

9780 = 22(426) + 408

426 = 1(408) + 18

408 = 22(18) + 12

18  = 1(12) + 6

12= 2(6) + 0

So HCF of 50604 and 10206 is the same as HCF of 6 and 12, which is 6.

Don’t believe me? Here’s the GCSE method:

hcf

How clever! Such fun.

Advertisements

2 thoughts on “Complements #9 LCM and HCF

  1. My KS2 level 6 tutee who can make number sit up and juggle is gonna love this. Now I have to work on making it a tad friendlier for my Y6 struggler. Best bit – I can leave it with her for practising: you save me soo much time.

  2. Pingback: Math(s) Teachers at Play – 83rd Edition | cavmaths

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s