Pell equation and continued fractions

Intuition Beginner

The Pell equation is the integer equation $x^2-D{y}^2=1$ for a fixed positive integer $D$ that is not a perfect square. The unknowns $x,y$ are positive integers, and the question is whether interesting solutions exist beyond the boring case $(1,0)$. That boring pair $(x,y)=(1,0)$ always works; what we want is positive-integer pairs with $y\ge 1$.

A cattle problem. Bhaskara II's Bījagaṇita (1150 CE) poses, in a cattle-counting puzzle, the question: find positive integers $x,y$ with $x^2-8y^2=1$. Test small $y$. For $y=1$ we need $x^2=9$, so $x=3$. The pair $(3,1)$ solves $9-8=1$.

Bhaskara's actual cattle problems demanded much larger $D$ values. The famous $D=61$ case has minimal solution $x=1766319049$, $y=226153980$ — a $10$-digit number found by chakravala in 1150 CE, then re-discovered by Brouncker in 1657 in response to a challenge from Fermat. For the small $D=2$ case the answer is $(x,y)=(3,2)$: $9-8=1$.

Why is $D$ required to be non-square? If $D=d^2$ is a perfect square, the left-hand side factors as $(x-dy)(x+dy)=1$, so the only integer solutions are $(x-dy,x+dy)=(\pm 1,\pm 1)$ with the signs matched. This gives $x=\pm 1$ and $y=0$, the degenerate cases. So the equation is interesting exactly when $D$ is not a perfect square — and then it always has infinitely many positive-integer solutions, as Lagrange proved in 1770.

Solutions multiply. The deeper observation, going back to Brahmagupta in 628 CE, is that two solutions multiply to make a new solution. If $(x_1,y_1)$ and $(x_2,y_2)$ both solve $x^2-D{y}^2=1$, consider the product $(x_1+y_1\sqrt{D})(x_2+y_2\sqrt{D})=(x_1{x}_2+D{y}_1{y}_2)+(x_1{y}_2+x_2{y}_1)\sqrt{D}$.

Writing $X=x_1{x}_2+D{y}_1{y}_2$ and $Y=x_1{y}_2+x_2{y}_1$, the algebraic identity $(a+b)(a-b)=a^2-b^2$ applied to the conjugate pair gives $X^2-D{Y}^2=(x_1^2-D{y}_1^2)(x_2^2-D{y}_2^2)=1\cdot 1=1$. So $(X,Y)$ is another Pell solution. Iterating with a fixed minimal solution $(x_1,y_1)$ generates an infinite chain of solutions.

The minimal solution. Among all positive-integer Pell solutions $(x,y)$ with $y\ge 1$, there is a smallest one — the fundamental solution, denoted $(x_1,y_1)$. Every other positive-integer solution is generated by multiplying $x_1+y_1\sqrt{D}$ by itself: the $n$-th power $(x_1+y_1\sqrt{D}{)}^n=x_n+y_n\sqrt{D}$ gives the $n$-th positive solution $(x_n,y_n)$. So once the fundamental solution is in hand, every other solution is one matrix-multiplication away. The hard work is finding the fundamental solution — and this is where continued fractions enter.

Why does it matter? Pell equations are the elementary face of the unit group of the ring $\mathbb{Z}[\sqrt{D}]$ — the multiplicative group of elements $\alpha =x+y\sqrt{D}$ with norm $\alpha \bar{\alpha }=x^2-D{y}^2=\pm 1$. The fundamental Pell solution is the fundamental unit, and the full solution group is generated by it.

Solving $x^2-2y^2=1$ to find $(3,2)$ is, in disguise, computing the unit group of $\mathbb{Z}[\sqrt{2}]$ as the infinite cyclic group $⟨1+\sqrt{2}⟩\times \{\pm 1\}$. This is the entry point to the theory of units in number fields, which culminates in the Dirichlet unit theorem (1846) for general number fields.

Visual Beginner

The Pell solutions $(x,y)$ are integer points on the hyperbola $x^2-D{y}^2=1$. For $D=2$ the hyperbola is $x^2-2y^2=1$, and the picture shows the first few lattice points on its right branch.

The picture captures the central structural fact: Pell solutions are integer points on a hyperbola, with consecutive solutions related by multiplication by the fundamental unit. The ratios $y_n/x_n$ are best rational approximations to $1/\sqrt{D}$ in the sense that no rational with smaller denominator gets closer — the convergents of the continued-fraction expansion of $1/\sqrt{D}$. This is the geometric bridge between Pell, continued fractions, and Diophantine approximation.

Worked example Beginner

Find all positive-integer solutions of $x^2-2y^2=1$ up to $y\le 100$, and verify the multiplication law.

Step 1. Find the fundamental solution by inspection of small $y$. For $y=1$ we need $x^2=3$, no integer. For $y=2$ we need $x^2=9$, so $x=3$. The fundamental solution is therefore $(x_1,y_1)=(3,2)$. Check: $9-8=1$.

Step 2. Generate the next solution by the multiplication law. Compute $(3+2\sqrt{2}{)}^2=9+12\sqrt{2}+8=17+12\sqrt{2}$, so $(x_2,y_2)=(17,12)$. Check: $289-288=1$.

Step 3. Generate the next solution. Compute $(3+2\sqrt{2}{)}^3=(3+2\sqrt{2})(17+12\sqrt{2})=51+36\sqrt{2}+34\sqrt{2}+48=99+70\sqrt{2}$, so $(x_3,y_3)=(99,70)$. Check: $9801-9800=1$.

Step 4. The next solution would be $(x_4,y_4)=(577,408)$ with $y_4=408>100$, so we stop. The complete list of positive-integer solutions with $y\le 100$ is $(3,2),(17,12),(99,70)$.

Step 5. Verify uniqueness by exhaustion. For each $y\in \{1,2,\dots ,100\}$, compute $2y^2+1$ and test whether it is a perfect square. The only values of $y$ in this range that give a perfect square are $y=2,12,70$, matching our list. So the three solutions are the only ones in this range.

Step 6. Verify the multiplication law more explicitly. The recursion $(x_{n+1},y_{n+1})=(3x_n+4y_n,2x_n+3y_n)$ follows from $(x_n+y_n\sqrt{2})(3+2\sqrt{2})=(3x_n+4y_n)+(2x_n+3y_n)\sqrt{2}$.

Starting from $(x_1,y_1)=(3,2)$: $(x_2,y_2)=(3\cdot 3+4\cdot 2,2\cdot 3+3\cdot 2)=(17,12)$. From $(17,12)$: $(x_3,y_3)=(3\cdot 17+4\cdot 12,2\cdot 17+3\cdot 12)=(99,70)$. The recursion grows the solutions by a factor of $3+2\sqrt{2}\approx 5.83$ at each step.

The same algorithm works for any non-square $D$, but the fundamental solution can be astronomically large. For $D=61$, the smallest case Fermat chose to challenge the English in 1657, the fundamental solution is $(1766319049,226153980)$ — a $10$-digit answer that Bhaskara II found by chakravala in 1150 CE without paper or modern arithmetic notation.

Check your understanding Beginner

Formal definition Intermediate+

We restate the Pell-equation setup precisely.

Definition (Pell equation). For $D$ a positive integer that is not a perfect square, the Pell equation is $x^2-D{y}^2=1$ in positive integers $x,y$. A pair $(x,y)\in {\mathbb{Z}}_{>0}^2$ with $x^2-D{y}^2=1$ is a Pell solution. The fundamental solution is the solution with smallest $y_1\ge 1$, equivalently the solution with smallest $x_1+y_1\sqrt{D}$ subject to $x_1,y_1\ge 1$.

Definition (negative Pell equation). The equation $x^2-D{y}^2=-1$ is the negative Pell equation. Unlike the Pell equation, the negative Pell equation is not always solvable: solutions exist iff the period of the continued-fraction expansion of $\sqrt{D}$ is odd (proved in the Key Theorem below).

Definition (generalised Pell equation). For $N\in \mathbb{Z}$ non-zero, the generalised Pell equation is $x^2-D{y}^2=N$ in integers $x,y$. The set of solutions, when non-empty, is a finite union of orbits under the multiplicative action of the Pell unit group $\{\pm (x_1+y_1\sqrt{D}{)}^n:n\in \mathbb{Z}\}$ on $\mathbb{Z}[\sqrt{D}]$.

