Unit 2: Continued Fractions & Pell's Diophantine Equation

1. Definition of Simple Continued Fractions

Definition 2.1 (Finite Simple Continued Fraction): A finite simple continued fraction is an expression of the form:

where $a_0 \in \mathbb{Z}$ and $a_1, a_2, \dots, a_n \in \mathbb{Z}^+$ ($a_i \ge 1$ for all $i \ge 1$). The integers $a_0, a_1, \dots, a_n$ are called the partial quotients (or partial denominators).

2. Correspondence with the Euclidean Algorithm

Let $r = a/b \in \mathbb{Q}$ with $\gcd(a, b) = 1$ and $b > 0$. Applying the Euclidean algorithm to $a$ and $b$:

Since the Euclidean algorithm terminates in a finite number of steps, we obtain the finite expansion:

Theorem 2.1 (Rational Numbers and Finite Continued Fractions): A real number $x \in \mathbb{R}$ is rational if and only if it can be expressed as a finite simple continued fraction. Furthermore, every rational number has exactly two finite representations:

which ensures uniqueness when requiring the final partial quotient $a_n > 1$.

1. Construction for Irrational Numbers

Let $x = x_0 \in \mathbb{R} \setminus \mathbb{Q}$ be an irrational number. Define iteratively:

Since $x$ is irrational, $x_k - a_k \ne 0$ for all $k$, so this process never terminates, generating an infinite sequence of partial quotients:

2. Convergence of Infinite Continued Fractions

Definition 2.2 (Value of an Infinite Continued Fraction): The value of an infinite simple continued fraction $[a_0; a_1, a_2, \dots]$ is defined as the limit of its finite truncations (convergents):

Theorem 2.2 (Convergence and Bijective Characterization): For any sequence of integers $a_0 \in \mathbb{Z}$ and $a_k \ge 1$ for all $k \ge 1$:

1. The limit $\lim_{n \to \infty} [a_0; a_1, \dots, a_n]$ exists and is an irrational number.
2. There is a canonical bijective correspondence between the set of irrational numbers $\mathbb{R} \setminus \mathbb{Q}$ and the set of infinite simple continued fractions.

1. Recurrence Relations for Convergents

Definition 2.3 (Convergents): For a continued fraction $[a_0; a_1, a_2, \dots]$, the rational number formed by truncating at the $k$-th term:

is called the $k$-th convergent.

Theorem 2.3 (Fundamental Recurrence Relations): The numerators $p_k$ and denominators $q_k$ satisfy the coupled linear recurrences:

with $p_0 = a_0, q_0 = 1$ and $p_1 = a_1 a_0 + 1, q_1 = a_1$.

Proof (by Mathematical Induction): For $k = 0$: $p_0 = a_0, q_0 = 1$. The formula gives $p_0 = a_0(1) + 0 = a_0$ and $q_0 = a_0(0) + 1 = 1$. For $k = 1$: $[a_0; a_1] = a_0 + 1/a_1 = (a_1 a_0 + 1)/a_1$. Recurrence gives $p_1 = a_1 p_0 + p_{-1} = a_1 a_0 + 1$, $q_1 = a_1 q_0 + q_{-1} = a_1(1) + 0 = a_1$. Now assume the relation holds for all $k \le m$. Note that $C_{m+1} = [a_0; a_1, \dots, a_m, a_{m+1}] = [a_0; a_1, \dots, a_{m-1}, a_m + \frac{1}{a_{m+1}}]$. Replacing $a_m$ with $a_m + 1/a_{m+1}$ in the $m$-th convergent:

This completes the induction step. $\blacksquare$

2. Fundamental Determinant Identities

Theorem 2.4 (Determinant Identity): For all $k \ge 0$:

Proof: For $k = 0$: $p_0 q_{-1} - p_{-1} q_0 = a_0(0) - (1)(1) = -1 = (-1)^{-1}$. By induction:

Applying this $k$ times:

Corollary 2.1 (Coprimality of Numerator and Denominator): Dividing by $q_k q_{k-1}$:

