Notes on Divisibility – Eratosthenes and Euclid

You will want to read the Notes on Divisibility post first.

In the figure below, I’ve shown the first 22 mile markers, and the red marks on each.  Skip counting by twos leads to the red “2” marks, skip counting by threes leads to the red “3” marks, and so forth. If you look at mile marker 15, you see the marks 1, 3, 5, 15.  These numbers are called the divisors of 15, even though we have yet to do any division.  There is a useful shorthand for saying that 3 is a divisor of 15: instead, we write 3 | 15.  This is pronounced  “3 divides into 15” or “3 is a divisor of 15”.

Something that shows up right away is that there is considerable variation in how many red marks each mile marker ends up with.  Mile marker 18 has 6 marks (1 green, 5 red), mile marker 1 is the odd one out with only a single mark, a green one.  Apart from mile marker 1, the minimum number of marks any mile marker has is 2 (one green, one red).  The mile markers with only one green and one red mark are known as primes.  The idea for identifying primes the way we’ve done it here is very old indeed, and is attributed to Eratosthenes, who lived some 2200 years ago. Eratosthenes

Even before Eratosthenes, another Greek, Euclid, was looking at how to find common divisors.  Imagine you focus on two particular mile markers and you wonder what divisors they have in common.  This question is easily answered if all the red marks have been put in place.   Let’s take a specific example and focus on mile markers 16 and 22.  They share some divisors and don’t share others.   Mile marker 16 has a divisor 2, and so does 22.  Mile marker 16 has a divisor 4, not shared by 22.  Mile marker 22 has a divisor 11, not shared by 16.  The common divisors are 1 and 2. Euclid

But what if the red marks haven’t yet been put in place – could you still figure out what divisors mile marker 16 and 22 have in common?  A red mark that hits both 16 and 22 is one that lands on 16 during the skip counting, and then lands on 22 later during the skip counting.  Since the two markers are 6 miles apart, that 6 miles must be a whole number of skips.  Hence the fundamental insight, already claimed by Euclid, that a common divisor of 16 and 22 is also a divisor of 6.  This allows us to answer the original question “what are the common divisors of 16 and 22?” with the somewhat less daunting question “what are the common divisors of 6 and 16?”  We somehow ended up looking at a different pair of mile markers, which on the whole were not so far down the road.  In turn, these mile markers are 10 miles apart, so any hop that lands on both must be a hop that covers 10 miles exactly. $\begin{matrix} \text{mile marker} & \text{other mile marker} & distance \\ \hline \\16 & 22 & 6 \\ 16 & 6 & 10 \\ 10 & 6 & 4 \\ 4 & 6 & 2 \\ 4 & 2 & 2 \\ 2 & 2 & 0 \end{matrix}$

The table shows our progression, from far-away mile markers to closer-in mile markers.  When we reach 2 and 2, we’re reached an end of sorts, since the common divisors of 2 and 2 are just the divisors of 2.  And, as is often the case, we don’t care for all the common divisors but just want to know the biggest one, then we already found it: it’s 2.

Below, I will summarize this approach to finding the biggest of the common divisors, starting from two arbitrary mile markers.  But we need a name.  It turns out in the USA there are at least two common names in circulation for this thing we’ve called the biggest common divisor.  It is sometimes called Greatest Common Divisor (GCD), and sometimes Greatest Common Factor (GCF).

Here is a summary for finding the GCD of two arbitrary mile markers p and q.

(1) if p=q, then the GCD is p.  We’re done.

(2) but if p>q, then replace p with p – q, and start again at (1) with the new value of p and the old value of q.

(3) but if p<q, then replace q with q – p, and start again at (1) with the old value of p and the new value of q.

I encourage you to play with this method for finding the biggest common divisor of any two numbers up to 22, and see how the method works.   You can look at the red markers to confirm that at each stage the common divisors stay the same (the fancy way of saying this is: kept invariant).

Notes:
(a) we decoupled the problem of finding all common divisors from that of finding the biggest common divisor.  If somebody needs all the common divisors, they can first find the biggest common divisor and then look for the divisors of it.
(b) many variants of this approach exist, and many of these variations all go by the name of Euclid’s algorithm.
(c) however you and I may think of divisors, the entire discussion in this post has completely avoided division.  It turns out you don’t even need to know what division is to have a deep look at patterns associated with divisors.
(d) an interesting alternate formulation of Euclid’s algorithm from the 3-step version above is this: $gcd(p,q) = \begin{cases}gcd(p-q,q) & \text{if } p > q \\ gcd(p,q-p) & \text{if } p < q \\ p & \text{if } p = q \end{cases}$