Homework 5: Continued Fractions
DUE WEDNESDAY, OCTOBER 31 (HALLOWEEN)

William Stein

Date: Math 124 $\quad$ HARVARD UNIVERSITY $\quad$ 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 $n$th convergent of the continued fraction $[a_0,a_1,\ldots,a_n]$ and $a_0>0$, show that

$$[a_n,a_{n-1},\ldots, a_1, a_0] = \frac{p_n}{p_{n-1}}$$

and

$$[a_n,a_{n-1},\ldots, 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(\tau)$, denoted by ellj in PARI, which takes as input a complex number $\tau$ with positive imaginary part, and returns a complex number called the ``$j$-invariant of the associated elliptic curve''. Suppose that $\tau$ is approximately $-0.5+ 0.3281996289i$ and that you know that $j=j(\tau)$ is a rational number. Use continued fractions and PARI to compute a reasonable guess for the rational number $j=$ellj$(\tau)$. (Hint: In PARI $\sqrt{-1}$ is represented by I.)

4.

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

(iv)

$[\overline{2,3}]$

(v)

$[2,\overline{1,2,1}]$

(vi)

$[0,\overline{1,2,3}]$

5.

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

(vii)

$\sqrt{5}$

(viii)

$$\frac{1+\sqrt{13}}{2}$$

(ix)

$$\frac{5+\sqrt{37}}{4}$$

6.

(x)

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

(xi)

(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

$$\left\vert x - \frac{a}{b}\right\vert < \frac{1}{\sqrt{5}b^2}.$$

Taking $x=\pi$, 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,\ldots].$$

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.

(xii)

(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.

(xiii)

(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.