Earlier this term there was a question on my first-year pure Piazza forum about greatest common divisors (highest common factors).
Question: I know how to show that something is a common divisor of two numbers but how do you show that it is the greatest common divisor of those two numbers?
The Students’ Answer was sensible:
Try the Euclidean Algorithm
with a reference to the relevant lecture (“Lecture 7b”)
I then responded with two posts:
There are, in fact, lots of different ways to investigate the greatest common divisor of two integers and , as long as we know that they are not both . (I’ll assume this below.)
To make things simple, let’s assume that and are non-negative. (Replacing with and/or with has no effect on the GCD, so we can always change the numbers to arrange this without changing the GCD.)
If, for example, , then we must have , and
Similarly if then we must have and
So now we can suppose that and are natural numbers. Then, if either or is , the GCD is obviously , so we can ignore this case.
So now we can assume that and are natural numbers and that both are at least . By the FTA (Fundamental Theorem of Arithmetic, Lecture 6) we can, in theory, find the prime factorizations of and , and use that to find the GCD. This works reasonably well for small numbers. For example, suppose and . Then and . (Not too hard to work out with small numbers.) Then you can read off the GCD by raising each prime to the highest power available (ensuring that this divides both and ) and then multiplying the resulting prime powers together. (If there are no common prime divisors, you end up multiplying the th powers together and end up with .) Here we get
In a similar way, if you have one small number and one much larger number, you can sometimes use the prime factorization of the smaller number to limit the possibilities for what the GCD could be, and then use e.g. modular arithmetic to determine which of these possibilities is the right one. (I’ll give you some examples of this type in a quiz soon! But see also past exam papers.)
For example, can you determine ? Well, , so there are not that many possibilities, and this is reduced further by the fact that is odd. So you find that you just need to determine the highest power of dividing , and this is easily done using modular arithmetic.
But if both numbers are large, then you probably won’t easily be able to determine the prime factorization of either!
In this case, as suggested above, you may want to use the Euclidean Algorithm, as we did in Lecture 7b. Note that we proved some theory first in order to justify why the Euclidean Algorithm always works to find the GCD. Of course, it may take a lot of steps before it finishes, and it does involve repeatedly finding quotient and remainder (the Division Agorithm). This basically boils down to long division, but it may not be so easy with large numbers. Still, the Euclidean Algorithm is generally the most systematic approach.
Yet another approach uses theory associated with the proof of Bézout’s Lemma from Workshop 4: if we somehow manage to find integers and so that is a (strictly) positive common divisor of and , then must actually be the GCD of and . So if you happen to spot a nice way to combine multiples of and in this way to produce a relatively small positive integer , and if you spot that is a positive common divisor of and , then must be the GCD. For example, if and then we might spot that . Then modular arithmetic (for example) helps us to spot that really is a common divisor of and , so (by the result we proved in Workshop 4) must actually be the greatest common divisor.
Well, I’ve given you so many possible methods, how can you choose between them? I don’t know! But I’ll set you some quiz questions, and let you try the different methods for yourselves.
But to give you one to think about, can you determine when and ?
Follow up response:
Here is an interesting variant: what if, instead,
You can do this with the Euclidean algorithm, as long as you can find the correct and for the first division. But have another look at the proof of the lemma on annotated slide 4 of Lecture 7b.
[This is the result which says that when you use the Division Algorithm to write in the usual way, then .]
We used the fact that . But although we were most interested in the case where , we never used that inequality in the proof of the lemma! So in fact, the same result works whenever , and and are integers, even if you haven’t found the “best” integers and . That is not a standard fact, though, so if you want to use it or something similar you should prove it.
The reason we wanted to use the standard remainder is because this guarantees that the remainders are strictly decreasing and non-negative, so they have to stabilise. But there are alternatives based on careful generalisations of that lemma.
If you choose to use an which is negative, it is probably best to take the modulus of before continuing with the process. This does not affect the GCD, but the second line of the lemma, about what happens when the remainder is , does assume that , and anyway we usually divide by positive integers in this module.