Notes on Divisibility – Common Divisors
In an earlier post I introduced the notion of a divisor without relying on division, instead thinking of it as a mark that was left during skip counting. This is a very old notion, dating at least to the times of Eratosthenes. In the same post, I also introduced the notion of Common Divisors of a pair of numbers, again without relying on division, an approach that has been known at least since Euclid. Since the common divisors of a given pair of numbers are all themselves divisors of a single number, known as the Greatest Common Divisor (GCD), it is common to just look for the GCD instead of for all common divisors.
Just like the normal multiplication table shows the product of two numbers, we can make a table that shows the GCD of two numbers – that is, of any two numbers up to a certain limit. For multiplication tables, you usually see the table drawn from 1 to 10, for our GCD table it will show numbers from 1 to 20.
To use this table to find the Greatest Common Divisor of 9 and 6, we’d look in row 9 and column 6 and find the entry 3, which is the GCD of 9 and 6.
In this table, many interesting patterns can be discerned. Here are some:
- Lots of entries are 1. These entries correspond to pairs of numbers that are relative primes, something we touched on in a prior post.
- If you look at the diagonal, you see 1, 2, 3, etc. The greatest common divisor of two identical numbers is that number itself.
- If you look at the row for a prime number, the only other number than the prime number you find there is 1.
- For any row, the numbers you find there are the divisors of the row number. E.g. for row 15 the only entries you find are 1, 3, 5, 15. These are exactly the divisors of 15.
- You could flip all the numbers around the diagonal and end up with the same table: like multiplication, the GCD doesn’t depend on the order of the two numbers.
Can you find additional patterns? For the patterns I listed and the ones you find yourself, can you convince yourself why those patterns obtain? “Extra credit” if you can show how come the patterns obtain without any reference to division!