9. Diophantine equations¶

Which whole numbers \(a, b, c\) satisfy \(a^2 + b^2 = c^2\)? Are there any with \(a^4 + b^4 = c^4\)? Which \(x, y\) solve \(x^2 - 61y^2 = 1\)? An equation whose solutions must be whole numbers (or fractions) is called a Diophantine equation, after Diophantus of Alexandria, whose Arithmetica (probably third century CE) collected problems of this kind. This chapter solves the first equation completely, proves the second impossible with Fermat's method of infinite descent, and shows that the third always has infinitely many solutions forming a group. It then tours some famous equations, solved and unsolved, and ends with a theorem that puts a limit on the whole subject: no algorithm can decide whether an arbitrary Diophantine equation has a solution.

In this chapter

You will learn:

every Pythagorean triple, by algebra and by drawing lines through a point on a circle
Fermat's method of infinite descent, and a full proof that \(x^4 + y^4 = z^2\) has no solutions in positive integers
Pell's equation \(x^2 - dy^2 = 1\): why its solutions form a group, generated by one fundamental solution
how congruences show that an equation has no solutions, and where that test stops working
Markov's equation, Catalan's equation, sums of three cubes and other famous cases
Hilbert's tenth problem and Matiyasevich's theorem: there is no general method

You need: Chapter 2 (unique factorization), Chapter 3 (gcd; linear Diophantine equations), Chapter 4 (congruences) and Chapter 8 for some arguments mod \(p\). The gentler versions are Pythagorean triples and Linear Diophantine equations.

Levels: 9.1 is intermediate; 9.2 and 9.3 are advanced; 9.4 is advanced with statements at expert level; 9.5 is expert (the ideas, not the full proof).

9.1 Pythagorean triples¶

The triangle with sides 3, 4, 5 has a right angle, because \(3^2 + 4^2 = 9 + 16 = 25 = 5^2\). A Babylonian clay tablet known as Plimpton 322 (about 1800 BCE) lists fifteen rows of numbers that are read today as sides of such triangles, some as large as \(12\,709\), \(13\,500\), \(18\,541\); so the question of finding them is very old.

Definition

A Pythagorean triple is a triple \((a, b, c)\) of positive integers with \(a^2 + b^2 = c^2\). It is primitive if \(\gcd(a, b, c) = 1\).

Multiplying a triple by any \(k\) gives another (\(6, 8, 10\) from \(3, 4, 5\)). Conversely, if \(d = \gcd(a, b, c)\), dividing by \(d\) gives a primitive triple. So it is enough to find the primitive ones. Note that in a primitive triple any two of \(a, b, c\) are already coprime: a prime dividing \(a\) and \(b\) divides \(c^2\), hence \(c\); a prime dividing \(a\) and \(c\) divides \(b^2\), hence \(b\).

Theorem 9.1 (Pythagorean triples)

The primitive Pythagorean triples with \(b\) even are exactly

\[ a = m^2 - n^2, \qquad b = 2mn, \qquad c = m^2 + n^2, \]

where \(m > n > 0\) are coprime integers of opposite parity (one even, one odd). Each primitive triple arises from exactly one such pair.

Proof. These are triples: \((m^2 - n^2)^2 + (2mn)^2 = m^4 - 2m^2n^2 + n^4 + 4m^2n^2 = (m^2 + n^2)^2\). They are primitive: a prime \(p\) dividing \(a\) and \(c\) divides their sum \(2m^2\) and difference \(2n^2\); \(p \ne 2\) since \(c\) is odd (\(m, n\) have opposite parity); so \(p \mid m\) and \(p \mid n\), contradicting \(\gcd(m, n) = 1\).

Every primitive triple has this form. Let \((a, b, c)\) be primitive. Not both \(a, b\) are even (they are coprime). Not both are odd: odd squares are \(\equiv 1 \pmod 4\), so \(c^2 \equiv 2 \pmod 4\), which no square is. So exactly one is even; call it \(b\). Then \(a\) and \(c\) are odd, and

\[ b^2 = c^2 - a^2 = (c - a)(c + a), \qquad \left(\frac b2\right)^2 = \frac{c + a}{2} \cdot \frac{c - a}{2} , \]

