Exercise Set 7:

Continued Fractions

Math 414, Winter 2010, University of Washington

Due Wednesday, February 24, 2010

1. Show that every nonzero rational number can be represented in exactly two ways by a finite simple continued fraction. (For example, 2 can be represented by [1, 1] and [2], and 1/3 by [0, 3] and [0, 2, 1].)

2. If c_{n} = p_{n}/q_{n} is the nth convergent of [a_{0}, a_{1}, …, a_{n}] and a_{0} > 0, show

that

[a_{n}, a_{n−1}, …, a_{1}, a_{0}] = \frac{p_{n}}{p_{n−1}}

and

[a_{n}, a_{n−1}, …, a_{2}, a_{1}] = \frac{q_{n}}{q_{n−1}} .

(Hint: In the first case, notice that \frac{p_{n}}{p_{n−1}} = a_{n} + \frac{p_{n−2}}{p_{n−1}} = a_{n} + \frac{1}{\frac{p_{n−1}}{p_{n−2}}} .)

3. Use continued fractions to find an “impressive” rational approximation to e^{π} = 23.1406 . . ..

4. Evaluate the infinite continued fraction [2, \overline{1, 2, 1}].

5. Determine the infinite continued fraction of \frac{1+\sqrt{13}}{2}.

6. Let d be an integer that is coprime to 10. Prove that the decimal expansion of \frac{1}{d} has a period equal to the order of 10 modulo d. (Hint: For every positive integer r, we have \frac{1}{1−10^{r}} = ∑_{n≥1} 10^{−rn}.)

7. Find a positive integer that has at least three different representations as the sum of two squares, disregarding signs and the order of the summands.