Mathematics
The Pell Equation and Its Solution via Continued Fractions
Quick fact
For any non-square positive integer D, the Pell equation x² – Dy² = 1 always has infinitely many integer solutions, and they are generated from the continued fraction expansion of √D. The smallest non-trivial solution for D=2 is (3,2), for D=3 it's (2,1), and for D=60 it's (31,4).
Why this is interesting
You know how to solve equations like x² – 2y² = 1? It looks simple, but the solutions are surprisingly large and tricky to find. Can you guess the next one after (3, 2) and (17, 12)?
Read the full explanation
Understanding The Pell Equation and Its Solution via Continued Fractions
Imagine you're trying to find two integers x and y such that the difference between x² and D·y² is exactly 1. That's the Pell equation. For D=2, (3,2) works because 3² – 2·2² = 9 – 8 = 1. It seems like a random guess, but there's a systematic way: use the continued fraction of √D. A continued fraction is a way to represent a number as a nested fraction, like a + 1/(b + 1/(c + ...)). For √2, this expansion is [1; 2, 2, 2, ...]—the '2's repeat forever. If you cut off this expansion after a few terms, you get a rational approximation, called a convergent. For √2, the convergents are 1, 3/2, 7/5, 17/12, ... . Notice that the numerators and denominators appear in the Pell solutions: (1,0), (3,2), (7,5), (17,12). After the first, every other convergent (the ones where the period is even) gives a solution to x² – 2y² = 1. This is not a coincidence: it happens because the convergent's numerator and denominator satisfy the equation exactly when the period is even, and for all D, the fundamental solution emerges from the period of the continued fraction.
A deeper explanation
The connection goes deeper. The Pell equation can be rewritten as (x + y√D)(x – y√D) = 1. This means that x + y√D is a unit in the ring of integers of the quadratic field Q(√D). The continued fraction expansion of √D is ultimately periodic, and its period length encodes the structure of these units. Specifically, if the period length is n, then the convergent just before the period repeats gives the fundamental solution (x₁, y₁). All other solutions are powers of this fundamental unit: xk + yk√D = (x₁ + y₁√D)ᵏ. This is why there are infinitely many solutions: each power produces a new pair. The period length also tells us whether the negative Pell equation x² – Dy² = –1 has a solution: it does only if n is odd. This reveals a beautiful interplay between approximation (continued fractions) and algebraic number theory. Besides being a classic puzzle, Pell equations appear in problems of finding integer solutions to quadratic equations, in the study of algebraic number theory, and even in the design of certain public-key cryptosystems.