Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 37 · Diophantine Equations

Pell's Equation and Sums of Squares

Solve x² - Dy² = 1 with continued fractions, generate infinitely many solutions, and learn which integers are sums of two squares or four squares.

Two famous questions about squares sit in this lesson. The first is Pell's equation x² - D·y² = 1, where D is a positive non-square integer. Its solutions give extremely good rational approximations of √D. The second is sums of squares: which integers can be written as a² + b², or as a sum of four squares?

Both have complete answers. Pell's equation always has infinitely many solutions, built from one smallest solution by a multiplication rule. A number is a sum of two squares precisely when its prime factors of the form 4k + 3 appear to even powers. Every non-negative integer is a sum of four squares.

Pell's equation

For D = 2 the equation is x² - 2y² = 1. Try (3, 2): 9 - 8 = 1. Next (17, 12): 289 - 288 = 1. The ratios 3/2 = 1.5, 17/12 = 1.4167 approach √2 = 1.41421.... That is no accident: x² - Dy² = 1 means (x/y)² = D + 1/y², so x/y is very close to √D.

For some D the smallest solution is huge. The infamous case D = 61 has smallest solution x = 1766319049, y = 226153980. Brute force search will not find it.

Python Brute force works only for small D

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solving with continued fractions

Lagrange showed that the smallest solution comes from the continued fraction expansion of √D, which is always periodic: √D = [a₀; a₁, a₂, ..., a_r, 2a₀, a₁, ...]. The convergents h/k are the best rational approximations, and the first convergent satisfying h² - Dk² = 1 is the fundamental solution.

Python Pell's equation via continued fractions

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All checks print True, including D = 61, 109 and 181, whose fundamental solutions have 10, 15 and 19 digits. For D = 61 you will see 1766319049, 226153980.

All solutions from the fundamental one

If (x₁, y₁) is the smallest solution, every other positive solution (xₙ, yₙ) is given by

xₙ + yₙ√D = (x₁ + y₁√D)ⁿ.

Expanding the product gives a recurrence: xₙ₊₁ = x₁xₙ + D·y₁yₙ, yₙ₊₁ = x₁yₙ + y₁xₙ. The solutions grow exponentially, and they form a group under this "multiplication", which is why the topic connects to algebraic number theory.

Python Infinitely many solutions

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ratios x/y converge to √2 quickly. The last line uses D = 8: the numbers y² for its solutions y = 1, 6, 35, ... are both square and triangular (1, 36, 1225, ...), a classic puzzle solved by Pell's equation.

Sums of two squares

Which integers n equal a² + b²? From the small cases: 1, 2, 4, 5, 8, 9, 10, 13 are, while 3, 6, 7, 11, 12, 14 are not. Fermat's two-square theorem: a prime p is a sum of two squares iff p = 2 or p ≡ 1 (mod 4). For general n: factor it; n is a sum of two squares iff every prime q ≡ 3 (mod 4) divides n to an even power.

The product rule (a² + b²)(c² + d²) = (ac - bd)² + (ad + bc)² shows that sums of two squares are closed under multiplication, which is why only the primes matter.

Python Which numbers are sums of two squares?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every prime that is 1 modulo 4 shows a representation, and none of the primes that are 3 modulo 4 would.

Counting representations: Gaussian integers

The number of ways to write n as a² + b² (counting order and signs) is r₂(n) = 4·(d₁(n) - d₃(n)), where d₁ and d₃ count divisors of n congruent to 1 and 3 modulo 4. This is Jacobi's formula. It follows from unique factorization in the Gaussian integers ℤ[i], where a² + b² = (a + bi)(a - bi).

Python Jacobi's formula for r2(n)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For instance, 65 = 5 × 13 has 16 representations: 1² + 8² and 4² + 7², each with 8 sign and order variants.

Four squares

Lagrange's four-square theorem (1770): every non-negative integer is a sum of four squares, so a² + b² + c² + d² covers all of ℕ. Numbers of the form 4^a(8b + 7) need all four, by Legendre's three-square theorem. A simple search verifies the theorem.

Python Lagrange's four squares

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The theorem holds for all numbers tested, and the last line lists those that cannot be written with three squares: 7, 15, 23, 28, 31, 39, 47, 55.

flowchart TD
    N["n"] --> Q{"primes 3 mod 4 all to even powers?"}
    Q -->|yes| TWO["sum of two squares"]
    Q -->|no| T{"n = 4^a (8b + 7)?"}
    T -->|yes| FOUR["needs four squares"]
    T -->|no| THREE["sum of three squares"]

How many squares does an integer need?

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which of these is the fundamental solution of x^2 - 2y^2 = 1?

    3^2 - 2*2^2 = 9 - 8 = 1, and no smaller positive pair works.
  2. 2. How are further Pell solutions generated?

    (x1 + y1 sqrt D)^n expands into x_n + y_n sqrt D with x_n^2 - D y_n^2 = 1.
  3. 3. Which number is NOT a sum of two squares?

    21 = 3 * 7 has two primes that are 3 mod 4, each to an odd power.
  4. 4. Which integer needs four squares (cannot be a sum of three)?

    28 = 4 * 7 has the form 4^a(8b + 7).

Summary

  • Pell's equation x² - Dy² = 1 has infinitely many solutions when D is not a square; the smallest comes from the continued fraction of √D.
  • All solutions are the powers of the fundamental one in ℤ[√D].
  • n is a sum of two squares iff primes ≡ 3 (mod 4) occur to even powers; Jacobi's formula counts the representations.
  • Every non-negative integer is a sum of four squares; numbers 4^a(8b + 7) need all four.

Next: Quadratic Residues and Euler's Criterion