Pell's Equation and Quadratic Irrationals - Continued Fractions Course

The most remarkable structural result in the theory of continued fractions is a perfect correspondence: periodic continued fractions are exactly the quadratic irrationals. This connection, discovered by Lagrange in 1770, leads to a complete solution of Pell’s equation, one of the oldest problems in number theory.

$The golden spiral and continued fractions$

Quadratic Irrationals and Periodic Continued Fractions

Definition (Periodic Continued Fraction). A continued fraction is eventually periodic if there exist integers $ k \geq 0 $ and $ \ell \geq 1 $ such that $ a_{n+\ell} = a_n $ for all $ n \geq k $. We write

$$ \alpha = [a_0; a_1, \ldots, a_{k-1}, \overline{a_k, a_{k+1}, \ldots, a_{k+\ell-1}}]. $$

If $ k = 0 $, the CF is purely periodic: $ \alpha = [\overline{a_0, a_1, \ldots, a_{\ell-1}}] $.

Definition (Quadratic Irrational). A quadratic irrational is a number of the form $ \alpha = (P + \sqrt{D})/Q $ where $ P, Q, D \in \mathbb{Z} $, $ Q \neq 0 $, and $ D > 0 $ is not a perfect square. Its conjugate is $ \bar{\alpha} = (P – \sqrt{D})/Q $.

Lagrange’s Theorem

Important: A real number $ \alpha $ has an eventually periodic continued fraction expansion if and only if $ \alpha $ is a quadratic irrational.

Proof outline.

$ (\Leftarrow) $ Let $ \alpha $ be a quadratic irrational. Each complete quotient $ \alpha_n $ can be written as $ \alpha_n = (P_n + \sqrt{D})/Q_n $ where $ Q_n \mid (D – P_n^2) $. One shows that $ 0 < P_n < \sqrt{D} $ and $ 0 < Q_n < 2\sqrt{D} $ for all $ n \geq 1 $. Since there are finitely many pairs $ (P_n, Q_n) $ satisfying these bounds, by the pigeonhole principle, some $ \alpha_i = \alpha_j $ with $ i < j $, and the CF is periodic from index $ i $ with period $ j – i $. $ (\Rightarrow) $ If $ \alpha = [a_0; a_1, \ldots, a_{k-1}, \overline{a_k, \ldots, a_{k+\ell-1}}] $, let $ \beta = [\overline{a_k, \ldots, a_{k+\ell-1}}] $. Then $ \beta $ satisfies a quadratic equation: from $ \beta = [a_k; a_{k+1}, \ldots, a_{k+\ell-1}, \beta] $, the recurrence gives $$ \beta = \frac{p_{\ell-1}\beta + p_{\ell-2}}{q_{\ell-1}\beta + q_{\ell-2}} $$

which yields $ q_{\ell-1}\beta^2 + (q_{\ell-2} – p_{\ell-1})\beta – p_{\ell-2} = 0 $, so $ \beta $ is a quadratic irrational. Then $ \alpha $, being a Mobius transformation of $ \beta $ with integer coefficients, is also a quadratic irrational. $ \square $

Purely Periodic Continued Fractions

Theorem. A quadratic irrational $ \alpha $ has a purely periodic CF if and only if $ \alpha > 1 $ and its conjugate satisfies $ -1 < \bar{\alpha} < 0 $. Such a quadratic irrational is called reduced.

Example. The purely periodic CF $ \alpha = [\overline{1}] $ satisfies $ \alpha = 1 + 1/\alpha $, giving $ \alpha^2 – \alpha – 1 = 0 $, whose positive root is $ \varphi = (1+\sqrt{5})/2 $. Its conjugate is $ (1-\sqrt{5})/2 \approx -0.618 $, which indeed lies in $ (-1, 0) $.

Similarly, $ \alpha = [\overline{2}] $ satisfies $ \alpha = 2 + 1/\alpha $, giving $ \alpha^2 – 2\alpha – 1 = 0 $, with positive root $ 1 + \sqrt{2} $.

