Greatest common divisors

This post was originally posted on my WordPress blog
https://explainingmaths.wordpress.com/2021/01/03/greatest-common-divisors/

Earlier this term [Autumn 2020] 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:

Main response:

Hi,

There are, in fact, lots of different ways to investigate the greatest common divisor of two integers \(a\) and \(b\), as long as we know that they are not both \(0\). (I'll assume this below.)

To make things simple, let's assume that \(a\) and \(b\) are non-negative. (Replacing \(a\) with \(-a\) and/or \(b\) with \(-b\) has no effect on the GCD, so we can always change the numbers to arrange this without changing the GCD.)

If, for example, \(b=0\), then we must have \(a > 0\), and

\(\mathrm{GCD}(a,b) =\mathrm{GCD}(a,0)=a\).

Similarly if \(a=0\) then we must have \(b>0\) and

\(\mathrm{GCD}(a,b)=\mathrm{GCD}(0,b)=b\).

So now we can suppose that \(a\) and \(b\) are natural numbers [i.e., positive integers]. Then, if either \(a\) or \(b\) is \(1\), the GCD is obviously \(1\), so we can ignore this case.

So now we can assume that \(a\) and \(b\) are natural numbers and that both are at least \(2\). By the FTA (Fundamental Theorem of Arithmetic, Lecture 6) we can, in theory, find the prime factorizations of \(a\) and \(b\), and use that to find the GCD. This works reasonably well for small numbers. For example, suppose \(a=63\) and \(b=147\). Then \(a=3^2 \times 7\) and \(b=3 \times 7^2\). (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 \(a\) and \(b\)) and then multiplying the resulting prime powers together. (If there are no common prime divisors, you end up multiplying the \(0\)th powers together and end up with \(1\).) Here we get

\(\mathrm{GCD}(a,b)=3^1 \times 7^1 = 21\).

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 \(\mathrm{GCD}(36,10^{23}+11)\)? Well, \(36=2^2 \times 3^2\), so there are not that many possibilities, and this is reduced further by the fact that \(10^{23}+11\) is odd. So you find that you just need to determine the highest power of \(3\) dividing \(10^{23}+11\), 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 \(m\) and \(n\) so that \(y=ma+nb\) is a (strictly) positive common divisor of \(a\) and \(b\), then \(y\) must actually be the GCD of \(a\) and \(b\). So if you happen to spot a nice way to combine multiples of \(a\) and \(b\) in this way to produce a relatively small positive integer \(y\), and if you spot that \(y\) is a positive common divisor of \(a\) and \(b\), then \(y\) must be the GCD. For example, if \(a=2^{100}-1\) and \(b=2^{99}+1\) then we might spot that \(2b-a=3\). Then modular arithmetic (for example) helps us to spot that \(3\) really is a common divisor of \(a\) and \(b\), so (by the result we proved in Workshop 4) \(3\) 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 \(\mathrm{GCD}(a,b)\) when \(a=10^{1000}-1\) and \(b=10^{998}-1\)?

Best wishes,
Dr Feinstein

Follow up response:

Here is an interesting variant: what if, instead,

\(a=10^{1000}-1\) and \(b=10^{998}+1\)?

You can do this with the Euclidean algorithm, as long as you can find the correct \(q\) and \(r\) 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 \(a=qb+r\) in the usual way, then \(\mathrm{GCD}(a,b)=\mathrm{GCD}(b,r)\).]

We used the fact that \(a=qb+r\). But although we were most interested in the case where \(0 \leq r < b\), we never used that inequality in the proof of the lemma! So in fact, the same result works whenever \(a\in \mathbb{Z}\), \(b\in \mathbb{N}\) and \(q\) and \(r\) are integers, even if you haven't found the "best"  integers \(q\) and \(r\). 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 \(r\) 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 \(r\) which is negative, it is probably best to take the modulus of \(r\) 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 \(0\), does assume that \(b>0\), and anyway we usually divide by positive integers in this module.

Best wishes,
Dr Feinstein