Recounting the Rationals, part IV

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 $3/7$ is in lowest terms, but $14/21$ 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 $6/49$ 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 $\gcd(m,n)$ , is the largest number which evenly divides both m and n. For example, $\gcd(12,30) = 6$ , 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 $\gcd(m,n) = 1$ .

You should be able to verify a few simple properties of the GCD function yourself. For example, $\gcd(m,n) = \gcd(n,m)$ , and $\gcd(km, kn) = k \cdot \gcd(m,n)$ . Another slightly less obvious property, but more important for our purposes, is that $\gcd(m,n) = \gcd(m, m \pm n)$ . Why is this? Well, suppose $\gcd(m,n) = d$ . That means d divides both m and n, so we can write $m = dr$ and $n = ds$ . Therefore $m+n = dr + ds = d(r+s)$ , 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 $(m+n) - m = n$ , 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 $\gcd(m,n) = \gcd(m, m+n)$ . The argument to show that $\gcd(m,n) = \gcd(m,m-n)$ is exactly the same.

Applying this to the Calkin-Wilf tree is a piece of cake. We want to show that for every $i/j$ in the Calkin-Wilf tree, it is the case that $\gcd(i,j) = 1$ . Well, it’s certainly true for the root node, 1/1: $\gcd(1,1) = 1$ . And supposing it is true for some node $i/j$ , it must also be true for the child nodes, since we know that $\gcd(i,j) = \gcd(i,i+j) = \gcd(i+j,j)$ . 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.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

11 Responses to Recounting the Rationals, part IV

Bran says:

February 6, 2008 at 5:40 pm

I really like this series of articles. It’s accessible, interesting, and the proofs are elementary enough that it would make for reading even for a non-mathematician. Keep it up!
Brent says:

February 7, 2008 at 1:33 pm

Bran: thanks! Your kind encouragement means a lot to me. Don’t worry, I definitely intend to keep it up!
Pingback: The One-Year Anniversary Carnival of Mathematics « 360
Jonathan says:

February 9, 2008 at 6:19 pm

I’m enjoying this, too. I really never saw the Calkin-WIlf tree before. Where would one normally encounter it?

Jonathan
Brent says:

February 10, 2008 at 4:09 pm

Where would one normally encounter it? Well, I’m not sure one would “normally” encounter it, depending on your definition of “normally”. I didn’t encounter it until just this year, by reading this very paper.
Jonathan says:

February 27, 2008 at 1:02 pm

Hey, Brent, out of curiosity: in the original paper, which you mentioned contained a comprehensible concept but would be hard to laymen to understand because it was written for mathematicians, how is this proof handled? I can see how it might be regarded as trivial, but then it is also important to prove what you assert, right? So how much detail did they go into, if any? I’m curious what the protocol is, and a bit about the phrasing.
Brent says:

February 28, 2008 at 2:48 pm

Jonathan: good question. I’ll quote the original proof here in its entirety:

“The numerator and denominator at each vertex are relatively prime. This is certainly true at the top vertex. Otherwise, suppose r/s is a vertex on the highest possible level of the tree for which this is false. If r/s is a left child, then its parent is r/(s − r), which would clearly also not be a reduced fraction, and would be on a higher level, a contradiction. If r/s is a right child, then its parent is (r − s)/s, which leads to the same contradiction.”

As you can see, they are assuming several things, including (a) that you know what “relatively prime” means, (b) that you realize why r/(s-r) is “clearly” not reduced if r/s isn’t, (c) you are comfortable with proof by contradiction, and possibly several other things.
conner says:

June 13, 2008 at 9:32 pm

i understand that this is not the place to post what i am posting. but it is interesting. the first 3 perfect numbers (6,28,492) have a relationship with the fibonacci sequence. the fibonacci sequence is: 1,1,2,3,5,8,13,21,34…
if you place the perfect numbers into the sequence you get: 1,1,2,3,5,6,8,13,21,28,34… now focus on the pairs of four numbers with the perfect numbers in the 3rd position. 3,5,6,8 and 13,21,28,34. the 2 numbers surrounding the perfect number (5,8) and (21,34) are what you utilize next. 5,6,8. 6-5=1 8-6=2 1+2= 3!! the sequential number occuring before the 2 numbers you used. this is consistant with all of the perfect numbers known. ( 13,21,28,34 – 28-21= 7 34-28=6 – 7+6= 13) if anyone can think of a use for this phenomen please post it. by the way brent, i love the article. you definitely should keep it up. hope you get lots of support. thank you.
Brent says:

June 14, 2008 at 11:30 am

Hi Conner,

Actually, this has nothing to do with perfect numbers. =) For example, try 30 instead of 28: 13,21,30,34. 30 – 21 is 9, 34 – 30 is 4, 9+4 = 13. This works for any number at all that you would like to stick in between two Fibonacci numbers. Try it! I will leave the explanation up to you or anyone else who would like to figure it out. =)

Thanks for the encouragement! Glad you are enjoying it.
Pingback: The hyperbinary sequence and the Calkin-Wilf tree | The Math Less Traveled
Pingback: Recounting the Rationals, part IVb: the Euclidean Algorithm | The Math Less Traveled