Pell's Equation

Pell's Equation

Pell's equation is the Diophantine equation

where $n$ is a given positive integer that is not a perfect square, and we seek integer solutions $x, y \in \mathbb{Z}$.

Why the Square-Free Condition Matters

If $n$ were a perfect square, say $n = k^2$, the equation becomes

which only has the trivial solutions $x = \pm 1, y = 0$. The interesting, infinite structure only appears when $n$ is square-free (or at least not a perfect square), because then $\sqrt{n}$ is irrational and $x/y$ can approximate it arbitrarily well.

The Trivial Solution

Every Pell's equation has the trivial solution

The goal is to find the fundamental solution $(x_1, y_1)$ — the smallest solution with $x, y > 0$ — from which every other solution can be generated.

Connection to Continued Fractions

The fundamental solution of $x^2 - n y^2 = 1$ comes from the continued fraction expansion of $\sqrt{n}$, which is always periodic:

Let $p_i / q_i$ be the convergents of this continued fraction. If the period length $k$ is even, the fundamental solution is given by the convergent just before the period repeats:

If $k$ is odd, that convergent instead solves $x^2 - n y^2 = -1$, and the fundamental solution to the $+1$ equation comes from the convergent at $2k - 1$.

from fractions import Fraction
import math

def continued_fraction_sqrt(n):
    """Yield the periodic continued fraction coefficients of sqrt(n)."""
    a0 = int(math.isqrt(n))
    if a0 * a0 == n:
        raise ValueError("n must not be a perfect square")
    # standard algorithm: track (m, d, a) triples until a repeat signals the period
    m, d, a = 0, 1, a0
    coeffs = [a0]
    while True:
        m = d * a - m          # next numerator term
        d = (n - m * m) // d   # next denominator term
        a = (a0 + m) // d      # next continued fraction coefficient
        coeffs.append(a)
        if a == 2 * a0:        # the period always ends right before 2*a0 repeats
            break
    return coeffs  # [a0, a1, a2, ..., a_k] where a_k restarts the period

def fundamental_pell_solution(n):
    """Find the smallest positive (x, y) solving x^2 - n*y^2 = 1."""
    coeffs = continued_fraction_sqrt(n)
    a0 = coeffs[0]
    # build convergents p_i/q_i via the standard recurrence, stopping as soon
    # as one satisfies the Pell equation
    h_prev2, h_prev1 = 1, a0       # h_{-1}, h_0
    k_prev2, k_prev1 = 0, 1        # k_{-1}, k_0
    for a in coeffs[1:]:
        h = a * h_prev1 + h_prev2
        k = a * k_prev1 + k_prev2
        if h * h - n * k * k == 1:
            return h, k
        h_prev2, h_prev1 = h_prev1, h
        k_prev2, k_prev1 = k_prev1, k
    raise RuntimeError("no solution found within one period (shouldn't happen)")

print(fundamental_pell_solution(2))  # (3, 2):   3^2 - 2*2^2 = 1
print(fundamental_pell_solution(7))  # (8, 3):   8^2 - 7*3^2 = 1

Generating All Solutions

Once the fundamental solution $(x_1, y_1)$ is known, every positive solution $(x_k, y_k)$ is generated by

Expanding and matching rational and irrational parts gives a clean recurrence:

def next_pell_solution(x1, y1, xk, yk, n):
    """Advance from solution k to k+1 using the fundamental solution (x1, y1)."""
    # derived from (x1 + y1*sqrt(n)) * (xk + yk*sqrt(n)) = x_{k+1} + y_{k+1}*sqrt(n)
    x_next = x1 * xk + n * y1 * yk
    y_next = x1 * yk + y1 * xk
    return x_next, y_next

n = 2
x, y = fundamental_pell_solution(n)  # (3, 2)
solutions = [(x, y)]
for _ in range(4):
    x, y = next_pell_solution(3, 2, x, y, n)
    solutions.append((x, y))

print(solutions)  # [(3,2), (17,12), (99,70), (577,408), (3363,2378)]

Worked Example

Solve $x^2 - 2y^2 = 1$.

• $\sqrt{2} = [1; \overline{2}]$, a period of length $k = 1$ (odd).
• The convergent from the odd-length period, $p_0/q_0 = 1/1$, solves $x^2 - 2y^2 = -1$ instead.
• Continuing one more period gives the convergent $3/2$: $$3^2 - 2 \cdot 2^2 = 9 - 8 = 1$$
• So the fundamental solution is $(x_1, y_1) = (3, 2)$.
• Subsequent solutions follow the recurrence $x_{k+1} = 3x_k + 4y_k,\ y_{k+1} = 3y_k + 2x_k$, giving $(17, 12), (99, 70), \ldots$

Why It Matters

• Continued fractions: Pell's equation is one of the classic applications of periodic continued fraction expansions of quadratic irrationals.
• Units in quadratic fields: solutions $(x, y)$ correspond to units $x + y\sqrt{n}$ in the ring $\mathbb{Z}[\sqrt{n}]$, a key object in algebraic number theory.
• Rational approximation: the ratios $x_k / y_k$ generated by Pell's equation are extremely good rational approximations to $\sqrt{n}$.
• Historical puzzles: Archimedes' cattle problem and many classical number-theory challenges reduce to solving a Pell's equation.

Reference

• https://en.wikipedia.org/wiki/Pell%27s_equation
• https://en.wikipedia.org/wiki/Continued_fraction