Finding Integer Solutions Worksheet With Answer Key - 7th Grade, Serin Hong (Page 5 of 6) in pdf

Finding Integer Solutions Worksheet With Answer Key - 7th Grade, Serin Hong Page 5

Math 7 Spring 2016

Instructor: Serin Hong

1 =

. .

Prove the following properties of the Calkin-Wilf tree:

(a) (10 pts) Every fraction in this tree is in reduced form, i.e., its denominator and numerator are

relatively prime.

Solution. From the identity a + b = a 1 + b we deduce that gcd(a + b, a) = gcd(a, b). Similarly,

we deduce that gcd(a + b, b) = gcd(a, b) from the identity a + b = b 1 + a. Hence if

is in reduced

a + b

form, its children

and

are also in reduced form.

a + b

Since the tree is generated from a single fraction 1 =

which is in reduced form, every fraction

in the tree must be in reduced form.

(b) (20 pts) Every positive rational number appears exactly once in this tree.

Solution. Let r be an arbitrary positive rational number. We deﬁne a sequence r

, r

as follows:

(1) r

= r.

(2) If r < 1 with reduced form

, we set r

(3) If r > 1 with reduced form

, we set r

(4) If r = 1, we terminate the sequence.

Note that the sum of denominator and numerator is strictly decreasing in this sequence, implying

that the sequence must terminate after ﬁnite steps. On the other hand, it is evident from the above

rules that the last term must be 1. Hence we have a sequence of the form r = r

, r

, r = 1.

Tracing this sequence backwards gives a “genealogy” for r in the tree, as each r is a child of r

by the above rules. This proves that r appears in this tree.

Finding Integer Solutions Worksheet With Answer Key - 7th Grade, Serin Hong Page 5