Continued Fractions of Square Roots

For $ \sqrt{D} $ with $ D $ not a perfect square, the CF has a particularly beautiful structure.

Theorem. Let $ D $ be a positive integer that is not a perfect square, and let $ a_0 = \lfloor \sqrt{D} \rfloor $. Then

$$ \sqrt{D} = [a_0; \overline{a_1, a_2, \ldots, a_{\ell-1}, 2a_0}] $$

where the periodic part has a palindromic structure: $ a_i = a_{\ell – i} $ for $ 1 \leq i \leq \ell – 1 $.

Example (Common Square Root Expansions).

$$ \begin{aligned} \sqrt{2} &= [1; \overline{2}] & \text{period } 1\\ \sqrt{3} &= [1; \overline{1, 2}] & \text{period } 2\\ \sqrt{5} &= [2; \overline{4}] & \text{period } 1\\ \sqrt{6} &= [2; \overline{2, 4}] & \text{period } 2\\ \sqrt{7} &= [2; \overline{1, 1, 1, 4}] & \text{period } 4\\ \sqrt{10} &= [3; \overline{6}] & \text{period } 1\\ \sqrt{11} &= [3; \overline{3, 6}] & \text{period } 2\\ \sqrt{13} &= [3; \overline{1, 1, 1, 1, 6}] & \text{period } 5\\ \sqrt{14} &= [3; \overline{1, 2, 1, 6}] & \text{period } 4\\ \sqrt{19} &= [4; \overline{2, 1, 3, 1, 2, 8}] & \text{period } 6 \end{aligned} $$

Note the palindromic structure in each period (excluding the final term $ 2a_0 $): in $ \sqrt{7} = [2; \overline{1,1,1,4}] $, the sub-sequence $ 1,1,1 $ is a palindrome; in $ \sqrt{19} = [4; \overline{2,1,3,1,2,8}] $, the sub-sequence $ 2,1,3,1,2 $ is a palindrome.

The Golden Ratio: The Most Irrational Number

The golden ratio $ \varphi = [1; \overline{1}] $ is the “hardest” irrational number to approximate by rationals, in the sense that its partial quotients are all as small as possible (all equal to 1). Since the quality of rational approximation improves with large partial quotients, having all partial quotients equal to 1 makes $ \varphi $ the worst-approximated irrational.

The convergents of $ \varphi $ are ratios of consecutive Fibonacci numbers:

$$ \frac{p_n}{q_n} = \frac{F_{n+2}}{F_{n+1}}: \quad \frac{1}{1}, \frac{2}{1}, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \frac{13}{8}, \frac{21}{13}, \ldots $$

The Fibonacci and Lucas numbers are further connected by the identity $ L_n^2 – 5F_n^2 = 4(-1)^n $, a disguised form of the Pell equation for $ D = 5 $.

Pell’s Equation

One of the most spectacular applications of continued fractions is to Pell’s equation.

Definition. For a positive integer $ D $ that is not a perfect square, Pell’s equation is

$$ x^2 – Dy^2 = 1, \quad x, y \in \mathbb{Z}. $$

The negative Pell equation is $ x^2 – Dy^2 = -1 $.

Solution via Continued Fractions

Important: Let $ \sqrt{D} = [a_0; \overline{a_1, \ldots, a_\ell}] $ with period length $ \ell $, and let $ p_n/q_n $ denote the convergents. Then:

(i) The fundamental solution $ (x_1, y_1) $ of $ x^2 – Dy^2 = 1 $ is given by $ (x_1, y_1) = (p_{\ell-1}, q_{\ell-1}) $ if $ \ell $ is even, or $ (x_1, y_1) = (p_{2\ell-1}, q_{2\ell-1}) $ if $ \ell $ is odd.

(ii) If $ \ell $ is odd, then $ (p_{\ell-1}, q_{\ell-1}) $ solves the negative Pell equation $ x^2 – Dy^2 = -1 $.