where both fractions are whole numbers, since \(c \pm a\) are even. Let \(u = (c+a)/2\) and \(v = (c-a)/2\). Any common divisor of \(u\) and \(v\) divides \(u + v = c\) and \(u - v = a\), so \(\gcd(u, v) = 1\). Two coprime positive integers whose product is a square must each be squares (look at each prime's exponent, by unique factorization). So \(u = m^2\) and \(v = n^2\) with \(m > n > 0\), and

\[ c = u + v = m^2 + n^2, \qquad a = u - v = m^2 - n^2, \qquad b = 2\sqrt{uv} = 2mn . \]

Here \(\gcd(m, n) = 1\) because \(\gcd(u, v) = 1\), and \(m, n\) have opposite parity because \(c\) is odd. Finally \(m, n\) are determined by the triple (\(m^2 = (c+a)/2\), \(n^2 = (c-a)/2\)), which gives uniqueness. \(\square\)

Worked example. The pairs \((m, n)\) with \(m \le 4\): \((2, 1) \to (3, 4, 5)\); \((3, 2) \to (5, 12, 13)\); \((4, 1) \to (15, 8, 17)\); \((4, 3) \to (7, 24, 25)\). (\((3, 1)\) is excluded since both are odd: it gives \((8, 6, 10)\), not primitive.) There are exactly 16 primitive triples with \(c < 100\); the largest is \((65, 72, 97)\) from \((m, n) = (9, 4)\).

The same answer by geometry¶

Divide \(a^2 + b^2 = c^2\) by \(c^2\): \((a/c)^2 + (b/c)^2 = 1\). So primitive triples correspond to rational points on the unit circle \(x^2 + y^2 = 1\), points whose coordinates are both fractions. There is a beautiful way to find them all.

Start from the obvious rational point \(A = (-1, 0)\). Draw the line through \(A\) with slope \(t\). It meets the circle in one more point \(P\). If \(t\) is rational, so is \(P\); and conversely, if \(P\) is rational, the slope of \(AP\) is rational.

To find \(P\), substitute \(y = t(x + 1)\) into \(x^2 + y^2 = 1\):

\[ x^2 + t^2(x+1)^2 = 1 \iff (x + 1)\big((1 + t^2)x - (1 - t^2)\big) = 0 . \]

The root \(x = -1\) is \(A\); the other root gives

\[ P = \left( \frac{1 - t^2}{1 + t^2},\ \frac{2t}{1 + t^2} \right) . \]

With \(t = n/m\) this is \(\big((m^2 - n^2)/(m^2 + n^2),\ 2mn/(m^2 + n^2)\big)\): the formulas of Theorem 9.1 again. In the picture \(t = 1/2\) gives \(P = (3/5, 4/5)\), the 3-4-5 triangle.

This "chord method" is the first example of a principle that runs through the rest of the book: a curve's rational points are governed by its geometry. A conic (degree 2) with one rational point has infinitely many, all given by one parameter \(t\). A cubic is different: a line through one rational point usually meets it in two more, which need not be rational, and through two rational points in a third, which is. That leads to the group of points on an elliptic curve (Chapter 19).

And not every conic has a rational point. The circle \(x^2 + y^2 = 3\) has none: if \((a/c)^2 + (b/c)^2 = 3\) with \(\gcd(a, b, c) = 1\) then \(a^2 + b^2 = 3c^2\). Mod 3, squares are 0 or 1, so \(a^2 + b^2 \equiv 0\) forces \(3 \mid a\) and \(3 \mid b\); then \(9 \mid 3c^2\), so \(3 \mid c\), contradicting \(\gcd = 1\).

9.2 Fermat's descent¶

Level: advanced.

In the margin of his copy of Diophantus, next to the problem on Pythagorean triples, Pierre de Fermat wrote (around 1637) that it is impossible to split a cube into two cubes, or a fourth power into two fourth powers, or in general any power higher than the second into two like powers, and that he had a truly marvellous proof which the margin was too narrow to contain. The note was published by his son in 1670, after Fermat's death. The general claim became Fermat's last theorem, proved by Andrew Wiles in 1994 (Chapter 20). For the fourth power, though, Fermat did leave an argument, and it introduced a method.

Infinite descent is a form of proof by contradiction. Show that from any positive integer solution you can build another with a strictly smaller positive size. Then there would be an infinite strictly decreasing sequence of positive integers, which is impossible. Equivalently: take a solution with the smallest size, and produce a smaller one.

Theorem 9.2 (Fermat)

The equation \(x^4 + y^4 = z^2\) has no solutions in positive integers.

Proof. Suppose there are solutions, and choose one with \(z\) as small as possible.

Step 1: \(\gcd(x, y) = 1\). If a prime \(p\) divides both \(x\) and \(y\), then \(p^4 \mid z^2\), so \(p^2 \mid z\), and \((x/p, y/p, z/p^2)\) is a solution with smaller \(z\).

Step 2: a primitive triple. \((x^2)^2 + (y^2)^2 = z^2\), and \(\gcd(x^2, y^2) = 1\), so \((x^2, y^2, z)\) is a primitive Pythagorean triple. Exactly one of \(x^2, y^2\) is even; say \(y\) is even. By Theorem 9.1 there are coprime \(m > n > 0\) of opposite parity with

\[ x^2 = m^2 - n^2, \qquad y^2 = 2mn, \qquad z = m^2 + n^2 . \]

Step 3: a second triple. The first equation says \(x^2 + n^2 = m^2\), with \(\gcd(m, n) = 1\): another primitive triple. Here \(x\) is odd, so \(n\) must be the even member: if \(n\) were odd and \(m\) even, then \(x^2 = m^2 - n^2 \equiv 0 - 1 \equiv 3 \pmod 4\), impossible. Applying Theorem 9.1 again, there are coprime \(r > s > 0\) with

\[ x = r^2 - s^2, \qquad n = 2rs, \qquad m = r^2 + s^2 . \]

Step 4: three squares. Now \(y^2 = 2mn = 4rs(r^2 + s^2)\), so \((y/2)^2 = r \cdot s \cdot (r^2 + s^2)\). The three factors are pairwise coprime: \(\gcd(r, s) = 1\), and a prime dividing \(r\) and \(r^2 + s^2\) would divide \(s^2\). A product of pairwise coprime positive integers that is a square has each factor a square. So \(r = u^2\), \(s = v^2\), \(r^2 + s^2 = w^2\) for positive integers \(u, v, w\).

Step 5: descent. Then \(u^4 + v^4 = r^2 + s^2 = w^2\): a new solution. And \(w \le w^2 = m \le m^2 < m^2 + n^2 = z\) (the last step uses \(n > 0\)). This contradicts the minimality of \(z\). \(\square\)

Corollary 9.3. \(x^4 + y^4 = z^4\) has no solutions in positive integers, since \((x, y, z^2)\) would solve Theorem 9.2. This is Fermat's last theorem for exponent 4. It has a useful consequence: if \(n\) is divisible by 4, then \(x^n + y^n = z^n\) has no solutions either (\(x^n = (x^{n/4})^4\)). Every \(n \ge 3\) is divisible by 4 or by an odd prime, so Fermat's last theorem reduces to the case of odd prime exponents. Euler handled \(n = 3\) (1770, with a gap later filled), Dirichlet and Legendre \(n = 5\) (around 1825), Lamé \(n = 7\) (1839), and Kummer a large class of primes in the 1840s (Algebra, Chapter 18).

Fermat's own application. The same descent (applied to \(x^4 - y^4 = z^2\), a close cousin) proves that the area \(ab/2\) of a right triangle with whole-number sides is never a perfect square. Equivalently, 1 is not a congruent number: no right triangle with rational sides has area 1. The congruent number problem, which asks which whole numbers are areas of rational right triangles, leads straight to elliptic curves and the Birch and Swinnerton-Dyer conjecture (Chapter 19).

Why descent works so often. In Step 2 to Step 4, the equation was taken apart using unique factorization ("coprime factors of a square are squares"). That only works in rings where unique factorization holds. In the 1840s attempts to prove Fermat's last theorem by factoring \(x^p + y^p\) over the complex numbers ran into exactly this obstacle, and the repair (ideals, the class number) became algebraic number theory (Chapter 17).

9.3 Pell's equation¶

Level: advanced.

Look for whole numbers with \(x^2 - 2y^2 = 1\). A small search finds \((3, 2)\): \(9 - 8 = 1\). The next is \((17, 12)\): \(289 - 288 = 1\). Then \((99, 70)\), \((577, 408)\). The fractions \(3/2, 17/12, 99/70, 577/408\) are very good approximations of \(\sqrt 2 \approx 1.4142136\) (indeed \(577/408 \approx 1.4142157\)), and that is no coincidence: \(x^2 - 2y^2 = 1\) means \(x/y = \sqrt{2 + 1/y^2}\).

Definition

Pell's equation is \(x^2 - dy^2 = 1\), where \(d\) is a positive integer that is not a perfect square, to be solved in integers \(x, y\).

The solutions \((\pm 1, 0)\) are trivial. (If \(d\) were a square \(k^2\), then \((x - ky)(x + ky) = 1\) would force only the trivial solutions; that is why squares are excluded.) The name is a historical accident: Euler attributed the equation to John Pell, who had little to do with it. It is far older, as we will see.

Multiplying solutions¶

The key is to factor the equation using \(\sqrt d\):

\[ x^2 - dy^2 = (x + y\sqrt d)(x - y\sqrt d) . \]

Consider numbers of the form \(\alpha = x + y\sqrt d\) with \(x, y\) integers. They form a ring, written \(\mathbb{Z}[\sqrt d]\): sums and products stay of that form, since \((x + y\sqrt d)(u + v\sqrt d) = (xu + dyv) + (xv + yu)\sqrt d\). Its conjugate is \(\bar\alpha = x - y\sqrt d\), and its norm is \(N(\alpha) = \alpha\bar\alpha = x^2 - dy^2\). Since \(\sqrt d\) is irrational, \(x\) and \(y\) are determined by \(\alpha\) (see Chapter 2 for irrationality of square roots), and a direct computation shows conjugation respects products: \(\overline{\alpha\beta} = \bar\alpha\bar\beta\). So

\[ N(\alpha\beta) = \alpha\beta\bar\alpha\bar\beta = N(\alpha)N(\beta) . \]

Pell's equation asks for the \(\alpha\) with \(N(\alpha) = 1\). By the norm rule, the product of two solutions is a solution. This identity, in the form

\[ (x^2 - dy^2)(u^2 - dv^2) = (xu + dyv)^2 - d(xv + yu)^2 , \]

was found by Brahmagupta in 628, in his Brāhmasphuṭasiddhānta; he called the combining of solutions bhāvanā.

Worked example. \((3 + 2\sqrt 2)^2 = 9 + 12\sqrt 2 + 8 = 17 + 12\sqrt 2\) and \((3 + 2\sqrt 2)^3 = (17 + 12\sqrt 2)(3 + 2\sqrt 2) = 51 + 48 + (34 + 36)\sqrt 2 = 99 + 70\sqrt 2\). The powers of the first solution produce all the others. In general, from \((x, y)\) the next solution of \(x^2 - 2y^2 = 1\) is \((3x + 4y, 2x + 3y)\).

Also, if \(N(\alpha) = 1\) then \(\alpha^{-1} = \bar\alpha\), again of the same form. So the solutions of Pell's equation, viewed as numbers \(x + y\sqrt d\), form a group under multiplication: they are the units of norm 1 in \(\mathbb{Z}[\sqrt d]\).

Every solution is a power of one¶

Theorem 9.4

Suppose Pell's equation \(x^2 - dy^2 = 1\) has a nontrivial solution. Let \(\varepsilon = x_1 + y_1\sqrt d\) be the smallest solution with \(\varepsilon > 1\) (the fundamental solution). Then the solutions are exactly \(\pm\varepsilon^k\) for \(k \in \mathbb{Z}\). In particular, the positive solutions \((x_k, y_k)\) are given by \(x_k + y_k\sqrt d = \varepsilon^k\) for \(k = 1, 2, 3, \dots\)

Proof. First, which \(\alpha = x + y\sqrt d\) of norm 1 are greater than 1? If \(\alpha > 1\) then \(\bar\alpha = 1/\alpha\) lies in \((0, 1)\), so \(x = (\alpha + \bar\alpha)/2 > 0\) and \(y\sqrt d = (\alpha - \bar\alpha)/2 > 0\). So \(\alpha > 1\) exactly when \(x, y > 0\). Among solutions with \(x, y \ge 1\), the size of \(\alpha\) grows with \(x\) and \(y\), so there is a smallest one, \(\varepsilon\), as soon as there is any.

Now let \(\eta\) be any solution with \(\eta > 1\). Since \(\varepsilon > 1\), its powers grow without bound, so there is a \(k \ge 1\) with \(\varepsilon^k \le \eta < \varepsilon^{k+1}\). Divide by \(\varepsilon^k\): the number \(\theta = \eta \varepsilon^{-k} = \eta\,\bar\varepsilon^{\,k}\) is in \(\mathbb{Z}[\sqrt d]\), has norm \(1 \cdot 1 = 1\), and satisfies \(1 \le \theta < \varepsilon\). If \(\theta > 1\) it would be a solution between 1 and \(\varepsilon\), contradicting the choice of \(\varepsilon\). So \(\theta = 1\) and \(\eta = \varepsilon^k\).

Every solution \(\eta\) is \(\pm 1\), or \(\eta > 1\), or \(0 < \eta < 1\) (then \(1/\eta = \bar\eta > 1\)), or negative (then \(-\eta\) is positive). Applying the previous paragraph covers all cases: \(\eta = \pm\varepsilon^k\). \(\square\)

In group language, the solutions form the group \(\{\pm 1\} \times \mathbb{Z}\): a sign, and a free exponent. This is the simplest case of Dirichlet's unit theorem (Chapter 17).

Existence¶

Theorem 9.4 assumed a nontrivial solution exists. It always does:

Theorem 9.5 (Lagrange, 1768)

For every positive integer \(d\) that is not a square, \(x^2 - dy^2 = 1\) has a solution with \(y \ne 0\), and hence infinitely many.

We state it here and prove it in Chapter 10, where continued fractions both prove the theorem and compute the fundamental solution. The idea: Dirichlet's approximation theorem gives infinitely many fractions \(x/y\) with \(|x - y\sqrt d| < 1/y\); for these, \(|x^2 - dy^2| = |x - y\sqrt d| \cdot |x + y\sqrt d| < 2\sqrt d + 1\), so some value \(N\) of \(x^2 - dy^2\) occurs infinitely often; two such pairs that are congruent mod \(|N|\) can be divided to produce a solution of norm 1.

The fundamental solution can be enormous. A few examples:

\(d\)	fundamental solution \((x_1, y_1)\)
2	\((3, 2)\)
3	\((2, 1)\)
7	\((8, 3)\)
13	\((649, 180)\)
61	\((1\,766\,319\,049,\ 226\,153\,980)\)
109	\((158\,070\,671\,986\,249,\ 15\,140\,424\,455\,100)\)

Check for \(d = 13\): \(649^2 = 421\,201\) and \(13 \cdot 180^2 = 421\,200\).

The size jumps erratically with \(d\): \(d = 60\) has \((31, 4)\), while its neighbour 61 needs ten digits. No simple pattern holds; the fundamental solution can have on the order of \(\sqrt d\) digits.

History¶

Brahmagupta (628) solved several cases, including \(x^2 - 92y^2 = 1\) with \((1151, 120)\), by combining solutions of \(x^2 - dy^2 = k\) for small \(k\). Bhāskara II (1150) gave a general method, the chakravāla ("cyclic") method, and used it to solve \(d = 61\). In Europe, Fermat in 1657 challenged English mathematicians with the equation, naming \(d = 61\) and \(d = 109\) as examples; Brouncker and Wallis found a method. Euler studied it with continued fractions; Lagrange gave the first complete proof of existence in 1768.

A famous instance is the cattle problem attributed to Archimedes, a poem that asks for the sizes of herds of the sun god's cattle under arithmetic conditions. It reduces to a Pell equation with \(d = 410\,286\,423\,278\,424\). A. Amthor showed in 1880 that the smallest answer has 206 545 digits; it was first printed out in full with computer help in 1965 (by Williams, German and Zarnke).

The negative Pell equation¶

What about \(x^2 - dy^2 = -1\)? For \(d = 2\): \((1, 1)\), \((7, 5)\), \((41, 29)\), which are the odd powers of \(1 + \sqrt 2\) (note \((1 + \sqrt 2)^2 = 3 + 2\sqrt 2\), the fundamental solution of the \(+1\) equation). But for \(d = 3\) there is no solution: mod 3 it says \(x^2 \equiv -1 \equiv 2\), and 2 is not a square mod 3. More generally, if any prime \(p \equiv 3 \pmod 4\) divides \(d\), then \(x^2 \equiv -1 \pmod p\) is impossible (Chapter 8). Exactly which \(d\) allow a solution is subtle; the proportion among suitable \(d\) was a long-standing conjecture of Peter Stevenhagen, on which there has been major recent progress (Koymans and Pagano, 2022).

Try it in Python

from math import isqrt

def pell_bruteforce(d, ymax=10**6):
    """Smallest y >= 1 with d*y^2 + 1 a square. Only for small fundamental solutions."""
    for y in range(1, ymax):
        x2 = d * y * y + 1
        x = isqrt(x2)
        if x * x == x2:
            return x, y

def powers(x1, y1, d, k):
    x, y, out = x1, y1, []
    for _ in range(k):
        out.append((x, y))
        x, y = x1 * x + d * y1 * y, x1 * y + y1 * x
    return out

print(pell_bruteforce(13))        # (649, 180)
print(powers(3, 2, 2, 5))         # (3,2) (17,12) (99,70) (577,408) (3363,2378)

Brute force fails badly for \(d = 61\); Chapter 10 gives a method that finds it at once.

9.4 Markov's equation and other famous equations¶

Level: advanced, with expert statements.

Congruence obstructions¶

The quickest way to show an equation has no solutions is to find a modulus where it has none. Some examples:

\(x^2 + y^2 = 4k + 3\): squares are 0 or 1 mod 4, so a sum of two squares is 0, 1 or 2 mod 4, never 3.
\(x^2 - 3y^2 = 2\): mod 3, \(x^2 \equiv 2\), impossible.
\(x^3 + y^3 + z^3 = n\) with \(n \equiv 4\) or \(5 \pmod 9\): cubes mod 9 are only \(0, 1, 8\) (that is \(0, \pm 1\)), since \((3k)^3 \equiv 0\) and \((3k \pm 1)^3 = 27k^3 \pm 27k^2 + 9k \pm 1 \equiv \pm 1\). Three of them add to at most \(\pm 3\), never \(\pm 4\) mod 9.

But the method has limits. An equation can have solutions mod every \(n\) and still have no integer solutions. For quadratic forms, the Hasse-Minkowski theorem says that "solvable mod every \(n\) and over the reals" does imply "solvable in rationals"; for cubic equations it fails, as Selmer's example \(3x^3 + 4y^3 + 5z^3 = 0\) shows (Chapter 18).

Markov's equation¶

\[ x^2 + y^2 + z^2 = 3xyz \]

Small solutions: \((1, 1, 1)\), \((1, 1, 2)\), \((1, 2, 5)\), \((1, 5, 13)\), \((2, 5, 29)\). Andrey Markov met this equation in 1879-1880 while studying how well real numbers can be approximated by fractions (Chapter 10): the numbers appearing in its solutions, the Markov numbers \(1, 2, 5, 13, 29, 34, 89, 169, 194, 233, 433, 610, 985, \dots\), describe the worst-approximable numbers and binary quadratic forms with extreme minima.

Vieta jumping. Fix \(y\) and \(z\) and view the equation as a quadratic in \(x\):

\[ x^2 - 3yz\,x + (y^2 + z^2) = 0 . \]

If \(x\) is one root, the other is \(x' = 3yz - x\) (the roots sum to \(3yz\)), which is also a positive integer, since \(xx' = y^2 + z^2 > 0\). So from any solution we can jump to a new one by replacing one coordinate: \((x, y, z) \mapsto (3yz - x, y, z)\). From \((1, 2, 5)\) the three jumps give \((29, 2, 5)\), \((1, 13, 5)\) and \((1, 2, 1)\).

Theorem 9.6 (Markov)

Every positive solution of \(x^2 + y^2 + z^2 = 3xyz\) can be reached from \((1, 1, 1)\) by a sequence of such jumps (and permutations). The solutions form an infinite tree in which every vertex other than the first two has three neighbours.

Proof (descent). Take a solution with \(x \le y \le z\). Let \(f(t) = t^2 - 3xy\,t + (x^2 + y^2)\); its two roots are \(z\) and \(z' = 3xy - z\), with \(zz' = x^2 + y^2 > 0\), so \(z' > 0\). Evaluate \(f\) at \(y\):

\[ f(y) = y^2 - 3xy^2 + x^2 + y^2 = x^2 - (3x - 2)y^2 \le x^2 - y^2 \le 0 , \]

using \(3x - 2 \ge 1\) and \(y \ge x\). A monic quadratic is \(\le 0\) only between its roots, so \(z' \le y \le z\). Equality \(f(y) = 0\) needs both inequalities to be equalities: \(3x - 2 = 1\) and \(y = x\), so \(x = y = 1\), and then \(2 + z^2 = 3z\) gives \(z = 1\) or \(z = 2\). So for every solution other than \((1, 1, 1)\) and \((1, 1, 2)\) we have \(f(y) < 0\), hence \(z' < y \le z\): jumping in the largest coordinate gives a solution with a strictly smaller sum. Sums of positive integers cannot decrease forever, so repeated jumps reach \((1, 1, 1)\) or \((1, 1, 2)\), and \((1, 1, 2)\) jumps to \((1, 1, 1)\). Each jump is its own inverse (jumping twice in the same place returns), so retracing the path leads from \((1, 1, 1)\) to the solution we started with. \(\square\)

The uniqueness conjecture. In every solution found so far, the largest number determines the other two: there is only one Markov triple with largest entry 5, one with 13, one with 29, and so on. Frobenius asked in 1913 whether this always holds. The Markov uniqueness conjecture is still open; it has been checked for very large Markov numbers and proved for some special ones (for example prime powers).

Catalan's equation¶

The numbers 8 and 9 are consecutive and both perfect powers: \(3^2 - 2^3 = 1\). Eugène Catalan conjectured in 1844 that this is the only case: \(x^a - y^b = 1\) with \(x, y, a, b > 1\) has only the solution \(3^2 - 2^3\). Preda Mihăilescu proved it in 2002, with a proof based on cyclotomic fields that is famous for using only classical (if deep) tools.

Ramanujan-Nagell¶

For which \(n\) is \(2^n - 7\) a perfect square? \(2^3 - 7 = 1\), \(2^4 - 7 = 9\), \(2^5 - 7 = 25\), \(2^7 - 7 = 121\) and \(2^{15} - 7 = 32\,761 = 181^2\). Ramanujan conjectured in 1913 that these are all; Trygve Nagell proved it in 1948, working in the ring \(\mathbb{Z}[(1 + \sqrt{-7})/2]\), which has unique factorization.

Sums of three cubes¶

Which integers \(n\) are \(x^3 + y^3 + z^3\) with \(x, y, z\) integers (negative allowed)? The congruence argument rules out \(n \equiv \pm 4 \pmod 9\), and it is conjectured that every other \(n\) is possible, in infinitely many ways. The solutions can be huge. For \(n = 33\), the first solution was found by Andrew Booker in 2019:

\[ 33 = 8\,866\,128\,975\,287\,528^3 + (-8\,778\,405\,442\,862\,239)^3 + (-2\,736\,111\,468\,807\,040)^3 , \]

and the last case below 100, \(n = 42\), was solved by Booker and Andrew Sutherland later in 2019 with a large distributed computation:

\[ 42 = (-80\,538\,738\,812\,075\,974)^3 + 80\,435\,758\,145\,817\,515^3 + 12\,602\,123\,297\,335\,631^3 . \]

Check: Python's integers are exact, so typing either right side gives 33 and 42. Whether every \(n \not\equiv \pm 4 \pmod 9\) is a sum of three cubes is unknown; there is not even an algorithm known to decide it for a given \(n\).

Fermat's last theorem and beyond¶

\(x^n + y^n = z^n\) has no positive solutions for \(n \ge 3\) (Wiles, with Taylor, 1995). Its generalisation \(x^a + y^b = z^c\) with \(1/a + 1/b + 1/c < 1\) (the Fermat-Catalan or Beal-type equations) is open in general (Chapter 20), and the abc conjecture would control it (Chapter 21).

9.5 Hilbert's tenth problem¶

Level: expert (the ideas; the full proof fills a short book).

At the International Congress of Mathematicians in Paris in 1900, David Hilbert presented a list of problems for the new century. The tenth asked for a process which, given any Diophantine equation (a polynomial equation with integer coefficients in any number of unknowns), decides in a finite number of steps whether it has a solution in integers.

Notice what is and is not asked. Not a formula for the solutions, just a yes-or-no procedure. For a single unknown there is one (an integer root divides the constant term). For two-variable quadratics there is one (via Pell's equation and congruences). Hilbert assumed the general answer would also be yes.

It is no. The answer came in stages:

In the 1930s Gödel, Church and Turing made "algorithm" precise and showed that some yes-or-no problems, such as whether a computer program ever stops, have no algorithm.
Martin Davis (1950s) conjectured that the sets of integers definable by Diophantine equations are exactly the sets a computer can list, the listable (recursively enumerable) sets.
Davis, Hilary Putnam and Julia Robinson proved in 1961 that this holds if one also allows the unknowns to appear in exponents, and that the exponential case reduces to one fact: a Diophantine set whose growth is exponential.
Yuri Matiyasevich, in 1970, supplied that fact, using the Fibonacci numbers. He showed that the relation \(y = F_{2x}\) (Fibonacci numbers) is Diophantine. (Later proofs use the solutions of Pell's equation \(x^2 - (a^2 - 1)y^2 = 1\), which grow exponentially in the same way.)

Theorem 9.7 (Matiyasevich-Robinson-Davis-Putnam, 1970)

A set of positive integers is listable by a computer program if and only if it is Diophantine: there is a polynomial \(P(a, x_1, \dots, x_m)\) with integer coefficients such that \(a\) is in the set exactly when \(P(a, x_1, \dots, x_m) = 0\) has a solution in non-negative integers \(x_1, \dots, x_m\). Consequently, there is no algorithm that decides, for every Diophantine equation, whether it has an integer solution.

The second sentence follows from the first: if there were such an algorithm, it would decide membership in every listable set, including the set of programs that halt, which Turing showed is impossible.

Strange consequences.

A polynomial for the primes. The primes are listable, so they are Diophantine. Rearranging gives a polynomial whose positive values, as its variables run over the non-negative integers, are exactly the primes. J. P. Jones, D. Sato, H. Wada and D. Wiens wrote one down explicitly in 1976, with 26 variables and degree 25. It is useless for computing primes, but it exists.
Few variables suffice. Matiyasevich showed that 9 unknowns are enough for a "universal" equation, one able to encode every listable set (the proof was written up by Jones in 1982).
Undecidable statements. For any consistent formal system strong enough for arithmetic (such as the usual axioms of set theory), there is a specific Diophantine equation that has no solutions, but whose lack of solutions cannot be proved in that system. Gödel's incompleteness, translated into a polynomial.
Famous problems become equations. Goldbach's conjecture and the Riemann hypothesis can each be rewritten as "this particular Diophantine equation has no solutions".

What is still open. The same question over the rationals, deciding whether a polynomial equation has a solution in fractions, is unsolved. It contains, for example, deciding whether an elliptic curve has infinitely many rational points, which is linked to the Birch and Swinnerton-Dyer conjecture (Chapter 19). Many experts suspect that the answer may even be positive for curves, and the analogous questions over rings of integers of number fields are an active research area.

So the subject of this chapter has no master key. Each family of equations needs its own idea: factorization and descent for Pythagoras and Fermat, groups for Pell and for elliptic curves, congruences for impossibility, and deep machinery (modular forms, cyclotomic fields, linear forms in logarithms) for the hardest cases.

Check yourself¶

1. List the primitive Pythagorean triples with \(c < 30\).

From \((m, n) = (2,1), (3,2), (4,1), (4,3), (5,2)\): \((3, 4, 5)\), \((5, 12, 13)\), \((15, 8, 17)\), \((7, 24, 25)\), \((21, 20, 29)\). The next pairs, \((5, 4)\) and \((6, 1)\), give \(c = 41\) and \(37\).

2. Prove that in every Pythagorean triple, \(60\) divides \(abc\).

It suffices to do primitive triples. 4: \(b = 2mn\) and one of \(m, n\) is even, so \(4 \mid b\). 3: if \(3 \nmid a, b\) then \(a^2 + b^2 \equiv 2 \pmod 3\), not a square. 5: squares mod 5 are \(0, \pm 1\); if none of \(a, b\) is divisible by 5, then \(a^2 + b^2 \in \{0, \pm 2\}\) mod 5, and it must be a square, so it is 0 and \(5 \mid c\).

3. Which rational point on \(x^2 + y^2 = 1\) does the line through \((-1, 0)\) of slope \(2/3\) hit? Which triple is it?

\(x = (1 - 4/9)/(1 + 4/9) = 5/13\) and \(y = (4/3)/(13/9) = 12/13\): the triple \((5, 12, 13)\).

4. Show that \(x^2 + y^2 = 3\) has no rational solutions, but \(x^2 + y^2 = 2\) has infinitely many.

The first was shown at the end of 9.1 (descent mod 3). For the second, \((1, 1)\) is a rational point, and lines of rational slope through it give infinitely many: with slope \(t\), the second point is \(\big((t^2 - 2t - 1)/(t^2 + 1), (-t^2 - 2t + 1)/(t^2 + 1)\big)\); \(t = 2\) gives \((-1/5, -7/5)\), and \(1/25 + 49/25 = 2\).

5. Find the first three positive solutions of \(x^2 - 3y^2 = 1\).

Fundamental: \((2, 1)\). Then \((2 + \sqrt 3)^2 = 7 + 4\sqrt 3\) and \((2 + \sqrt 3)^3 = (7 + 4\sqrt 3)(2 + \sqrt 3) = 26 + 15\sqrt 3\). Check: \(676 - 675 = 1\).

6. Verify Brahmagupta's solution of \(x^2 - 92y^2 = 1\) and find the next one.

\(1151^2 = 1\,324\,801\) and \(92 \cdot 120^2 = 1\,324\,800\). The next is \((1151 + 120\sqrt{92})^2 = 1151^2 + 92 \cdot 120^2 + 2 \cdot 1151 \cdot 120\sqrt{92} = 2\,649\,601 + 276\,240\sqrt{92}\).

7. Show that \(x^2 - 3y^2 = -1\) and \(x^2 - 7y^2 = -1\) have no integer solutions.

Mod 3: \(x^2 \equiv -1 \equiv 2\), impossible. Mod 7: \(x^2 \equiv -1\), impossible since \(7 \equiv 3 \pmod 4\). (Or mod 4 for both: \(x^2 - 3y^2 \equiv x^2 + y^2 \in \{0, 1, 2\}\), never \(3 \equiv -1\).)

8. Starting from the Markov triple \((1, 5, 13)\), find its three neighbours.

Replace each entry by \(3 \times\) (product of the other two) minus itself: \(3 \cdot 65 - 1 = 194\), giving \((194, 5, 13)\); \(3 \cdot 13 - 5 = 34\), giving \((1, 34, 13)\); \(3 \cdot 5 - 13 = 2\), giving \((1, 5, 2)\). Check: \(1 + 1156 + 169 = 1326 = 3 \cdot 1 \cdot 34 \cdot 13\).

9. Prove that \(x^3 + y^3 + z^3 = 2021\) has no integer solutions. Does the same argument work for 2023?

\(2021 = 224 \cdot 9 + 5\), so \(2021 \equiv 5 \equiv -4 \pmod 9\). Each cube is \(0\) or \(\pm 1\) mod 9, so three cubes sum to something in \(\{-3, \dots, 3\}\) mod 9, never \(\pm 4\). No solutions. For 2023: \(2023 = 224 \cdot 9 + 7 \equiv -2 \pmod 9\), which is \((-1) + (-1) + 0\), so the mod 9 test does not rule it out. Always compute the residue before claiming an obstruction.

10. Explain why Theorem 9.2 implies that \(x^n + y^n = z^n\) has no positive solutions when \(4 \mid n\), and why that reduces Fermat's last theorem to odd prime exponents.

If \(n = 4k\), a solution gives \((x^k)^4 + (y^k)^4 = (z^{2k})^2\), contradicting Theorem 9.2. Any \(n \ge 3\) not divisible by 4 has an odd prime factor \(p\), and a solution for \(n = pk\) gives the solution \((x^k, y^k, z^k)\) for exponent \(p\). So it suffices to treat \(n = 4\) and odd primes.

11. Show that \(2^{15} - 7\) is a square, and explain why \(2^n - 7\) cannot be a square for even \(n \ge 4\) other than \(n = 4\).

\(2^{15} - 7 = 32\,761 = 181^2\). For \(n = 2k\): \(2^{2k} - x^2 = 7\) gives \((2^k - x)(2^k + x) = 7\), so \(2^k - x = 1\) and \(2^k + x = 7\), hence \(2^{k+1} = 8\), \(k = 2\), \(n = 4\) (\(16 - 7 = 9\)).

12. The solutions of \(x^2 - 2y^2 = 1\) satisfy \((x, y) \mapsto (3x + 4y, 2x + 3y)\). Prove that this map preserves the equation, and compute the solution after \((577, 408)\).

It is multiplication by \(3 + 2\sqrt 2\), which has norm 1. Directly: \((3x + 4y)^2 - 2(2x + 3y)^2 = 9x^2 + 24xy + 16y^2 - 8x^2 - 24xy - 18y^2 = x^2 - 2y^2\). From \((577, 408)\): \((3 \cdot 577 + 4 \cdot 408, 2 \cdot 577 + 3 \cdot 408) = (3363, 2378)\).

What you learned¶

Primitive Pythagorean triples are exactly \((m^2 - n^2, 2mn, m^2 + n^2)\) with \(m > n\) coprime of opposite parity; geometrically, lines of rational slope through \((-1, 0)\) find every rational point on the circle.
Infinite descent proves impossibility by turning any solution into a smaller one; it shows \(x^4 + y^4 = z^2\) has no positive solutions, so Fermat's last theorem holds for \(n = 4\).
The solutions of Pell's equation \(x^2 - dy^2 = 1\) are the units of norm 1 in \(\mathbb{Z}[\sqrt d]\), a group \(\pm\varepsilon^k\) generated by the fundamental solution; Lagrange proved one always exists.
Congruences often prove that an equation has no solutions, but passing every congruence test is not enough.
Markov's equation has a tree of solutions found by Vieta jumping; Catalan's equation was settled in 2002; sums of three cubes still produce surprises.
Hilbert's tenth problem has a negative answer: Diophantine sets are exactly the listable sets, so no algorithm decides all Diophantine equations. Over the rationals the question is open.

Next: Chapter 10, continued fractions, which give the best fractions for any real number and solve Pell's equation in a few lines.