Definition (continued fraction). For $\alpha \in \mathbb{R}$, the continued-fraction expansion is the sequence $\alpha =[a_0;a_1,a_2,a_3,\dots ]$ produced by the recursion $$ \alpha_0 = \alpha, \qquad a_n = \lfloor \alpha_n \rfloor, \qquad \alpha_{n + 1} = \frac{1}{\alpha_n - a_n} $$ (continuing as long as ${\alpha }_n$ is not an integer). The $a_n$ are the partial quotients, all integers with $a_n\ge 1$ for $n\ge 1$. The convergents are the rationals $$ \frac{p_n}{q_n} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}} $$ computed by the linear recursion $p_n=a_n{p}_{n-1}+p_{n-2}$, $q_n=a_n{q}_{n-1}+q_{n-2}$ with initial values $p_{-1}=1,p_{-2}=0$, $q_{-1}=0,q_{-2}=1$.

Definition (purely periodic and reduced quadratic irrationals). A real number $\alpha$ is a quadratic irrational iff $\alpha$ satisfies an irreducible quadratic polynomial with rational coefficients. The continued fraction $[a_0;\overline{a_1,\dots ,a_{\ell }}]$ is purely periodic with period $\ell$ iff $a_{n+\ell }=a_n$ for all $n\ge 0$, equivalently $\alpha ={\alpha }_{\ell }$. A quadratic irrational $\alpha$ is reduced iff $\alpha >1$ and $-1<\bar{\alpha }<0$, where $\bar{\alpha }$ is the algebraic conjugate.

The convergents $p_n/q_n$ satisfy $\gcd (p_n,q_n)=1$ and the best-approximation property: for every rational $p/q$ with $1\le q\le q_n$, $|q_n\alpha -p_n|\le |q\alpha -p|$, with equality only if $p/q=p_n/q_n$. The cross-ratio identity $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n-1}$ holds for all $n\ge 0$.

Counterexamples to common slips

• "The Pell equation has the degenerate solution $(1,0)$ counted as fundamental." The fundamental solution is the smallest positive-integer solution with $y\ge 1$, not the degenerate $(1,0)$. The degenerate solution corresponds to the unit $1\in \mathbb{Z}[\sqrt{D}{]}^{\times }$, not to a generator of the infinite-cyclic part of the unit group.

• "$D$ negative gives an interesting Pell equation." False. For $D<0$, the equation $x^2+|D|y^2=1$ has only finitely many integer solutions (in fact at most four: $(\pm 1,0)$ when $|D|>1$, and four solutions when $|D|=1$). The infinite-solution-set phenomenon is specific to indefinite quadratic forms — i.e., $D>0$ non-square.

• "The continued-fraction expansion of every irrational is eventually periodic." False. Lagrange's theorem says $\alpha$ has eventually-periodic continued fraction iff $\alpha$ is a quadratic irrational. For algebraic numbers of degree $\ge 3$ or transcendental numbers like $e$ and $\pi$, the continued fraction is non-periodic. (The continued fraction of $e=[2;1,2,1,1,4,1,1,6,1,1,8,\dots ]$ has a pattern but is not periodic.)

• "The negative Pell equation $x^2-D{y}^2=-1$ is always solvable for $D$ non-square." False. The negative Pell equation is solvable iff the period of $\sqrt{D}$'s continued fraction is odd. Examples: $D=2$ has period $1$ (odd), so $-1$ is solvable: $1^2-2\cdot 1^2=-1$. $D=3$ has period $2$ (even), so $-1$ is not solvable. $D=5$ has period $1$ (odd), solvable: $2^2-5\cdot 1^2=-1$. $D=6$ has period $2$ (even), not solvable. The criterion is a deep consequence of Lagrange's algorithm.

• "The Liouville bound applies to all real numbers." False. Liouville's theorem applies only to algebraic numbers: if $\alpha$ has degree $n$, then $|\alpha -p/q|>c(\alpha )q^{-n}$ for all rationals $p/q$. For transcendental $\alpha$, no such bound exists — and Liouville used this to construct the first explicit transcendental numbers as those violating the bound for every $n$.

Key theorem with proof Intermediate+

The signature theorem of this unit is Lagrange's theorem on the existence of Pell solutions via continued fractions. We prove it via the periodicity of quadratic-irrational continued fractions.

Theorem (Lagrange 1770, Pell solvability via continued fractions). Let $D$ be a positive integer that is not a perfect square. Let $\sqrt{D}=[a_0;\overline{a_1,a_2,\dots ,a_{\ell }}]$ be the continued-fraction expansion, with period $\ell \ge 1$. Let $p_n/q_n$ be the convergents. Then:

(a) The continued fraction of $\sqrt{D}$ is eventually periodic, with $a_n=a_{n-\ell +1}$ for all $n\ge 1$ and $a_{\ell }=2a_0$.

(b) The convergent $p_{\ell -1}/q_{\ell -1}$ satisfies $p_{\ell -1}^2-D{q}_{\ell -1}^2=(-1{)}^{\ell }$. If $\ell$ is even, $(p_{\ell -1},q_{\ell -1})$ is the fundamental Pell solution. If $\ell$ is odd, $(p_{\ell -1},q_{\ell -1})$ solves the negative Pell equation, and the fundamental Pell solution is $(p_{2\ell -1},q_{2\ell -1})$.

(c) Every positive Pell solution is $(p_{m\ell -1},q_{m\ell -1})$ for some integer $m\ge 1$ (with $m\ell$ taken to be even).

Proof. We establish the three parts in sequence.

Step 1 — Periodicity of the continued fraction of $\sqrt{D}$. The expansion $\sqrt{D}=[a_0;a_1,a_2,\dots ]$ is generated by the recursion ${\alpha }_0=\sqrt{D}$, $a_n=\lfloor {\alpha }_n\rfloor$, ${\alpha }_{n+1}=1/({\alpha }_n-a_n)$. We claim each ${\alpha }_n$ is a quadratic irrational of the form ${\alpha }_n=(P_n+\sqrt{D})/Q_n$ with $P_n,Q_n\in \mathbb{Z}$, $Q_n\mid D-P_n^2$, and (for $n\ge 1$) ${\alpha }_n$ is reduced.

Induction on $n$. Base case $n=0$: ${\alpha }_0=\sqrt{D}=(0+\sqrt{D})/1$, so $P_0=0$ and $Q_0=1$; ${\alpha }_0$ is not reduced (since ${\bar{\alpha }}_0=-\sqrt{D}<-1$), but the reducedness will hold for $n\ge 1$.

Inductive step. Suppose ${\alpha }_n=(P_n+\sqrt{D})/Q_n$ with $Q_n\mid D-P_n^2$. Then $a_n=\lfloor {\alpha }_n\rfloor$, and $$ \alpha_{n + 1} = \frac{1}{\alpha_n - a_n} = \frac{Q_n}{P_n - a_n Q_n + \sqrt D} = \frac{Q_n (a_n Q_n - P_n + \sqrt D)}{D - (P_n - a_n Q_n)^2}. $$ Set $P_{n+1}=a_n{Q}_n-P_n$ and $Q_{n+1}=(D-P_{n+1}^2)/Q_n$. We must verify $Q_{n+1}\in \mathbb{Z}$ and $Q_{n+1}\mid D-P_{n+1}^2$. The first: $D-P_{n+1}^2=D-(a_n{Q}_n-P_n{)}^2=D-a_n^2{Q}_n^2+2a_n{Q}_n{P}_n-P_n^2$. By the inductive hypothesis $Q_n\mid D-P_n^2$, and the other terms are multiples of $Q_n$, so $Q_n\mid D-P_{n+1}^2$ and $Q_{n+1}=(D-P_{n+1}^2)/Q_n\in \mathbb{Z}$. The second: $D-P_{n+1}^2=Q_n{Q}_{n+1}$, so $Q_{n+1}\mid D-P_{n+1}^2$.

