Two numbers (positive integers) each have a collection of factors. Some of those factors belong in both lists - and can be called ‘common factors’ for that reason. At the least, 1 is in both lists. The biggest in the list of common factors is, obviously the highest common factor, or HCF. Easy.
You think.
Let’s look at 144. Factors {1,2,3,4,6,8,9,12,16,18,24,36,48,72,144}
It’s an odd numbered list because 144=12x12, and all the other numbers pair off: 8x18=144, 16x9=144 and so on.
Let’s also look at 56. Factor pairs are 1x56, 2x28, 4x14, 8x7, so the factors are {1,2,4,7,8,14,28,56}. Check, eight of them, 56 is not a square. The biggest number in both lists is 8. So the HCF of 144 and 56 is 8. Which we might write as HCF(144,546)=8.
Lets look at 128. We could do the same pairing, but I’m going to jump and point out that I ‘know’ this number already as 27, so I know straight away that all the factors will be powers of two and I can see that, in the list of factors for 144, I have {1,2,4,8,16}. So I can see that 16 is the HCF, that HCF(144,128)=16.
Since we can write that 144=9x16 and 128=8x16, we can also see that whatever the difference between 144 and 128 is, it is ALSO a multiple of the HCF of these two numbers. That;’s not just an observation, it must be true always. You could prove that.
Just in case you’re going to confuse HCF with other things, notice here that the highest common factor is necessarily not bigger than the numbers we’re working with.
Why didn’t I write smaller instead of not bigger? Try HCF (144, 72).
I say it is obvious, if only because we already did the work, that 144=2x72. so the HCF(144,72)=72. That’s as big as 72, though it’s smaller than 144. Prove that this is an extreme case.
Similarly, try HCF(144,49). The factors of 49 (it’s a square) are {1,7,49}. The only factor in both lists is 1 (one, unity). This is the other extreme case for HCF. Two numbers with the HCF=1 are called relatively prime, sometimes co-prime.
Examples for you to do: Find the HCF of each of the following pairs. Inspect each of your answers by checking that the difference of the two numbers given is also a multiple of the HCF
1 12, 26 5 56,144 9 108, 144 13 144, 1044
2 26, 36 6 56, 128 10 1008, 144 14 1008, 256
3 36, 48 7 56,108 11 10008, 144 15 169, 49
4 48, 56 8 56, 48 12 128, 1028 16 101, 10001
17 If the HCF of two numbers J and K is 56 and both numbers have three prime factors, what is the smallest pair of numbers that fit the description?
18 a = 2a 3b 5c and b= 2e 3f 5g Given that a,b,c,e,f,g are all relatively prime, find the HCF(a,b).
19 Number A is the product of primes and number B is the product of some different primes. What is HCF(A,B)?
20 HCF (x,y)=2, HCF(y,z)=3 What can you say about HCF (x,z)?
Can this extend to fractions? Well, yes, more or less, it can. HCF (⅔, 7/15) implies that we have a unit of 15ths, so we might view this as HCF15(6,7). But 6 and 7 are relatively prime, so the HCF is 1/15. I think this is sufficient explanation, but I don’t find fractions a problem.
Can we find the HCF of more than two numbers? Yes, and I think this is obvious.
HCF (36, 96, 144) we can eliminate 36 because it is a factor of 144, so this is the same as finding HCF(96,144)
HCF (48, 90, 156) lends itself to a table technique, where each new row is divided by the next possible common prime factor. All three divide by first 2 and then 3, leaving 8, 15 and 26 relatively prime.
Can we find HCF (1.2, 0.12)? Yes; first make them similar decimals, to two places. So we’re trying to do HCF (1.20, 0.12), which is equivalent to doing HCF (120, 12) and dividing the result by 100, or, as I wrote it before, HCF100 (120, 12). Clearly HCF(120,12) =12, so the answer is 0.12.
Pushing even harder, can we do HCF( √3, √5)? This is definitely not integer arithmetic, but these two are relatively prime, since 3 and 5 are. The common factor is √3x5 = √15, so the equivalent integer problem is HCF(5,3), which is 1, i.e. they are relatively prime.
These extreme cases (decimals fractions, surds) are all satisfied by finding a common unit. HCF (⅔, 7/15) used fifteenths, HCF (1.2, 0.12) used hundredths, HCF( √3, √5) uses √15. So the requirement to work with integer arithmetic is met by converting the problem to an intger arithmetic equivalent.
There are some good websites explaining LCM and HCF and little tricks to solve these.
DJS 20181004
answer to Q5 on Factors page:
1 HCF(12, 26)=2 2 HCF(26, 36)=2 3 HCF(36, 48)=12 4 HCF( 48, 56 )=8 5 HCF(56,144)=8 6 HCF(56, 128)=8 7 HCF(56,108)=4 8 HCF(56, 48)=8 9 HCF(108, 144)=36 10 HCF(1008, 144)=144 11 HCF(10008, 144)=72 12 HCF(128, 1028)=4 13 HCF( 144, 1044)=36 14 HCF(1008, 256)=144 15 HCF(169, 49)=1 16 HCF(101, 10001)=1
17 56 = 2.2.2.7 so just two primes used. The smallest other primes are 3 and 5, so one is 56x3 and the other is 56x5, i.e. (J, K)= 168, 280)
18 HCF(a,b) = 2x3x5=30
19 HCF(A,B)=1
20 HCF (x,y)=2, HCF(y,z)=3 So both 2 and 3 are factors of y but x has not factor 3 and z has no factor 2. SoHCF (x,z) could be 1, but it could also be some other number that is not a factor of y, such as 7. Example: x=14, y=12, z=21; HCF(14,12)=2, HCF(12,21)=3, HCF(14,21)=7.3√3
