Homework 5: Continued Fractions

Due Wednesday, October 31 (Halloween)

William Stein

Math 124 Harvard University Fall 2001

There are 10 problems. Feel free to use a computer on any of them.

1. (3 points) Draw some sort of diagram that illustrates the partial convergents of the following continued fractions:

(i) [13, 1, 8, 3]

(ii) [1, 1, 1, 1, 1, 1, 1, 1]

(iii) [1, 2, 3, 4, 5, 6, 7, 8]

2. (5 points) If c_{n} = p_{n}/q_{n} is the nth convergent of the continued fraction [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. (4 points) There is a function j(τ), denoted by ellj in PARI, which takes as input a complex number τ with positive imaginary part, and returns a complex number called the “j-invariant of the associated elliptic curve”. Suppose that τ is approximately −0.5 + 0.3281996289i and that you know that j = j(τ) is a rational number. Use continued fractions and PARI to compute a reasonable guess for the rational number j = ellj(τ). (Hint: In PARI \sqrt{−1} is represented by I.)

4. (3 points) Evaluate each of the following infinite continued fractions:

(i) [\overline{2, 3}]

(ii) [2, \overline{1, 2, 1}]

(iii) [0, \overline{1, 2, 3}]

5. (3 points) Determine the infinite continued fraction of each of the following numbers:

(i) \sqrt{5}
(ii) \frac{1 + \sqrt{13}}{2}
(iii) \frac{5 + \sqrt{37}}{4}

6. (i) (4 points) For any positive integer n, prove that \sqrt{n^{2} + 1} = [n, \overline{2n}].

(ii) (2 points) Find a convergent to \sqrt{5} that approximates \sqrt{5} to within four decimal places.

7. (4 points) A famous theorem of Hurwitz (1891) says that for any irrational number x, there exists infinitely many rational numbers a/b such that

|x − \frac{a}{b}| < \frac{1}{\sqrt{5}b^{2}} .

Taking x = π, obtain three rational numbers that satisfy this inequality.

8. (3 points) The continued fraction expansion of e is

[2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, …].

It is a theorem that the obvious pattern continues indefinitely. Do you think that the continued fraction expansion of e^{2} also exhibits a nice pattern? If so, what do you think it is?

9. (i) (4 points) Show that there are infinitely many even integers n with the property that both n + 1 and \frac{n}{2} + 1 are perfect squares.

(ii) (3 points) Exhibit two such integers that are greater than 389.

10. (7 points) A primitive Pythagorean triple is a triple x, y, z of integers such that x^{2}+y^{2} = z^{2}. Prove that there exists infinitely many primitive Pythagorean triples x, y, z in which x and y are consecutive integers.