Continuing a series about the Calkin-Wilf tree (see those links for some background), today I’d like to show why all the rationals in the tree must be in lowest terms. Let’s start off with a little number theory!
What do we mean when we say that a fraction is “in lowest terms”? We simply mean that the numerator and denominator have no common factors other than 1. So is in lowest terms, but isn’t, since the numerator and denominator are both divisible by 7. You will sometimes also hear the term relatively prime to describe two numbers which have no common factors. It doesn’t really have anything to do with being prime; for example, 6 and 49 are relatively prime (and hence is in lowest terms), even though neither 6 nor 49 is prime.
A more formal way to talk about all of this is in terms of the greatest common divisor, or GCD. The GCD of two numbers m and n, often written , is the largest number which evenly divides both m and n. For example, , since 6 is the largest number which evenly divides both 12 and 30. So, in particular, we can say that m and n are relatively prime when .
You should be able to verify a few simple properties of the GCD function yourself. For example, , and . Another slightly less obvious property, but more important for our purposes, is that . Why is this? Well, suppose . That means d divides both m and n, so we can write and . Therefore , so d divides m+n too! So, d is a common divisor of m and m+n. Note also that if anything bigger than d was a common divisor of m and m+n, then this larger divisor would also divide , so it would be a common divisor of m and n — but we already know that d is the greatest common divisor of m and n. Therefore, d really is the greatest common divisor of m and m+n, and . The argument to show that is exactly the same.
Applying this to the Calkin-Wilf tree is a piece of cake. We want to show that for every in the Calkin-Wilf tree, it is the case that . Well, it’s certainly true for the root node, 1/1: . And supposing it is true for some node , it must also be true for the child nodes, since we know that . And we’re done! This is a nice example of a proof by induction: all we have to do is prove that something is true for some starting value, and that whenever it is true for one thing it must be true for the next, and voilà! We have proved it for an infinite series of cases.
So, we now know that the Calkin-Wilf tree contains every positive rational, in lowest terms, exactly once! Next time, I’ll talk about a way to compute the GCD of two numbers, called the Euclidean Algorithm—which is probably a lot different than the way you learned to compute GCDs in elementary school—and its cool connection to the Calkin-Wilf tree.