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.

Greatest Common Divisors

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!

About these ads

About Bert Speelpenning

http://unlearningmath.com is my blog on math learning and math teaching. My background is in the high-tech computer software industry (I've got a PhD in Computer Science from the University of Illinois) and worked for Hewlett Packard, Silicon Graphics, Borland and finally for Microsoft till I left in 2000. I have since worked in the area of math learning, with students (7-9th grade) and teachers (elementary school level). I own an independent educational consulting business called Math Partners.
This entry was posted in Uncategorized and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s