Tuesday 29 January 2013

Map of relatively prime pairs

Here is something which I thought was impressive. Imagine dividing a plane into two halves with the vector (1,0) labelling the left half and the vector (0,1) labelling the right. Imagine then creating a downward split in this line, a bifurcation, such that the new region created below the point of the split is labelled with the vector that is the sum of (1,0) and (0,1) namely (1,1). Now create two new bifurcations on these lines with the labels for the newly created regions being the sum of the vectors for the regions either side of the line leading to the point of the split. So, we end up with two new regions labelled with the vectors (1,0)+(1,1)=(2,1) and (1,1)+(0,1)=(1,2). Now repeat this process again ad infinitum creating 4, then 8, then 16...regions. This is the map of relatively prime pairs.

The top of this map can be seen on the front of Stillwell's book. It has some interesting properties. Firstly, each region of the map (except (1,0) and (0,1)) is labelled by a relatively prime (or coprime) pair of natural numbers. This means that for such a region (a,b), a and b have no common divisor apart from 1 (that is gcd(a,b)=1). Now what is even more amazing is that every possible pair of relatively prime natural numbers (a,b) appears as a label once, and only once, in this diagram. What is more, starting from the top of the diagram you can follow a unique path down the tree to a particular pair (a,b) of your choosing.

I think if someone asked me if it was possible to come up with some orderly way of finding every possible pair of coprime natural numbers I would have said that it was impossible and yet here is a way. What's more, it is a fairly structured diagram. If natural number pair (k,l) is anywhere to the left of natural number pair (m,n) then (k/l)>(m/n), so the ratio of the pairings decreases from left to right. In fact, if we consider the fraction a/b for any natural number pair (a,b) then this diagram contains all possible reduced fractions (i.e. fractions where a and b have no common divisor) and the fractions decrease in size from left to right.

What a cool thing!