(iii) All positive solutions are generated by $ (x_n + y_n\sqrt{D}) = (x_1 + y_1\sqrt{D})^n $ for $ n = 1, 2, 3, \ldots $

The key identity is: for the convergents of $ \sqrt{D} $, we have $ p_n^2 – D q_n^2 = (-1)^{n+1} Q_{n+1} $ where $ Q_{n+1} $ comes from the complete quotient $ \alpha_{n+1} = (P_{n+1} + \sqrt{D})/Q_{n+1} $. At the end of a full period, $ Q_\ell = 1 $, giving $ p_{\ell-1}^2 – D q_{\ell-1}^2 = (-1)^\ell $.

Worked Examples

$ D = 2 $: $ x^2 – 2y^2 = 1 $. We have $ \sqrt{2} = [1; \overline{2}] $ with period $ \ell = 1 $ (odd). The convergent at $ \ell – 1 = 0 $ is $ p_0/q_0 = 1/1 $, and $ 1^2 – 2 \cdot 1^2 = -1 $. So the negative Pell equation has solution $ (1, 1) $. For the positive equation, we go to $ 2\ell – 1 = 1 $: $ p_1/q_1 = 3/2 $. Check: $ 9 – 8 = 1 $. Fundamental solution: $ (3, 2) $.

Subsequent solutions via $ (3 + 2\sqrt{2})^n $:

$$ \begin{aligned} n=2: &\quad (3 + 2\sqrt{2})^2 = 17 + 12\sqrt{2} \implies (17, 12),\\ n=3: &\quad (3 + 2\sqrt{2})^3 = 99 + 70\sqrt{2} \implies (99, 70),\\ n=4: &\quad (3 + 2\sqrt{2})^4 = 577 + 408\sqrt{2} \implies (577, 408). \end{aligned} $$

Check: $ 577^2 – 2 \cdot 408^2 = 332929 – 332928 = 1 $.

$ D = 3 $: $ x^2 – 3y^2 = 1 $. $ \sqrt{3} = [1; \overline{1, 2}] $, period $ \ell = 2 $ (even). Convergent at $ \ell – 1 = 1 $: $ p_1/q_1 = 2/1 $. Check: $ 4 – 3 = 1 $. Fundamental solution: $ (2, 1) $.

$ D = 7 $: $ x^2 – 7y^2 = 1 $. $ \sqrt{7} = [2; \overline{1, 1, 1, 4}] $, period $ \ell = 4 $ (even). Computing convergents:

$ n $: $ a_n $ | $ -2 $: | $ -1 $: | 0: 2 | 1: 1 | 2: 1 | 3: 1
$ n $: $ p_n $ | $ -2 $: 0 | $ -1 $: 1 | 0: 2 | 1: 3 | 2: 5 | 3: 8
$ n $: $ q_n $ | $ -2 $: 1 | $ -1 $: 0 | 0: 1 | 1: 1 | 2: 2 | 3: 3
The convergent at $ \ell – 1 = 3 $ is $ 8/3 $. Check: $ 64 – 63 = 1 $. Fundamental solution: $ (8, 3) $.

$ D = 13 $: Negative Pell Equation. $ \sqrt{13} = [3; \overline{1, 1, 1, 1, 6}] $, period $ \ell = 5 $ (odd). The convergent at $ \ell – 1 = 4 $ is $ 18/5 $: $ 324 – 325 = -1 $. So $ x^2 – 13y^2 = -1 $ has solution $ (18, 5) $. The fundamental solution to the positive equation is $ (649, 180) $, from $ (18 + 5\sqrt{13})^2 $.

$ D = 61 $: A Famous Example. The equation $ x^2 – 61y^2 = 1 $ has the astonishingly large fundamental solution

$$ (x_1, y_1) = (1\,766\,319\,049,\; 226\,153\,980). $$

This was known to Bhaskara II in the 12th century, who found it using the chakravala method, an algorithm developed by Jayadeva (c. 950 CE) that can be viewed as a precursor to the CF method.

Summary Table