Reducedness for $n\ge 1$: we show ${\alpha }_n>1$ and $-1<{\bar{\alpha }}_n<0$. The first is immediate since $a_n\ge 1$ in the recursion. The second is a standard induction: if ${\alpha }_n$ is reduced, then ${\bar{\alpha }}_{n+1}=1/({\bar{\alpha }}_n-a_n)\in (-1,0)$ because ${\bar{\alpha }}_n-a_n<-a_n\le -1$, so $|{\bar{\alpha }}_n-a_n|>1$, hence $|1/({\bar{\alpha }}_n-a_n)|<1$, and the sign is negative because ${\bar{\alpha }}_n-a_n<0$.

Now the key finiteness: for reduced ${\alpha }_n=(P_n+\sqrt{D})/Q_n$, the integers $P_n,Q_n$ are bounded. Reducedness gives ${\alpha }_n>1$ and ${\bar{\alpha }}_n=(P_n-\sqrt{D})/Q_n\in (-1,0)$. Adding: ${\alpha }_n+{\bar{\alpha }}_n=2P_n/Q_n$, so $P_n/Q_n\in (0,{\alpha }_n/2+1)$. Subtracting: ${\alpha }_n-{\bar{\alpha }}_n=2\sqrt{D}/Q_n>0$, so $Q_n>0$. From ${\bar{\alpha }}_n\in (-1,0)$, $P_n-\sqrt{D}\in (-Q_n,0)$, so $\sqrt{D}-Q_n<P_n<\sqrt{D}$. From ${\alpha }_n>1$, $P_n+\sqrt{D}>Q_n$, so $P_n>Q_n-\sqrt{D}$. Combining: $\max (0,Q_n-\sqrt{D})<P_n<\sqrt{D}$, and $Q_n<2\sqrt{D}$ (from ${\alpha }_n\cdot |{\bar{\alpha }}_n|=|D-P_n^2|/Q_n^2\le 1$ and a short manipulation). So $P_n,Q_n$ each take only finitely many integer values.

Since the pair $(P_n,Q_n)$ determines ${\alpha }_n$ and there are only finitely many possible pairs, the sequence ${\alpha }_1,{\alpha }_2,\dots$ must repeat. The first repetition gives the period $\ell$, and the algorithm is periodic from index $1$ onward.

The final identity $a_{\ell }=2a_0$ is a standard consequence of the conjugation symmetry of the recursion (see Hardy-Wright §10.10).

Step 2 — Pell solutions from convergents. The convergents $p_n/q_n$ of the continued fraction of $\sqrt{D}$ satisfy the basic identity $$ p_n^2 - D q_n^2 = (-1)^{n + 1} Q_{n + 1}, $$ where $Q_{n+1}$ is the denominator in the recursion of Step 1. (Proof: induction on $n$; the base case $n=0$ gives $a_0^2-D=-Q_1$, and the step uses the recursion $p_n=a_n{p}_{n-1}+p_{n-2}$ together with ${\alpha }_{n+1}=(P_{n+1}+\sqrt{D})/Q_{n+1}$.)

At $n=\ell -1$: $Q_{\ell }=Q_0=1$ (since the period closes at index $\ell$, so ${\alpha }_{\ell }={\alpha }_0$ and the denominators match). Hence $$ p_{\ell - 1}^2 - D q_{\ell - 1}^2 = (-1)^\ell. $$

If $\ell$ is even, $(p_{\ell -1},q_{\ell -1})$ satisfies $x^2-D{y}^2=1$, a Pell solution.

If $\ell$ is odd, $(p_{\ell -1},q_{\ell -1})$ satisfies $x^2-D{y}^2=-1$, a negative-Pell solution. Squaring the negative-Pell solution as an element of $\mathbb{Z}[\sqrt{D}]$: $(p_{\ell -1}+q_{\ell -1}\sqrt{D}{)}^2=(p_{\ell -1}^2+D{q}_{\ell -1}^2)+2p_{\ell -1}{q}_{\ell -1}\sqrt{D}$. The norm is $(-1{)}^2=1$, so the rational and irrational parts $(p_{\ell -1}^2+D{q}_{\ell -1}^2,2p_{\ell -1}{q}_{\ell -1})$ form a Pell solution. The same is $(p_{2\ell -1},q_{2\ell -1})$ by the convergent identity applied at index $2\ell -1$ (using $Q_{2\ell }=Q_0=1$ from period-$\ell$ structure repeated twice).

Step 3 — Fundamental solution and complete generation. Suppose $(x,y)$ is any positive Pell solution with $y\ge 1$. We show $(x,y)=(p_{m\ell -1},q_{m\ell -1})$ for some $m\ge 1$. The best-approximation property of convergents says: for every rational $p/q$ with $|q\sqrt{D}-p|<1/(2q)$, $p/q$ must be a convergent of $\sqrt{D}$. From $x^2-D{y}^2=1$, we have $x-y\sqrt{D}=1/(x+y\sqrt{D})$, so $|x-y\sqrt{D}|=1/(x+y\sqrt{D})<1/(2y\sqrt{D})<1/(2y)$ (using $x+y\sqrt{D}>2y\sqrt{D}$ for $x,y\ge 1$). Hence $x/y$ is a convergent, $x/y=p_n/q_n$, and since $\gcd (p_n,q_n)=1=\gcd (x,y)$ (the latter from $x^2-D{y}^2=1$), $(x,y)=(p_n,q_n)$.

The convergent identity $p_n^2-D{q}_n^2=(-1{)}^{n+1}{Q}_{n+1}$ shows $(p_n,q_n)$ is a Pell solution iff $Q_{n+1}=1$ and $n$ is odd. Since $Q_{n+1}=1$ holds exactly when the index $n+1$ is a multiple of $\ell$ (from periodicity), the Pell solutions are precisely $(p_{m\ell -1},q_{m\ell -1})$ for $m\ge 1$ (with $m\ell$ even, i.e., $m$ even when $\ell$ is odd and $m$ arbitrary when $\ell$ is even). The fundamental Pell solution is the one with smallest $m$. $\square$

Bridge. Lagrange's theorem is the elementary face of the Dirichlet unit theorem: for the real quadratic field $K=\mathbb{Q}(\sqrt{D})$ with $D>0$ non-square, the unit group of the ring of integers ${\mathcal{O}}_K$ is ${\mathcal{O}}_K^{\times }=\{\pm 1\}\times ⟨\epsilon ⟩$ where $\epsilon$ is the fundamental unit. The fundamental unit corresponds to the fundamental Pell (or negative-Pell) solution: when the negative-Pell equation is solvable, $\epsilon$ has norm $-1$ and ${\epsilon }^2$ generates the Pell solutions; when it is not solvable, $\epsilon$ itself has norm $+1$ and generates the Pell solutions directly. This is the first substantive instance of the general Dirichlet unit theorem (Dirichlet 1846), which gives the rank of the unit group of any number field as $r_1+r_2-1$ where $r_1,r_2$ are the numbers of real and complex embeddings. For real quadratic $K$ the rank is $2-1=1$, so the free part is infinite cyclic, generated by the fundamental unit — Pell.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib provides scattered pieces of the Pell-and-continued-fractions infrastructure, but no unified pedagogical module.

-- Operative imports: Mathlib.NumberTheory.Pell,
-- Mathlib.NumberTheory.Zsqrtd.Basic,
-- Mathlib.Analysis.SpecialFunctions.ContinuedFractions

#check @Pell.xn
-- The x-coordinate of the n-th positive Pell solution for non-square D.

#check @Pell.yn
-- The y-coordinate of the n-th positive Pell solution.

#check @Pell.pell_eq
-- The Pell identity: xn^2 - D * yn^2 = 1 for all n.

#check @Pell.exists_pell_solution
-- Existence of a positive (y >= 1) Pell solution for non-square D > 0.

#check @Pell.is_fundamental
-- The fundamental Pell solution is the smallest positive solution.

#check @Zsqrtd.norm
-- The norm map N(a + b * sqrt d) = a^2 - d * b^2 on Z[sqrt d].

#check @Zsqrtd.norm_mul
-- Norm multiplicativity N(alpha * beta) = N(alpha) * N(beta).

#check @ContinuedFractions.convergents
-- The convergents p_n / q_n of a real-valued continued fraction.

#check @ContinuedFractions.bestApproximation
-- The best-approximation property of convergents.

