Pell's Equation — Mathematics Knowledge System

Overview

Pell's equation is x² − Ny² = 1, where N is a fixed nonsquare positive integer and integer solutions (x, y) are sought. Despite the name, Pell had little to do with it — Euler mistakenly attributed earlier work to John Pell, and the equation was studied far earlier, including a rich treatment by Indian mathematicians Brahmagupta (7th century) and Bhāskara II (12th century), who developed the chakravala method for solving it. Whenever N is not a perfect square, Pell's equation has infinitely many positive integer solutions, all generated from a single smallest one — the 'fundamental solution' — by a simple recurrence; if N is a perfect square, only the trivial solution (x, y) = (1, 0) exists, since the equation would factor over the integers. The fundamental solution is found directly from the continued fraction expansion of √N: it comes from the first convergent that satisfies the equation, and the theory guarantees this always happens within the periodic part of the expansion. Pell's equation shows up wherever quadratic irrationals do — rational approximation of √N, the study of units in real quadratic number fields, and classical geometric problems like the 'cattle problem' attributed to Archimedes.

Intuition

Think of x + y√N as a single algebraic number; the equation x² − Ny² = 1 says exactly that this number, multiplied by its 'conjugate' x − y√N, equals 1 — so x + y√N is a unit (an invertible element) in the ring ℤ[√N]. Units multiply to give units, which is why raising the smallest nontrivial unit (the fundamental solution) to higher and higher powers sweeps out every solution: (x₁ + y₁√N)^k is automatically another solution for every positive integer k, and it turns out these are all of them. Finding that smallest unit is where continued fractions come in: √N has a purely periodic continued fraction expansion (after the first term), and the convergents of that expansion hit the fundamental solution of Pell's equation right at the end of the first period.

Formal Definition

Definition

For a fixed nonsquare positive integer N, Pell's equation asks for integers x, y satisfying:

x^{2} - N y^{2} = 1

Pell's equation

(x_1, y_1) \text{ fundamental} \ \Rightarrow\ x_k + y_k \sqrt{N} = (x_1 + y_1\sqrt{N})^{k}

All solutions generated from the fundamental one

x_{k+1} = x_1 x_k + N y_1 y_k, \qquad y_{k+1} = x_1 y_k + y_1 x_k

Recurrence for successive solutions

Worked Examples

Substitute x = 3, y = 2.
$3^{2} - 2\cdot 2^{2} = 9 - 8$
Simplify.
$9 - 8 = 1$

Answer: 3² − 2·2² = 1, so (3, 2) solves x² − 2y² = 1; checking all smaller positive y (y=1 gives x²=3, not a perfect square) confirms it is the fundamental solution.

Practice Problems

Difficulty 5/10

Verify that (x, y) = (2, 1) is the fundamental solution of x² − 3y² = 1.

Difficulty 7/10

Using the fundamental solution (3, 2) of x² − 2y² = 1 and the recurrence x_{k+1} = 3x_k + 4y_k, y_{k+1} = 3y_k + 2x_k, find the next solution.

Difficulty 6/10

Verify that (x, y) = (9, 4) is the fundamental solution of x² − 5y² = 1.

Quiz

Summary

Pell's equation x² − Ny² = 1 (N a nonsquare positive integer) has infinitely many positive integer solutions, all generated from one fundamental solution.
Solutions correspond to units x + y√N in ℤ[√N]; raising the fundamental unit to successive powers sweeps out every solution via a linear recurrence.
The fundamental solution is found from the continued fraction expansion of √N, which is purely periodic and yields the answer at the end of its first period.

References

WebsiteWikipedia — Pell's equation