Professor Dave again, let’s talk about greatest common factors.
We just learned about least common multiples.
These can be found when comparing two numbers, and finding the smallest number that is a
multiple of both of them.
By the same token, we will want to be able to identify the greatest common factor of
two numbers.
As you might be able to guess, this is the largest number that is a factor of both the
numbers.
Take for example ten and fifteen.
If we write out all the factors, for ten that would be one, two, five, and ten.
For fifteen, that would be one, three, five, and fifteen.
The largest number that can be found in both of these lists is five, so five is the greatest
common factor of these two numbers.
Now let’s try eighteen and twenty-four.
Here are all the factors for both of these numbers, and we will find that six is the
largest factor that is common to both lists, so six is the greatest common factor of eighteen
and twenty-four.
Just like with the least common multiples, this is easy to do for small numbers, because
they will only have a handful of factors, so we can just list them all and compare.
But again, as numbers get larger, it may become tedious to identify and list every single
factor for a number, so there is a bit of trick to this as well.
Let’s look at the same example we just did.
We can carry out the prime factorization of both numbers, and that would give us two times
three times three, and two times two times two times three.
Once we have this, all we do is take all the numbers that appear in both lists, as many
times as they appear in both of the lists, and multiply them together.
So this first two, that’s in both so let’s pull that aside.
This three, that’s also in both, so let’s pull that aside as well.
Now we are done, because one list has a three left and no twos, and the other list has some
twos but no threes.
Now we take the two and three we pulled aside and multiply them together to get six, which
we already knew was the answer.
This works, because if we take all of the prime factors present in both lists, they
must necessarily give a product that is a factor of both numbers, and with no more prime
factors left in common to multiply, this will necessarily be the greatest common factor.
Let’s try the same thing for twenty-four and a hundred and eight.
For twenty-four let’s chop that up into twelve times two, the twelve into four times
three, and the four into two times two.
That gives us two times two times two times three.
For a hundred and eight let’s cut it in half, cut the fifty-four in half, cut the
twenty-seven into three and nine, and nine into three and three.
That gives us two times two times three times three times three.
Now we see what we have in both lists.
We take one of the twos, another two, and a three, and that’s all we can do, so two
times two times three is twelve, and that’s the greatest common factor for these two numbers.
This technique is reliable no matter how big the numbers get, so it eventually becomes
a much better strategy than listing all the factors and examining the lists.
Let’s check comprehension.