The Mathlib formalisation covers the existence of the fundamental Pell solution, the cyclic structure of the solution set, the norm-multiplicative ring $\mathbb{Z}[\sqrt{d}]$, and the basic theory of continued-fraction convergents. What Mathlib has not yet packaged as a unified pedagogical module: (i) Lagrange's periodicity theorem for the continued fraction of every quadratic irrational; (ii) the explicit algorithm reading the fundamental Pell solution off the convergent of $\sqrt{D}$ immediately before the period closes; (iii) Dirichlet's pigeonhole proof of Pell solvability bypassing continued fractions; (iv) the chakravala algorithm of Brahmagupta-Bhaskara with constructive termination; (v) the criterion that the negative Pell equation $x^2-D{y}^2=-1$ is solvable iff the period of $\sqrt{D}$'s continued fraction is odd; (vi) the Liouville approximation bound and the Thue-Siegel-Roth tower. These are the formalisation gaps documented in the unit metadata Mathlib gap analysis.

Advanced results Master

Theorem 1 (Lagrange periodicity, 1770). For every quadratic irrational $\alpha$, the continued-fraction expansion $\alpha =[a_0;a_1,a_2,\dots ]$ is eventually periodic. Moreover, $\alpha$ is purely periodic (i.e., $\alpha =[\overline{a_0;a_1,\dots ,a_{\ell }}]$) iff $\alpha$ is a reduced quadratic irrational: $\alpha >1$ and $-1<\bar{\alpha }<0$ ^{[Lagrange 1770]}. Proved in the Key Theorem above (Step 1) via finiteness of the integer parameters $(P_n,Q_n)$ in the reduced form ${\alpha }_n=(P_n+\sqrt{D})/Q_n$. The pure-periodicity characterisation is due to Galois (1828 Ann. de Gergonne 19, 294), generalising Lagrange's result.

Theorem 2 (Pell solvability, Lagrange 1770). For every non-square $D>0$, the Pell equation $x^2-D{y}^2=1$ has a positive-integer solution ^{[Lagrange 1770]}. Proved in the Key Theorem above as a corollary of Lagrange periodicity: the convergent $p_{\ell -1}/q_{\ell -1}$ of $\sqrt{D}=[a_0;\overline{a_1,\dots ,a_{\ell }}]$ satisfies $p_{\ell -1}^2-D{q}_{\ell -1}^2=(-1{)}^{\ell }$, so $(p_{\ell -1},q_{\ell -1})$ is a Pell solution when $\ell$ is even and $(p_{2\ell -1},q_{2\ell -1})$ is a Pell solution when $\ell$ is odd. This is the first complete proof in European mathematics — 620 years after Bhaskara II's chakravala (1150 CE).

Theorem 3 (cyclic structure of the Pell solution set). The positive-integer solutions of $x^2-D{y}^2=1$ are exactly $(x_n,y_n)=$ rational and irrational parts of $(x_1+y_1\sqrt{D}{)}^n$ for $n\ge 1$, where $(x_1,y_1)$ is the fundamental solution ^{[Hardy-Wright 2008]}. Proved as Exercise 5 above via the multiplication law and the ordering argument. The full unit group ${\mathcal{O}}_{\mathbb{Q}(\sqrt{D})}^{\times }$ of the ring of integers (when $\mathbb{Z}[\sqrt{D}]$ is the full ring of integers, i.e., $D\not\equiv 1(\mathrm{mod}4)$) is $\{\pm 1\}\times ⟨\epsilon ⟩$ where $\epsilon =x_1+y_1\sqrt{D}$ when the negative-Pell equation is unsolvable, and $\epsilon =$ the smaller fundamental negative-Pell solution when it is solvable.

Theorem 4 (negative Pell criterion). The negative Pell equation $x^2-D{y}^2=-1$ has an integer solution iff the period $\ell$ of the continued-fraction expansion of $\sqrt{D}$ is odd ^{[Hardy-Wright 2008]}. The direction $\Leftarrow$ follows from the convergent identity $p_{\ell -1}^2-D{q}_{\ell -1}^2=(-1{)}^{\ell }$: when $\ell$ is odd, this gives $-1$, so $(p_{\ell -1},q_{\ell -1})$ is a negative-Pell solution. The direction $\Rightarrow$ uses the complete characterisation of Pell-type solutions as convergents (best-approximation analogue of the Key Theorem) plus a parity argument on $\ell$. There are deep open questions about which $D$ have odd period: for $D=p$ prime with $p\equiv 1(\mathrm{mod}4)$, the period is always odd (Pell solvable); for $p\equiv 3(\mathrm{mod}4)$, the period is always even (not solvable); for composite $D$ the situation depends on the class group of $\mathbb{Q}(\sqrt{D})$ (Stevenhagen 1993 conjecture: density of $D$ with odd period is approximately $0.58$).

Theorem 5 (Dirichlet unit theorem for real quadratic fields). For $D>0$ non-square, the unit group of the ring of integers ${\mathcal{O}}_K$ of $K=\mathbb{Q}(\sqrt{D})$ is ${\mathcal{O}}_K^{\times }=\{\pm 1\}\times ⟨\epsilon ⟩$ where $\epsilon$ is the fundamental unit — the smallest unit $>1$ ^{[Dirichlet 1846]}. Proved by Dirichlet 1846 Bericht Preuss. Akad. via the geometry of numbers and a pigeonhole argument analogous to Exercise 7 above. The general Dirichlet unit theorem for number fields (1846) says the unit group of ${\mathcal{O}}_K$ has rank $r_1+r_2-1$, where $r_1,r_2$ are the numbers of real and complex embeddings; for real quadratic $K$ this rank is $1$ and the fundamental unit generates the free part. Pell solvability for non-square $D>0$ is the elementary face of the rank-$1$ unit theorem for real quadratic fields.

Theorem 6 (chakravala algorithm; Jayadeva c. 1000, Bhaskara II 1150). The chakravala (cyclic) algorithm computes the fundamental Pell solution of $x^2-D{y}^2=1$ for non-square $D>0$ in finitely many steps. Given a triple $(a,b,k)$ with $a^2-D{b}^2=k$ (started from $(a,b,k)=(\lfloor \sqrt{D}\rfloor ,1,\lfloor \sqrt{D}{\rfloor }^2-D)$), choose $m\in \mathbb{Z}$ minimising $|m^2-D|$ subject to $a+bm\equiv 0(\mathrm{mod}|k|)$; produce the new triple $$ \left(\frac{a m + D b}{|k|}, \frac{a + b m}{|k|}, \frac{m^2 - D}{k}\right). $$ Iteration terminates when $k=1$, yielding the fundamental Pell solution ^{[Bhaskara II 1150]}. Termination requires a careful argument; the original chakravala texts use the Brahmagupta composition principle (Exercise 4) repeatedly to descend to $|k|=1$. Modern proofs by Selenius (1975 Hist. Math. 2, 167) and Lenstra (2002 Mathematical Intelligencer 24, 22) show chakravala produces the fundamental solution in $O(\log D)$ iterations on average — faster than the naive continued-fraction algorithm in many cases, and asymptotically as fast as the fastest known. Hankel 1874 called chakravala "the finest thing achieved in the theory of numbers before Lagrange".

Theorem 7 (Liouville approximation bound, 1844). If $\alpha$ is an algebraic number of degree $n\ge 2$, there exists $c(\alpha )>0$ with $|\alpha -p/q|>c(\alpha )q^{-n}$ for every rational $p/q$ with $q\ge 1$ ^{[Liouville 1844]}. Proved as Exercise 8 above via the minimal-polynomial argument. Liouville's exponent $n$ is sharp only for $n=2$ (saturated by the convergents of every quadratic irrational, since $|\sqrt{D}-p_n/q_n|<1/q_n^2$). For $n\ge 3$ the exponent is far from sharp — improved by Thue, Siegel, Roth as below.