In particular, $\gcd(p_k, q_k) = 1$, so all convergents are automatically in reduced fractional form! Moreover, the even convergents increase strictly and the odd convergents decrease strictly:

3. Best Rational Approximations (Dirichlet)

Theorem 2.5 (Dirichlet's Approximation Quality): For any convergent $p_k/q_k$ of an irrational number $x$:

Conversely, if a rational $p/q$ satisfies $\left| x - \frac{p}{q} \right| < \frac{1}{2q^2}$, then $p/q$ is necessarily a convergent of $x$!

1. Quadratic Irrationals

Definition 2.4 (Quadratic Irrational): A real number $\alpha \in \mathbb{R}$ is called a quadratic irrational if it is irrational and satisfies a quadratic equation with integer coefficients:

Equivalently, $\alpha = \frac{P + \sqrt{D}}{Q}$ where $P, Q, D \in \mathbb{Z}$, $D > 0$ is not a perfect square, and $Q \mid (D - P^2)$.

2. Periodic Continued Fractions

Definition 2.5 (Periodic Continued Fraction): An infinite continued fraction is called periodic if its partial quotients eventually repeat:

Here $m$ is the period length. If the repeating block begins at $a_0$ ($k = 0$), it is called purely periodic.

3. Lagrange's Theorem

Theorem 2.6 (Lagrange's Theorem, 1770): An infinite simple continued fraction is periodic if and only if it represents a quadratic irrational number.

Proof ($\implies$ Periodicity implies Quadratic Irrational): Suppose $x = [\overline{a_0; a_1, \dots, a_{m-1}}]$ is purely periodic. Then $x = [a_0; a_1, \dots, a_{m-1}, x]$. In terms of the $m$-th convergent recurrence:

Since $q_{m-1} \ge 1$, this is a non-trivial quadratic equation with integer coefficients. Since the continued fraction is infinite, $x$ cannot be rational. Thus $x$ is a quadratic irrational. The general case where periodicity begins after a pre-period follows identically by fractional linear transformation. $\blacksquare$

Theorem 2.7 (Expansion of $\sqrt{d}$): For any non-square positive integer $d > 0$, the continued fraction of $\sqrt{d}$ has the canonical form:

where $a_0 = \lfloor \sqrt{d} \rfloor$, and the symmetric palindrome property holds:

1. Pell's Equation

Definition 2.6 (Pell's Equation): Let $d \in \mathbb{N}$ be a square-free positive integer ($d \ne k^2$). Pell's Equation is the Diophantine equation:

The companion equation with $-1$:

is called the Negative Pell's Equation.

2. Solving Pell's Equation via Continued Fractions

Factor the left-hand side in the quadratic ring $\mathbb{Z}[\sqrt{d}]$:

Dividing by $y$:

By Dirichlet's best approximation theorem (Theorem 2.5), any solution $(x, y)$ must be a convergent $x/y = p_k/q_k$ of the continued fraction expansion of $\sqrt{d}$!

Theorem 2.8 (Complete Characterization of Pell Solutions): Let $\sqrt{d} = [a_0; \overline{a_1, \dots, a_{m-1}, 2a_0}]$ have period length $m$. Let $p_k / q_k$ be the convergents of $\sqrt{d}$.

1. If the period $m$ is even:

• The fundamental (minimal positive) solution to $x^2 - d y^2 = 1$ is:

• The negative equation $x^2 - d y^2 = -1$ has no integer solutions.

1. If the period $m$ is odd:

• The fundamental solution to $x^2 - d y^2 = -1$ is $x = p_{m-1}, y = q_{m-1}$.
• The fundamental solution to $x^2 - d y^2 = 1$ is:

3. Generation of the Infinite Solution Family

Theorem 2.9 (The Group of Units and All Solutions): Let $(x_1, y_1)$ be the fundamental solution to $x^2 - d y^2 = 1$. Then all positive integer solutions $(x_n, y_n)$ for $n \ge 1$ are generated by powers of the fundamental unit $\epsilon = x_1 + y_1 \sqrt{d}$:

In terms of recurrence relations: