highest common factor

this method, of lining up the factors in common, seems a helpful way to try to find the highest common factor of two numbers
having already done a prime factor break down

for example, for 1050 and 1540:

1050 = 2 x 3 x 5 x 5 x 7

1540 = 2 x 2 x 5 x 7 x 11,

putting loops around the common factors shows more clearly those numbers that are in both sets:

the product of these is the hcf

the product of what is left and the hcf is the lcm

the lcm can be calculated from the hcf since  hcf (a,b) x lcm (a,b) = a x b
so to find the lcm (often the trickier task) you can divide the product of the two numbers by their hcf

why is this relationship true?


Jo Morgan, at resourceaholic, suggests using a division by a common factor method:

a Venn diagram can be helpful

place the common factors in the intersection of two sets
hcf = product of the elements in (A intersection B)

the lowest common multiple is the product of all the elements in (A union B)

e.g. for 48 and 180

hcf is 2 x 2 x 3 = 12

lcm is 12 x 4 x 15 = 720








then, of course, there is always Euclid's algorithm
e.g. the highest common factor of 48 and 180 is
also the highest common factor of 180 - 48
and 180 - 2 x 48
and 180 - 3 x 48 = 36
so the problem is simplified to finding the hcf of  36 and 48