Theorem 8 (Thue-Siegel-Roth, 1909-1955). For every algebraic irrational $\alpha$ and every $\epsilon >0$, only finitely many rationals $p/q$ satisfy $|\alpha -p/q|<q^{-(2+\epsilon )}$ ^{[Roth 1955]}. The exponent $2$ is sharp by Dirichlet (Exercise 6), and the bound is the optimal universal exponent for algebraic irrationals. Thue 1909 ^{[Thue 1909]} proved exponent $n/2+1+\epsilon$; Siegel 1921 ^{[Siegel 1921]} improved to $2\sqrt{n}+\epsilon$; Roth 1955 ^{[Roth 1955]} reached the optimal $2+\epsilon$, earning the Fields Medal 1958. The proof is ineffective: it bounds the number of approximating rationals but does not bound their height, so explicit bounds for Diophantine equations cannot be deduced. Baker 1966-67 Mathematika 13, 14 introduced linear forms in logarithms to give effective bounds at the cost of weaker exponents.

Synthesis. The Pell equation is the elementary face of the unit group of $\mathbb{Q}(\sqrt{D})$, the simplest interesting number field beyond $\mathbb{Q}$ itself. The fundamental Pell (or negative-Pell) solution is the fundamental unit, and the continued-fraction algorithm for $\sqrt{D}$ is the constructive procedure for computing it. The same circle of ideas — continued fractions, periodicity, best approximation, Dirichlet pigeonhole — generalises in three directions:

(i) Algebraic direction (Dirichlet 1846, Minkowski 1896, Hasse-Minkowski 1923): the Dirichlet unit theorem for general number fields gives the rank of the unit group as $r_1+r_2-1$, with the fundamental units generating the free part. The Minkowski geometry-of-numbers approach (1896 Geometrie der Zahlen) reproves Pell solvability via the lattice $\mathbb{Z}[\sqrt{D}]\hookrightarrow {\mathbb{R}}^2$ and Minkowski's convex-body theorem, generalising to lattices of arbitrary rank. The Hasse-Minkowski theorem (1923-24) classifies indefinite quadratic forms over $\mathbb{Q}$ via local-global principle, with the Pell equation as the rank-$2$ indefinite case.

(ii) Analytic direction (Liouville 1844, Thue 1909, Siegel 1921, Roth 1955): the Liouville bound and its improvements bound the rate at which algebraic numbers can be rationally approximated. The Pell convergents saturate the Liouville bound for quadratic $\alpha$, but for higher-degree algebraic numbers the Roth theorem $|\alpha -p/q|>q^{-(2+\epsilon )}$ (sharp) shows algebraic numbers are essentially as hard to approximate as random irrationals. Schmidt's subspace theorem (1972 Acta Math. 125, 189) generalises Roth to simultaneous Diophantine approximation, with deep applications to integral points on subvarieties of tori.

(iii) Geometric direction (Thue 1909, Siegel 1929, Mordell 1922, Faltings 1983): finiteness of integer solutions of Diophantine equations of degree $\ge 3$. Thue's 1909 theorem says $f(x,y)=c$ has finitely many integer solutions for $f$ irreducible binary of degree $\ge 3$. Mordell 1922 conjectured (and Faltings 1983 proved, Fields Medal 1986) that every curve of genus $\ge 2$ over a number field has finitely many rational points. The Pell equation is precisely the boundary case — genus-$0$ curve with infinitely many integer points (in fact a $\mathbb{Z}$-torsor for the unit group) — and the contrast with the higher-genus finiteness is the elementary entry point to arithmetic geometry.

The historical arc from Brahmagupta 628 CE to Roth 1955 is a $1300$-year story of one elementary equation generating ever-richer mathematics. Brahmagupta's composition principle (samasa-bhavana) is the embryonic form of norm multiplicativity in number fields. Bhaskara II's chakravala (1150 CE) is the embryonic form of Gauss's reduction theory of quadratic forms. Lagrange's continued-fraction proof (1770) is the embryonic form of the Dirichlet unit theorem. Liouville's bound (1844) is the embryonic form of Diophantine approximation theory. Roth's theorem (1955) is the optimal exponent — but the underlying object, $x^2-D{y}^2=1$, is the same one Brahmagupta solved in 628 CE.

The applied legacy is more modest than for quadratic reciprocity, but real. Pell-equation solutions provide best rational approximations to $\sqrt{D}$, used in computer algebra systems (Mathematica, SageMath, GAP) for symbolic manipulation of quadratic irrationals. The continued-fraction algorithm is the foundation for lattice-reduction algorithms (LLL 1982 generalises the Euclidean algorithm and continued fractions to higher-dimensional lattices), which underlie cryptanalysis of low-exponent RSA (Coppersmith 1996), the NTRU cryptosystem (1996), and the modern post-quantum cryptography candidates LWE and SIS. The Pell equation itself surfaces in continued-fraction factorisation (CFRAC, Brillhart-Morrison 1975), the precursor algorithm to the quadratic sieve.

Full proof set Master

Proposition 1 (Lagrange periodicity). Every quadratic irrational has eventually-periodic continued fraction.

Proof. See Step 1 of the Key Theorem above. The recursion ${\alpha }_n=(P_n+\sqrt{D})/Q_n$ has integer parameters $P_n,Q_n$ bounded by a constant depending on $D$, so the sequence of $(P_n,Q_n)$ pairs takes only finitely many values, forcing the ${\alpha }_n$ (hence the partial quotients $a_n$) to be eventually periodic. $\square$

Proposition 2 (Pell solvability via convergents). For non-square $D>0$, the convergent $(p_{\ell -1},q_{\ell -1})$ of $\sqrt{D}$ satisfies $p_{\ell -1}^2-D{q}_{\ell -1}^2=(-1{)}^{\ell }$.

Proof. See Step 2 of the Key Theorem. The identity $p_n^2-D{q}_n^2=(-1{)}^{n+1}{Q}_{n+1}$ at $n=\ell -1$ uses $Q_{\ell }=Q_0=1$ (from the period closing at index $\ell$). $\square$

Proposition 3 (multiplication law for Pell solutions). If $(x_1,y_1)$ and $(x_2,y_2)$ are Pell solutions, so is $(x_1{x}_2+D{y}_1{y}_2,x_1{y}_2+x_2{y}_1)$.

Proof. See Exercise 4. Norm multiplicativity in $\mathbb{Z}[\sqrt{D}]$: $N(\alpha \beta )=N(\alpha )N(\beta )$ with $\alpha =x_1+y_1\sqrt{D}$, $\beta =x_2+y_2\sqrt{D}$. $\square$

Proposition 4 (cyclic structure of Pell solutions). The positive Pell solutions form an infinite cyclic semigroup generated by the fundamental solution.

Proof. See Exercise 5. By Lagrange, every Pell solution is a convergent; by the ordering argument plus the multiplication law, every positive solution is ${\epsilon }_1^n$ for $n\ge 1$. $\square$

Proposition 5 (Dirichlet pigeonhole approximation bound). For every irrational $\alpha$, there exist infinitely many rationals $p/q$ with $|\alpha -p/q|<1/q^2$.

Proof. See Exercise 6. Pigeonhole on the $N+1$ fractional parts $\{q\alpha \}$ for $q=0,1,\dots ,N$ in $N$ subintervals of $[0,1)$. $\square$

Proposition 6 (Dirichlet pigeonhole proof of Pell solvability). For non-square $D>0$, $x^2-D{y}^2=1$ has a positive-integer solution.

Proof. See Exercise 7. By Proposition 5, there are infinitely many $(p,q)$ with $|p-q\sqrt{D}|<1/q$. The integer values $p^2-D{q}^2$ are bounded, so some non-zero $N$ is attained infinitely often. Pigeonhole on residues modulo $|N|$ yields two distinct pairs $(p_1,q_1)\ne (p_2,q_2)$ with the same residues, and the quotient $(p_1+q_1\sqrt{D})/(p_2+q_2\sqrt{D})=X+Y\sqrt{D}$ has integer coordinates and norm $1$, hence is a Pell solution. $\square$

Proposition 7 (negative Pell criterion). The equation $x^2-D{y}^2=-1$ has an integer solution iff the period of the continued fraction of $\sqrt{D}$ is odd.