$ D $: 2 | CF of $ \sqrt{D} $: $ [1; \overline{2}] $ | Period $ \ell $: 1 | Fundamental solution: $ (3, 2) $ | $ x^2 – Dy^2 = -1 $?: Yes: $ (1, 1) $
$ D $: 3 | CF of $ \sqrt{D} $: $ [1; \overline{1, 2}] $ | Period $ \ell $: 2 | Fundamental solution: $ (2, 1) $ | $ x^2 – Dy^2 = -1 $?: No
$ D $: 5 | CF of $ \sqrt{D} $: $ [2; \overline{4}] $ | Period $ \ell $: 1 | Fundamental solution: $ (9, 4) $ | $ x^2 – Dy^2 = -1 $?: Yes: $ (2, 1) $
$ D $: 7 | CF of $ \sqrt{D} $: $ [2; \overline{1,1,1,4}] $ | Period $ \ell $: 4 | Fundamental solution: $ (8, 3) $ | $ x^2 – Dy^2 = -1 $?: No
$ D $: 13 | CF of $ \sqrt{D} $: $ [3; \overline{1,1,1,1,6}] $ | Period $ \ell $: 5 | Fundamental solution: $ (649, 180) $ | $ x^2 – Dy^2 = -1 $?: Yes: $ (18, 5) $
$ D $: 61 | CF of $ \sqrt{D} $: $ [7; \overline{1,4,3,1,2,2,1,3,4,1,14}] $ | Period $ \ell $: 11 | Fundamental solution: $ (1766319049, 226153980) $ | $ x^2 – Dy^2 = -1 $?: Yes

Tip: The negative Pell equation $ x^2 – Dy^2 = -1 $ has solutions if and only if the period length $ \ell $ of $ \sqrt{D} $ is odd.

Generating All Solutions

Proposition. If $ (x_1, y_1) $ is the fundamental solution of $ x^2 – Dy^2 = 1 $, then all positive solutions are given by

$$ x_n + y_n \sqrt{D} = (x_1 + y_1\sqrt{D})^n, \quad n = 1, 2, 3, \ldots $$

Equivalently, $ x_n $ and $ y_n $ satisfy the recurrences

$$ \begin{aligned} x_{n+1} &= x_1 x_n + D y_1 y_n, \\ y_{n+1} &= y_1 x_n + x_1 y_n. \end{aligned} $$

Proof. The solutions form a group under the operation $ (x_1, y_1) * (x_2, y_2) = (x_1 x_2 + D y_1 y_2, x_1 y_2 + x_2 y_1) $, corresponding to multiplication of elements $ x + y\sqrt{D} $ in $ \mathbb{Z}[\sqrt{D}] $. By Dirichlet’s unit theorem for real quadratic fields, the positive solutions form a cyclic group generated by the fundamental solution. $ \square $

Hurwitz’s Theorem

The theory of Diophantine approximation asks: how well can irrational numbers be approximated by rationals?

Theorem (Dirichlet). For any irrational $ \alpha $ and any positive integer $ N $, there exists a fraction $ p/q $ with $ 1 \leq q \leq N $ such that

$$ \left|\alpha – \frac{p}{q}\right| < \frac{1}{qN} \leq \frac{1}{q^2}. $$

In particular, there are infinitely many fractions $ p/q $ with $ |\alpha – p/q| < 1/q^2 $.

Hurwitz’s theorem provides the optimal improvement of the constant:

Important: For any irrational number $ \alpha $, there are infinitely many fractions $ p/q $ satisfying
$$ > \left|\alpha – \frac{p}{q}\right| < \frac{1}{\sqrt{5}\, q^2}. > $$
The constant $ \sqrt{5} $ is best possible: if $ \sqrt{5} $ is replaced by any larger constant, the theorem fails for $ \alpha = \varphi = (1+\sqrt{5})/2 $.

