Continued Fractions

note

This is lab was written by Elad Zelingher, all rights reserved to Elad Zelingher.

Continued fractions are a way of representing real numbers. Given a real number $\theta$, recall that we define $\theta_0 = \theta$ and $a_0 = \left\lfloor \theta_0 \right\rfloor$. If $a_0 \ne \theta_0$ (that is, if $\theta_0$ is not an integer), then we have that $0 < \theta - a_0 < 1$ and thus $\theta = a_0 + \frac{1}{\theta_1}$, where $\theta_1 = \frac{1}{\theta_0 - a_0} > 1$. We continue the process. Suppose that $(a_{j})_{j=0}^{n-1}$ and $(\theta_j)_{j=0}^{n}$ are defined so that $\theta_{j} = a_j + \frac{1}{\theta_{j+1}}$ for every $j < n$. We define $a_n = \left\lfloor \theta_n \right\rfloor$. If $a_n = \theta_n$ (that is, if $\theta_n$ is an integer), then we have that

$$\begin{equation} \theta = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\dots + \frac{1}{a_n}}}} \end{equation}$$

Otherwise, we have that $\theta_n = a_n + \frac{1}{\theta_{n+1}}$ where $\theta_{n+1} = \frac{1}{\theta_n - a_n} > 1$ and

$$\begin{equation} \theta = a_0 + \frac{1}{a_1 + \frac{1}{\dots + \frac{1}{a_n + \frac{1}{\theta_{n+1}}}}}. \end{equation}$$

The process ends if and only if the number $\theta$ is rational. Otherwise, the sequences $(a_i)_{i=0}^{\infty}$ and $(\theta_i)_{i=0}^{\infty}$ are infinite. If the process ends at step $n$, we write

$$\begin{equation} \theta = \left[a_0, a_1, \dots, a_n\right]. \end{equation}$$

Otherwise, we write

$$\begin{equation} \theta = \left[a_0, a_1, a_2, \dots \right]. \end{equation}$$

Problem 1

Compute the continued fractions of $\frac{25}{13}$, $\frac{1 + \sqrt{5}}{2}$ and of $\sqrt{3}$.

Problem 2

The program ContinuedFraction allows you to compute the continued fraction of a number of the form $a + b \sqrt{d}$ where $d \ge 0$ is a non-square integer (or zero) and $a,b$ are rational numbers. Use this program to verify the computations from the previous problem.

Problem 3

For a rational number $\frac{m}{n}$ with $m$ and $n$ coprime compare the continued fraction of $\frac{m}{n}$ produced by ContinuedFraction and the Euclidean algorithm steps for $m$ and $n$ produced by EuAlgDem. How are these related?

Problem 4

A continued fraction is called essentially periodic if the sequence $(a_n)$ is periodic from some place. Suppose that $a_n$ is periodic from place $m+1$ and that its period is of length $\ell$. We write

$$\begin{equation} \theta = \left[a_0,\dots,a_{m-1},a_m,\overline{a_{m+1}, \dots, a_{m+\ell}} \right]. \end{equation}$$

Use ContinuedFraction with different inputs to test whether the continued fraction of $a + b \sqrt{d}$ is always periodic for $b, d \ne 0$.

Problem 5

A continued fraction is called purely periodic if it is periodic from the first term. Given a purely periodic continued fraction, we can find the number it represents by writing down a recursive expression. For example, if

$$\begin{equation} x = 2 + \frac{1}{2 + \frac{1}{2 + \dots}} \end{equation}$$

Then we have $x = 2 + \frac{1}{x}$ and hence $x^2 - 2x - 1 = 0$. This equation has two solutions

$$\begin{equation} x = \frac{2 \pm \sqrt{8}}{2} = 1 \pm \sqrt{2}. \end{equation}$$

However it is clear that $x$ is positive so we must have $x = 1 + \sqrt{2}$.

Using this we can evaluate essentially periodic continued fractions: we first compute the periodic part and then substitute the expression we have for it in the continued fraction. Use this method to compute $[1,1,\overline{2}]$ and check your result using ContinuedFraction.

Problem 6

The program PCFEvaluator allows you to evaluate an essentially periodic continued fraction. Use this program to find numbers whose continued fraction expression is purely periodic. Can you classify these numbers?

Problem 7

Consider numbers of the form $\sqrt{d}$ where $d \ge 0$ is a square free integer. From which element of the sequence does the sequence become periodic? Use ContinuedFraction.

Problem 8

The convergents of $\sqrt{d}$ for a positive square-free integer $d$ are closely related to the Pell equation

$$\begin{equation} x^2 - d y^2 = 1 \end{equation}$$

Choose $d=7$ and try computing $p_n^2 - d q_n^2$ for the convergents of $\sqrt{d}$ using ContinuedFraction. Keep a list of which pairs satisfy that this difference is $1$. Now do the same for $d=5,6$.

Problem 9

The equation

$$\begin{equation} x^2 - d y^2 = 1 \end{equation}$$

Can be rewritten in the form

$$\begin{equation} \mathrm{N}(x + y \sqrt{d}) = (x - y \sqrt{d})(x + y \sqrt{d}) = 1. \end{equation}$$

Thus Pell's equation secretly seeks for the elements in $\mathbb{Z}[\sqrt{d}]$ with norm $1$.

Choose the first pair $(p_n, q_n)$ from each of the lists you made in the previous problem and compute the powers of $p_n + q_n \sqrt{d}$ using QuadraticPowerTab. What are the first few powers? How are they related to rest of the pairs you have on that list?

Problem 10

Use ContinuedFraction for different $d$ to try to find a pattern for the first convergent that satisfies the Pell equation $x^2 - dy^2 = 1.$