Proof sketch. Direction $\Leftarrow$ from Proposition 2 with odd $\ell$ giving $(-1{)}^{\ell }=-1$. Direction $\Rightarrow$: if $(x,y)$ is a negative-Pell solution, then by the convergent characterisation (analogous to Step 3 of the Key Theorem applied with the bound $|x-y\sqrt{D}|<1/(2y)$), $(x,y)$ is a convergent $(p_n,q_n)$. The convergent identity $p_n^2-D{q}_n^2=(-1{)}^{n+1}{Q}_{n+1}$ with value $-1$ forces $Q_{n+1}=1$ (so $n+1$ is a multiple of $\ell$) and $n$ even (so $(-1{)}^{n+1}=-1$). Hence $n+1=m\ell$ for some $m$ with $m\ell -1$ even, equivalently $m\ell$ odd. For $m\ge 1$ integer this forces both $m$ and $\ell$ odd, so $\ell$ is odd. $\square$

Proposition 8 (Liouville approximation bound). Algebraic $\alpha$ of degree $n\ge 2$ admits $|\alpha -p/q|>c(\alpha )q^{-n}$ for all $p/q$.

Proof. See Exercise 8. Minimal-polynomial argument: $|q^{n}f(p/q)|\ge 1$ on one side; $|f(p/q)|\le M|p/q-\alpha |$ on the other side by the mean-value theorem. $\square$

Proposition 9 (Brahmagupta composition for $x^2-D{y}^2=N$). If $(a,b)$ solves $x^2-D{y}^2=N_1$ and $(c,d)$ solves $x^2-D{y}^2=N_2$, then $(ac+Dbd,ad+bc)$ solves $x^2-D{y}^2=N_1{N}_2$.

Proof. Norm multiplicativity in $\mathbb{Z}[\sqrt{D}]$: $N((a+b\sqrt{D})(c+d\sqrt{D}))=N(a+b\sqrt{D})N(c+d\sqrt{D})=N_1{N}_2$, and the product expands to $(ac+Dbd)+(ad+bc)\sqrt{D}$. This is Brahmagupta's samasa-bhavana (628 CE), the foundational composition principle. $\square$

Connections Master

• Divisibility, gcd, and the Euclidean algorithm 21.01.01. Shipped. The Euclidean algorithm for $\gcd (a,b)$ is the finite-arithmetic analogue of the continued-fraction algorithm for $\sqrt{D}$: both are based on the recursion "subtract the largest possible integer multiple, then invert". The convergents $p_n/q_n$ of any irrational $\alpha$ satisfy the same cross-ratio identity $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n-1}$ that drives the Euclidean algorithm to a $\gcd$. The connection is the Stern-Brocot tree of best rational approximations.

• Primes and the fundamental theorem of arithmetic 21.01.02. Shipped. Pell solvability for prime $D=p$ depends on the residue $p(\mathrm{mod}4)$: for $p\equiv 1(\mathrm{mod}4)$, the negative-Pell equation $x^2-p{y}^2=-1$ is always solvable (period odd, by a deep theorem); for $p\equiv 3(\mathrm{mod}4)$, the negative-Pell equation is never solvable (period even). The bridge to 21.01.02 is the way prime-residue conditions modulo small integers control deep structural questions about $\mathbb{Q}(\sqrt{p})$.

• Real numbers and completeness 02.04.01. Pending. The continued-fraction algorithm requires the floor function $\lfloor \alpha \rfloor$, which presupposes the order completeness of $\mathbb{R}$. Lagrange's periodicity theorem uses the Bolzano-Weierstrass theorem (every bounded sequence has a convergent subsequence) implicitly via the finiteness-of-$(P_n,Q_n)$ argument. The Liouville approximation bound is a $C^1$-continuity statement about the minimal polynomial; the Thue-Siegel-Roth tower uses sophisticated complex-analytic arguments (transcendence-degree arithmetic, the Schmidt subspace theorem).

• Algebraic number fields and rings of integers 21.02.01. Pending. Pell solvability is the elementary face of the structure theory of the unit group of $\mathbb{Q}(\sqrt{D})$ for $D>0$ non-square. The number field $K=\mathbb{Q}(\sqrt{D})$ has ring of integers ${\mathcal{O}}_K=\mathbb{Z}[\sqrt{D}]$ (if $D\not\equiv 1(\mathrm{mod}4)$) or $\mathbb{Z}[(1+\sqrt{D})/2]$ (if $D\equiv 1(\mathrm{mod}4)$), and the unit group ${\mathcal{O}}_K^{\times }=\{\pm 1\}\times ⟨\epsilon ⟩$ is the elementary instance of the Dirichlet unit theorem for general number fields.

• Class groups and the ideal class group of $\mathbb{Z}[\sqrt{D}]$ 21.02.05. Pending. The Pell equation interacts with the class group $\mathrm{Cl}({\mathcal{O}}_K)$ of the real quadratic field $K=\mathbb{Q}(\sqrt{D})$: when $\mathrm{Cl}({\mathcal{O}}_K)=1$ (principal-ideal domain), the generalised Pell equation $x^2-D{y}^2=N$ for $N$ a prime ideal generator behaves uniformly; when $\mathrm{Cl}({\mathcal{O}}_K)>1$, the equation has multiple orbits of solutions corresponding to the ideal classes. The famous Cohen-Lenstra heuristics (1984) predict the distribution of class numbers and the density of $D$ with $|\mathrm{Cl}({\mathcal{O}}_K)|=1$.

• Dirichlet unit theorem 21.02.06. Pending. The Dirichlet unit theorem (Dirichlet 1846) gives the rank of the unit group of any number field as $r_1+r_2-1$, with the free part generated by the fundamental units. For real quadratic $K=\mathbb{Q}(\sqrt{D})$ the rank is $1$ and the fundamental unit is the fundamental Pell (or negative-Pell) solution. Pell is the simplest, most elementary case of the Dirichlet unit theorem.

• Diophantine approximation 21.01.10 pending. Lateral. The continued-fraction theory of Pell extends to the general theory of Diophantine approximation: how well can a real number be approximated by rationals? The Dirichlet bound (Exercise 6 above) is the universal lower bound $|\alpha -p/q|<1/q^2$ for infinitely many $p/q$; the Liouville bound (Exercise 8) is the upper bound for algebraic numbers; the Thue-Siegel-Roth tower gives the sharp $|\alpha -p/q|>q^{-(2+\epsilon )}$ for algebraic irrationals. The Khinchin metric theorem (1928): for almost every real $\alpha$ (Lebesgue), the convergent denominators satisfy $q_n^{1/n}\to K_0\approx 2.685$ — Khinchin's constant.

• Analysis prerequisites [02 analysis]. Lateral. Continued fractions converge to their limit at the rate $|\alpha -p_n/q_n|<1/q_n^2$ — a quantitative version of the Cauchy criterion. The Lagrange periodicity proof uses the Bolzano-Weierstrass theorem (compactness of bounded sequences). The Liouville approximation bound uses the mean-value theorem from calculus. The Roth theorem (1955) uses the Thue-Siegel principle — a deep argument about heights of points on algebraic varieties, with the auxiliary polynomial constructed via Siegel's lemma (Cassels 1957 Diophantine Approximation Ch. III).

• Continued-fraction expansions of fundamental constants. Lateral. The continued fraction of $e=[2;1,2,1,1,4,1,1,6,1,1,8,\dots ]$ (Euler 1737) has a clean pattern but is non-periodic, so $e$ is non-quadratic by Lagrange. The continued fraction of $\pi =[3;7,15,1,292,1,1,1,2,1,3,1,\dots ]$ (Brouncker 1655) has no known pattern, and the convergent $355/113$ (the Tsu Ch'ung-Chih approximation, c. 480 CE) agrees with $\pi$ to seven decimal places — explained by the large partial quotient $a_4=292$. Hermite 1873 proved $e$ transcendental; Lindemann 1882 proved $\pi$ transcendental; both proofs descend from the Liouville-style arguments developed for Pell.

Historical & philosophical context Master

The Pell equation has the longest continuously-recorded history of any single equation in mathematics: $1300$ years from Brahmagupta (628 CE) to Roth (1955).

Brahmagupta (628 CE) Brāhmasphuṭasiddhānta ^{[Brahmagupta 628]}, ch. 18 §§64-75 introduced the samasa-bhavana (composition principle): from two solutions of $x^2-D{y}^2=N_1$ and $x^2-D{y}^2=N_2$, produce one of $x^2-D{y}^2=N_1{N}_2$. This is the embryonic form of norm multiplicativity in $\mathbb{Z}[\sqrt{D}]$ and the elementary face of all subsequent reciprocity-style composition principles. Brahmagupta showed that if $x^2-D{y}^2=k$ is solved for $k\in \{-1,\pm 2,\pm 4\}$, then composition yields a Pell solution, providing the first general method for Pell-type equations in any culture. Brahmagupta's worked examples in $D=92,83$ and similar moderate cases are correct to the digit.

Jayadeva (c. 1000 CE, lost work) and Bhaskara II (1150 CE) Bījagaṇita ^{[Bhaskara II 1150]}, §§71-90 developed the chakravala (cyclic) algorithm completing Brahmagupta's composition to a guaranteed-terminating procedure. The chakravala algorithm produced Bhaskara's celebrated solution of $x^2-61y^2=1$ as $(1766319049,226153980)$ — a $10$-digit answer found without paper or modern arithmetic notation, in the 12th century. The same answer was re-discovered in 1657 by Brouncker in response to Fermat's challenge. Hankel 1874 Zur Geschichte der Mathematik in Altertum und Mittelalter called chakravala "the finest thing achieved in the theory of numbers before Lagrange" (Lagrange's own proof of Pell solvability did not appear until 620 years later).

