Pell's Equation and Sums of Squares

Definition. For a nonsquare positive integer $D$, Pell’s equation is

The trivial solutions $(\pm 1, 0)$ always exist; the equation is interesting because whenever one non-trivial solution $(x_1, y_1)$ exists, infinitely many do; all generated by powers of the fundamental solution in the ring $\mathbb{Z}[\sqrt{D}]$:

(the algebra works because $(x_1^2 - D y_1^2)(x_2^2 - D y_2^2) = (x_1 x_2 - D y_1 y_2)^2 - D(x_1 y_2 + x_2 y_1)^2$; Brahmagupta’s identity).

Example. $x^2 - 2y^2 = 1$: fundamental solution $(3, 2)$, and successive solutions $(17, 12), (99, 70), (577, 408), \ldots$; the $y$-values grow like $(3 + 2\sqrt 2)^k / (2\sqrt 2)$, exponentially.

Example (the cattle problem of Archimedes, simplified). $x^2 - 61 y^2 = 1$ has fundamental solution $x = 1766319049$, $y = 226153980$; a famously enormous answer discovered via continued fractions, illustrating why the equation resisted solution for centuries.

The continued fraction expansion of $\sqrt{D}$ is periodic for every nonsquare $D$:

The solutions of Pell’s equation come from the convergents $p_k/q_k$:

• If the period length $r$ is even, $(p_{r-1}, q_{r-1})$ is the fundamental solution of $x^2 - Dy^2 = 1$.
• If $r$ is odd, $(p_{2r-1}, q_{2r-1})$ solves $= 1$, and $(p_{r-1}, q_{r-1})$ solves the negative Pell equation $x^2 - D y^2 = -1$.

Worked example. $\sqrt{7} = [2; \overline{1, 1, 1, 4}]$ ($r = 4$, even). Convergents: $2/1$, $3/1$, $5/2$, $8/3$; check $8^2 - 7 \cdot 3^2 = 64 - 63 = 1$: fundamental solution $(8, 3)$, and the next is $(127, 48)$.

Theorem (Fermat, two squares). An odd prime $p$ satisfies $p = x^2 + y^2$ iff $p \equiv 1 \pmod 4$; and a general integer $n$ is a sum of two squares iff every prime $q \equiv 3 \pmod 4$ divides $n$ to an even power.

Proof idea of the prime case. For $p \equiv 1 \pmod 4$, $-1$ is a QR (Euler’s criterion), so $x^2 \equiv -1 \pmod p$ has a solution; $x^2 + 1 \equiv 0 \pmod p$ means $p \mid x^2 + 1$ with $0 < x^2 + 1 < p^2$, so by descent (repeatedly halving via a multiple of $p$) a genuine representation is produced. $\blacksquare$

Examples: $5 = 1 + 4$, $13 = 4 + 9$, $17 = 16 + 1$, $29 = 25 + 4$ ($p \equiv 1 \bmod 4$); while $3, 7, 11, 19 \equiv 3 \bmod 4$ are never sums of two squares. $21 = 3 \cdot 7$ has 3 to an odd power → not a sum of two squares. $45 = 3^2 \cdot 5$ → $45 = 36 + 9$ ✓ (3 appears to an even power).

Lagrange’s four-square theorem: every $n \geq 0$ is a sum of four squares (proven by Euler’s identity plus descent). Waring’s theorem generalises: every $n$ is a sum of at most $g(k)$ $k$-th powers; the conjectured values $g(2) = 4$, $g(3) = 9$, $g(4) = 19$ are known.

Two squares → at most four squares → the pattern of which numbers need how many squares is governed by Legendre’s three-square theorem: $n$ is a sum of three squares iff $n$ is not of the form $4^a(8b + 7)$.

• Pell has no solutions when $D$ is a perfect square ($x^2 - k^2 y^2 = 1$ factors over $\mathbb{Z}$, forcing $y = 0$).
• The fundamental solution can be astronomically large ($D = 61$ case); never guess it; use the continued fraction of $\sqrt{D}$.
• The two-squares criterion fails on the power of a $3 \bmod 4$ prime: $9 = 3^2$ is not a sum of two squares (odd power test), but $9 \cdot 5 = 45$ is.
• Products of sums of two squares are again sums of two squares (Brahmagupta); quotable in constructions.

• Congruences
• Quadratic Residues
• The Distribution of Primes

Generate Pell solutions by repeated multiplication in $\mathbb{Z}[\sqrt{D}]$: for $D = 2$, $(3 + 2\sqrt2)^2 = 17 + 12\sqrt2$, so the next solution is $(17, 12)$. Quote Brahmagupta’s identity as the reason powers of one solution are again solutions. Check every Pell solution by substitution before quoting it: $x^2 - Dy^2$ must equal exactly 1, and one arithmetic slip in a large multiplication invalidates the whole sequence.

For $D = 5$: $\sqrt5 = [2; \overline{4}]$, period 1 (odd), so $(9, 4)$ solves $x^2 - 5y^2 = 1$ from the convergent $9/4$, and $(2, 1)$ solves $x^2 - 5y^2 = -1$.

• Arithmetic Functions
• Congruences
• Continued Fractions
• Divisibility and the Euclidean Algorithm