Proof sketch. Consider three consecutive convergents $ p_{n-1}/q_{n-1} $, $ p_n/q_n $, $ p_{n+1}/q_{n+1} $. At least one of them satisfies the inequality. If all three fail, setting $ r = q_{n-1}/q_n $ and $ s = q_{n+1}/q_n $, one derives that $ r + 1/r \leq \sqrt{5} $ and $ s + 1/s \leq \sqrt{5} $, forcing $ r = 1/\varphi $ and $ s = \varphi $ exactly, meaning all partial quotients equal 1. This forces $ \alpha $ to be equivalent to $ \varphi $. For sharpness, the convergents of $ \varphi $ satisfy $ |\varphi – F_{n+1}/F_n| \sim 1/(\sqrt{5}\, F_n^2) $, achieving exactly the $ \sqrt{5} $ bound. $ \square $

The Markov Spectrum

After removing the golden ratio equivalence class, one can improve the constant. The “spectrum” of best approximation constants begins:

$ \sqrt{5} $ for $ \varphi $ and its equivalents,
$ \sqrt{8} $ for $ \sqrt{2} $ and its equivalents,
$ \sqrt{221}/5 $ for $ (\sqrt{221}+9)/10 $ and its equivalents.

The Markov constants are $ \sqrt{9m^2 – 4}/m $ where $ m $ ranges over the Markov numbers: $ 1, 2, 5, 13, 29, 34, 89, 169, \ldots $, the solutions to

$$ m_1^2 + m_2^2 + m_3^2 = 3m_1 m_2 m_3. $$

These constants accumulate at 3 from below, and above 3 the spectrum becomes continuous (Hall’s theorem).

Liouville’s Inequality and Transcendence

Theorem (Liouville, 1844). If $ \alpha $ is an algebraic number of degree $ n \geq 2 $, then there exists a constant $ c > 0 $ such that for all $ p/q \in \mathbb{Q} $,

$$ \left|\alpha – \frac{p}{q}\right| > \frac{c}{q^n}. $$

Proof. Let $ f(x) $ be the minimal polynomial of $ \alpha $ over $ \mathbb{Z} $. For rational $ p/q $ with $ f(p/q) \neq 0 $, the numerator $ |q^n f(p/q)| $ is a nonzero integer, so $ |f(p/q)| \geq 1/q^n $. By the mean value theorem, $ |f(p/q)| \leq M|p/q – \alpha| $, giving the result. $ \square $

Corollary. The Liouville number $ L = \sum_{k=1}^{\infty} 10^{-k!} = 0.110001000000000000000001\ldots $ is transcendental. Its partial sums approximate it so well (faster than any polynomial rate in the denominator) that it cannot be algebraic of any finite degree.

Tip: The irrationality measure $ \mu(\alpha) $ is the infimum of exponents $ \mu $ such that $ |\alpha – p/q| > q^{-\mu} $ has only finitely many solutions. By Dirichlet, $ \mu(\alpha) \geq 2 $ for all irrationals. By Roth’s theorem (1955, Fields Medal), $ \mu(\alpha) = 2 $ for all algebraic irrationals. Liouville numbers have $ \mu = \infty $.

Exercises

Find the continued fraction of $ \sqrt{23} $ and identify the period length and palindromic structure.
Use the CF of $ \sqrt{2} $ to find the first 4 solutions of $ x^2 – 2y^2 = 1 $.
Determine whether $ x^2 – 10y^2 = -1 $ has solutions by examining the period length of $ \sqrt{10} $.
Prove that $ [\overline{3}] $ satisfies a quadratic equation and find its value.
The Pell equation $ x^2 – 29y^2 = 1 $ has fundamental solution $ (9801, 1820) $. Verify this using the CF of $ \sqrt{29} $.
Show that if $ \alpha = (P + \sqrt{D})/Q $ is a reduced quadratic irrational (i.e., $ \alpha > 1 $ and $ -1 < \bar{\alpha} < 0 $), then the first partial quotient $ a_0 = \lfloor \alpha \rfloor $ satisfies $ a_0 \geq 1 $.
Construct a transcendental number whose CF expansion is $ [0; 1!, 2!, 3!, 4!, \ldots] $ and explain why Liouville’s theorem guarantees it is transcendental.