Fermat (1657) issued a public challenge in January 1657 to all European mathematicians: solve $x^2-D{y}^2=1$ for $D=61,109,149,433$ and other carefully-chosen large $D$ values where the fundamental solution has many digits. The English mathematicians Brouncker and Wallis responded with a continued-fraction-style algorithm, with Brouncker computing the $D=61$ solution in a few weeks. Wallis published the correspondence in Commercium Epistolicum 1658 ^{[Brouncker-Wallis 1657]}. Fermat acknowledged the solutions but did not publicly prove solvability for all non-square $D>0$; his infinite descent proof, alluded to in a 1657 letter to Frenicle, is lost.

Euler (1730s-1765) ^{[Euler 1765]} developed the continued-fraction algorithm for $\sqrt{D}$, expanding $\sqrt{D}=[a_0;\overline{a_1,a_2,\dots ,a_{\ell }}]$ and reading the fundamental Pell solution off the convergent immediately before the period closes. Euler also introduced the misattribution that has stuck: in his 1765 Novi Commentarii Academiae Scientiarum Petropolitanae paper he credited the equation to John Pell based on a misreading of Wallis's Algebra (1685, ch. 98) — Pell merely edited Brouncker's solution for printing. The name "Pell equation" has stuck despite Pell himself contributing nothing; the equation was solved by Brahmagupta in 628 CE, Bhaskara II in 1150 CE, Fermat in 1657, and Brouncker in 1658, all without Pell's involvement.

Lagrange (1770) Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin ^{[Lagrange 1770]} gave the first complete proof in European mathematics of Pell solvability for every non-square $D>0$. Lagrange's two theorems: (i) periodicity of the continued-fraction expansion of every quadratic irrational; (ii) the convergent immediately before the period closes gives the fundamental Pell (or negative-Pell) solution. This was 620 years after Bhaskara II's chakravala — a delay reflecting the European mathematical isolation from Indian sources.

Galois (1828) Annales de Gergonne 19, 294 generalised Lagrange's result with the purely-periodic characterisation: the continued fraction $[a_0;a_1,a_2,\dots ]$ is purely periodic iff $\alpha$ is a reduced quadratic irrational ($\alpha >1$, $-1<\bar{\alpha }<0$). Galois's result is the cleanest statement of the periodicity theorem and the basis for the modern proof in textbooks.

Dirichlet (1837 Werke I + Dirichlet-Dedekind 1894 Vorlesungen) ^{[Dirichlet 1837]} gave the pigeonhole proof of Pell solvability bypassing continued fractions: by the Dirichlet approximation theorem, there are infinitely many $(p,q)$ with $|p-q\sqrt{D}|<1/q$; the values $p^2-D{q}^2$ are bounded, so some non-zero $N$ is attained infinitely often; pigeonhole on residues modulo $|N|$ produces two pairs whose quotient is a Pell solution. The same machinery gives the Dirichlet unit theorem (1846): the unit group of any number field has rank $r_1+r_2-1$, with Pell as the rank-$1$ real-quadratic case.

Liouville (1844) ^{[Liouville 1844]} proved the Liouville approximation bound: algebraic $\alpha$ of degree $n$ cannot be approximated by rationals to order strictly better than $n$. Liouville used this to construct the first explicit transcendental numbers ${\sum }_{k}10^{-k!}$ (with truncations giving approximations of arbitrarily high order). The Pell convergents saturate the Liouville bound for $n=2$ — quadratic irrationals are exactly the irrationals approximable to order $2$ but not to order $>2$.

Thue (1909) ^{[Thue 1909]} Crelle 135 improved the Liouville exponent from $n$ to $n/2+1+\epsilon$. Thue's method introduced the auxiliary polynomial $P(x,y)$ used in all later refinements. Siegel (1921) ^{[Siegel 1921]} Math. Z. 10 improved to $2\sqrt{n}+\epsilon$, attaining the optimum of Siegel's variational argument. Roth (1955) ^{[Roth 1955]} Mathematika 2 reached the optimal $2+\epsilon$, sharp by the Dirichlet bound. Roth received the Fields Medal 1958 for this result.

The Roth theorem is ineffective: it bounds the number of approximating rationals but not their height. Effective bounds had to wait for Baker (1966-67) ^{[Roth 1955]} Mathematika 13-14 and his theory of linear forms in logarithms — for which Baker received the Fields Medal 1970. The Liouville-Thue-Siegel-Roth-Baker tower is the canonical example of a research programme where each generation refined the previous bound, with the final endpoint (Roth's exponent $2$) being optimal but ineffective, motivating an entirely new theory (Baker) to recover effectivity.

The philosophical lesson of the Pell story: a single elementary equation, posed by Brahmagupta in the 7th century, generated the entire theory of units in number fields, Diophantine approximation, transcendence theory, and the modern framework of integral points on algebraic varieties. The Pell equation is the simplest interesting Diophantine equation with infinitely many integer solutions, and understanding it completely — through Lagrange's continued fractions and Dirichlet's pigeonhole — required ideas that turned out to be the embryonic forms of $20$th-century algebraic and arithmetic geometry.

Bibliography Master

@book{Brahmagupta628,
  author    = {Brahmagupta},
  title     = {Br{\=a}hmasphu{\d{t}}asiddh{\=a}nta},
  year      = {628},
  note      = {Sanskrit, c. 628 CE. Chapter 18 (kuṭṭakādhyāya) §§64-75 develop the samasa-bhavana (composition principle) for $x^2 - D y^2 = N$: from solutions of $x^2 - D y^2 = N_1$ and $x^2 - D y^2 = N_2$, produce a solution of $x^2 - D y^2 = N_1 N_2$. The first general method for Pell-type equations in any culture. English: Colebrooke, Algebra with Arithmetic and Mensuration from the Sanscrit of Brahmegupta and Bháscara, London 1817 (reprinted Wiesbaden 1973).}
}

@book{BhaskaraII1150,
  author    = {{Bh{\=a}skara II}},
  title     = {B{\=\i}jaga{\d n}ita},
  year      = {1150},
  note      = {Sanskrit, c. 1150 CE. §§71-90 develop the chakravala (cyclic) algorithm completing Brahmagupta's composition principle to a guaranteed-terminating procedure for $x^2 - D y^2 = 1$. Famous worked example: fundamental solution of $x^2 - 61 y^2 = 1$ as $(1766319049, 226153980)$, found without paper or modern arithmetic notation. Hankel 1874 called chakravala 'the finest thing achieved in the theory of numbers before Lagrange'. English: Plofker, Mathematics in India, Princeton 2009, §5.4.2.}
}

@book{BrounckerWallis1658,
  author    = {Brouncker, William and Wallis, John},
  title     = {Commercium Epistolicum},
  publisher = {Oxford},
  year      = {1658},
  note      = {Fermat's January 1657 challenge to the English mathematicians: solve $x^2 - D y^2 = 1$ for $D = 61, 109, 149, \ldots$. Brouncker's continued-fraction-style algorithm produced the $D = 61$ solution $(1766319049, 226153980)$ in a few weeks; Wallis wrote the exposition. The first complete European treatment of the Pell equation, $500$ years after Bhaskara II's chakravala.}
}

@article{Euler1765,
  author  = {Euler, Leonhard},
  title   = {De usu novi algorithmi in problemate Pelliano solvendo},
  journal = {Novi Commentarii Academiae Scientiarum Petropolitanae},
  volume  = {11},
  pages   = {28--66},
  year    = {1765},
  note    = {Reprinted Opera Omnia I.3, 73-111. Euler's continued-fraction algorithm for $\sqrt D$, with the misattribution to John Pell based on a misreading of Wallis's Algebra (1685). The name 'Pell equation' has stuck despite Pell himself contributing nothing.}
}

@article{Lagrange1770,
  author  = {Lagrange, Joseph Louis},
  title   = {Solution d'un probl{\`e}me d'arithm{\'e}tique},
  journal = {M{\'e}moires de l'Acad{\'e}mie Royale des Sciences et Belles-Lettres de Berlin},
  volume  = {24},
  pages   = {165--310},
  year    = {1770},
  note    = {Originally presented 1768. Reprinted Oeuvres I, 671-731. First complete proof in European mathematics of Pell solvability for every non-square $D > 0$. Two theorems: (i) periodicity of the continued fraction of every quadratic irrational; (ii) the convergent before the period closes is the fundamental Pell solution. 620 years after Bhaskara II's chakravala.}
}

@book{DirichletDedekind1894Pell,
  author    = {Dirichlet, Peter Gustav Lejeune and Dedekind, Richard},
  title     = {Vorlesungen {\"u}ber Zahlentheorie},
  edition   = {4},
  publisher = {Vieweg},
  address   = {Braunschweig},
  year      = {1894},
  note      = {§§80-100 give Dirichlet's pigeonhole proof of Pell solvability bypassing continued fractions. The proof generalises to the Dirichlet unit theorem (1846) giving the rank of the unit group of any number field as $r_1 + r_2 - 1$, with Pell as the rank-$1$ real-quadratic case.}
}

@article{Liouville1844,
  author  = {Liouville, Joseph},
  title   = {Sur des classes tr{\`e}s {\'e}tendues de quantit{\'e}s dont la valeur n'est ni alg{\'e}brique, ni m{\^e}me r{\'e}ductible {\`a} des irrationelles alg{\'e}briques},
  journal = {Comptes Rendus de l'Acad{\'e}mie des Sciences de Paris},
  volume  = {18},
  pages   = {883--885 and 910--911},
  year    = {1844},
  note    = {Liouville's approximation bound: algebraic $\alpha$ of degree $n \geq 2$ cannot be approximated by rationals to order strictly better than $n$. Used to construct the first explicit transcendental numbers $\sum_k 10^{-k!}$. Founding result of transcendence theory.}
}

@article{Thue1909,
  author  = {Thue, Axel},
  title   = {{\"U}ber Ann{\"a}herungswerte algebraischer Zahlen},
  journal = {Journal f{\"u}r die reine und angewandte Mathematik},
  volume  = {135},
  pages   = {284--305},
  year    = {1909},
  note    = {Thue's improvement of Liouville: algebraic $\alpha$ of degree $n \geq 3$ is approximable to order at most $n/2 + 1 + \varepsilon$. Consequence: Thue equations $f(x, y) = c$ for $f$ irreducible binary of degree $\geq 3$ have only finitely many integer solutions.}
}

@article{Siegel1921,
  author  = {Siegel, Carl Ludwig},
  title   = {Approximation algebraischer Zahlen},
  journal = {Mathematische Zeitschrift},
  volume  = {10},
  pages   = {173--213},
  year    = {1921},
  note    = {Siegel's improvement of Thue: the approximation exponent for algebraic $\alpha$ of degree $n$ is at most $2 \sqrt n + \varepsilon$. The proximate predecessor of Roth's theorem.}
}

@article{Roth1955,
  author  = {Roth, Klaus Friedrich},
  title   = {Rational approximations to algebraic numbers},
  journal = {Mathematika},
  volume  = {2},
  pages   = {1--20},
  year    = {1955},
  note    = {Roth's theorem: for every algebraic irrational $\alpha$ and every $\varepsilon > 0$, only finitely many rationals $p/q$ satisfy $|\alpha - p/q| < q^{-(2 + \varepsilon)}$. The exponent $2$ is sharp by the Dirichlet bound. Roth received the Fields Medal 1958. Ineffective: bounds the number but not the height of approximating rationals.}
}

@book{HardyWright2008Pell,
  author    = {Hardy, G. H. and Wright, E. M.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {6},
  publisher = {Oxford University Press},
  year      = {2008},
  note      = {Revised by D. R. Heath-Brown and J. H. Silverman. Chapters X-XI develop the theory of continued fractions for real numbers and quadratic irrationals: the Euclidean expansion of rationals, the convergents $p_n/q_n$ with best-approximation property, Lagrange's periodicity theorem, the Pell equation and its complete solution via the convergents of $\sqrt D$, the generalised Pell equation, the negative Pell criterion.}
}

@book{NivenZuckermanMontgomery1991Pell,
  author    = {Niven, Ivan and Zuckerman, Herbert S. and Montgomery, Hugh L.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {5},
  publisher = {Wiley},
  year      = {1991},
  note      = {§§7.7-7.8 develop the Pell equation $x^2 - D y^2 = N$ for general $N$, the negative Pell criterion (solvable iff period of $\sqrt D$ is odd), the structure of solutions of the generalised Pell equation as a finite union of orbits under the Pell unit group.}
}

@book{Khinchin1964,
  author    = {Khinchin, Aleksandr Yakovlevich},
  title     = {Continued Fractions},
  publisher = {University of Chicago Press},
  year      = {1964},
  note      = {Translation by Scripta Technica from Tsepnye drobi (Moscow 1935; 3rd Russian edition 1961). Dover reprint 1997. §§I.1-9 basic algorithm and convergents; §§II.10-13 metric theory including Khinchin's constant $K_0 \approx 2.685$ and Markov spectrum; §§III.14-17 best rational approximations and quadratic-irrational characterisation. The canonical monograph on continued fractions.}
}

@book{Lang1962,
  author    = {Lang, Serge},
  title     = {Diophantine Geometry},
  publisher = {Interscience},
  year      = {1962},
  note      = {Chapter VII develops Pell equations, units in number fields, and the Liouville-Thue-Siegel-Roth tower from the algebraic-geometric viewpoint. The bridge from elementary continued-fraction theory to integral points on curves and the Mordell conjecture (Faltings 1983).}
}

@book{Cassels1957,
  author    = {Cassels, J. W. S.},
  title     = {An Introduction to Diophantine Approximation},
  series    = {Cambridge Tracts in Mathematics and Mathematical Physics},
  volume    = {45},
  publisher = {Cambridge University Press},
  year      = {1957},
  note      = {Reprinted 1965, Hafner. Chapters II-III develop approximation to algebraic numbers from Liouville through Thue, Siegel, and Roth, with explicit construction of the auxiliary polynomial used in the Thue-Siegel-Roth proofs and careful treatment of the ineffectivity issue.}
}

@book{Burton2010Pell,
  author    = {Burton, David M.},
  title     = {Elementary Number Theory},
  edition   = {7},
  publisher = {McGraw-Hill},
  year      = {2010},
  note      = {Chapter 14 §14.4 develops the Pell equation at the undergraduate Beginner-tier level: hand-computation of fundamental solutions for small $D$, the multiplication law for generating all solutions, statement of Lagrange's continued-fraction algorithm.}
}

@book{Stillwell2010,
  author    = {Stillwell, John},
  title     = {Mathematics and Its History},
  edition   = {3},
  publisher = {Springer Undergraduate Texts in Mathematics},
  year      = {2010},
  note      = {§5.4 develops Brahmagupta's Brāhmasphuṭasiddhānta (628 CE) and Bhaskara II's Bījagaṇita (1150 CE) on Pell with cattle-style worked examples and the historical chain Brahmagupta-Bhaskara-Brouncker-Lagrange-Dirichlet.}
}