Contents / Number Theory / Diophantine Equations

Chapter 5

Diophantine Equations

Linear equations solvable exactly when the gcd divides the constant, with the full solution set; primitive Pythagorean triples parametrised in both directions, and again through the Gaussian integers; Pell's equation, its fundamental solution and the group structure of all solutions; the Hasse-Minkowski local-global principle and Selmer's cubic counterexample; and Fermat's Last Theorem for n=4 proved completely by infinite descent.

Introduction

A Diophantine equation is a polynomial equation with integer coefficients, asked over the integers. The restriction to integer unknowns is the whole difficulty: $x^{2} - 2 = 0$ is trivial over $R$ and unsolvable over $Z$ , and no continuity argument, no intermediate value theorem, no derivative is available to help. What replaces them is arithmetic — divisibility, congruences, factorisation in a larger ring, and the pigeonhole principle.

The subject has no single method because it has no single answer. For $a x + b y = c$ there is a complete theory: a one-line solvability criterion, a formula for every solution, an algorithm. For a quadratic in two variables the theory is still complete but much deeper, and Pell's equation $x^{2} - d y^{2} = 1$ turns out to be a statement about a unit group. For quadratic forms in any number of variables the Hasse–Minkowski theorem reduces solvability over $Q$ to a finite list of congruence conditions. Past degree two everything changes: Thue proved that a homogeneous equation of degree at least three in two variables has only finitely many solutions, Faltings proved a vast generalisation, Wiles proved Fermat's Last Theorem, and Matiyasevich proved that no algorithm can decide the general case at all.

This chapter runs that arc. Three things are proved here in full because they are completely within reach and because they are the ones worth carrying away: the classification of solutions of $a x + b y = c$ , the parametrisation of primitive Pythagorean triples (twice — once by elementary parity analysis, once by unique factorisation in $Z [i]$ ), and Fermat's Last Theorem for $n = 4$ by infinite descent. Results whose proofs need machinery far beyond this chapter — MRDP, Hasse–Minkowski, Thue, Faltings, modularity — are stated precisely and then given a proof sketch that says exactly what it is assuming. Nothing is asserted silently.

Throughout, $g cd (a, b)$ is taken non-negative, "solution" means integer solution unless stated otherwise, and familiarity with congruences and the Euclidean algorithm, as in Divisibility and the Euclidean Algorithm, is assumed.

5.1The shape of the problem

Definition 5.1 (Diophantine equation). Let $f \in Z [x_{1}, \dots, x_{n}]$ . The Diophantine equation attached to $f$ is the problem of determining

{(a_{1}, \dots, a_{n}) \in Z^{n} : f (a_{1}, \dots, a_{n}) = 0} .

The equation is solvable if this set is non-empty. Its degree is $de g f$ and its dimension is the number of unknowns $n$ .

Three questions can be asked, in increasing order of ambition: is there a solution at all; are there finitely or infinitely many; and can they all be written down. Pell's equation answers all three affirmatively; for a general $f$ , even the first has no algorithmic answer.

The cheapest tool is reduction modulo $m$ . A solution in $Z$ is in particular a solution in $Z / m Z$ , and the latter is checked by finitely many substitutions.

Proposition 5.2 (Congruence obstruction). Let $f \in Z [x_{1}, \dots, x_{n}]$ and let $m \geq 2$ . If the congruence

f (x_{1}, \dots, x_{n}) \equiv 0 (mod m)

has no solution in $(Z / m Z)^{n}$ , then $f = 0$ has no solution in $Z^{n}$ .

Proof. Reduction modulo $m$ is a ring homomorphism $π : Z \to Z / m Z$ , and a ring homomorphism commutes with the polynomial operations that build $f$ out of its variables and coefficients. Hence for any $a \in Z^{n}$ ,

π (f (a_{1}, \dots, a_{n})) = \overset{ˉ}{f} (π (a_{1}), \dots, π (a_{n})),

where $\overset{ˉ}{f}$ is $f$ with its coefficients reduced. If $f (a) = 0$ in $Z$ then the left side is $\overset{ˉ}{0}$ , so $(π (a_{1}), \dots, π (a_{n}))$ solves the congruence. Contrapositively, no solution of the congruence means no integer solution.∎

The proposition is one-directional, and the gap is the entire subject: a congruence may be solvable for every $m$ with the equation still having no integer solution, as the theorem Selmer's counterexample to the local–global principle shows. What congruences give cheaply is the negative answer, and the art is the choice of modulus — in practice $4$ or $8$ for squares, $9$ for cubes, and a prime $p$ for anything governed by $(Z / p Z)^{\times}$ .

Example 5.3 (A sum of two squares that is never $3$ modulo $4$ ). Show that $x^{2} + y^{2} = 4003$ has no integer solutions.

Solution.

Every square is $0$ or $1$ modulo $4$ : if $x = 2 k$ then $x^{2} = 4 k^{2} \equiv 0$ , and if $x = 2 k + 1$ then $x^{2} = 4 k^{2} + 4 k + 1 \equiv 1$ .
So $x^{2} + y^{2} (mod 4)$ lies in ${0 + 0, 0 + 1, 1 + 0, 1 + 1} = {0, 1, 2}$ , and never equals $3$ .
But $4003 = 4 \cdot 1000 + 3 \equiv 3 (mod 4)$ .
By the proposition Congruence obstruction there is no solution. Note how little was used: nothing about $4003$ except its residue.

□

Exercises for §5.1 →

5.2Hilbert's tenth problem

In 1900 Hilbert asked, as the tenth of his twenty-three problems, for "a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers". The answer, completed by Matiyasevich in 1970 on the basis of work of Davis, Putnam and Robinson, is that no such process exists. The mechanism is that Diophantine equations are expressive enough to encode computation itself.

Definition 5.4 (Diophantine set). A set $S \subseteq Z_{\geq 0}^{k}$ is Diophantine if there is a polynomial $f \in Z [t_{1}, \dots, t_{k}, x_{1}, \dots, x_{n}]$ such that

(t_{1}, \dots, t_{k}) \in S ⟺ \exists x_{1}, \dots, x_{n} \in Z_{\geq 0} : f (t_{1}, \dots, t_{k}, x_{1}, \dots, x_{n}) = 0.

The variables $t_{i}$ are parameters and the $x_{j}$ are unknowns.

Many familiar sets are Diophantine, by elementary encodings. Non-negativity is Diophantine inside $Z$ by Lagrange's four-square theorem, $t \geq 0 ⟺ \exists a, b, c, d : t = a^{2} + b^{2} + c^{2} + d^{2}$ ; divisibility is, since $a ∣ b ⟺ \exists x : b = a x$ ; coprimality is, by Bézout; compositeness is, since $n = (u + 2) (v + 2)$ . Logical operations come free: $f = 0 \land g = 0$ is the single equation $f^{2} + g^{2} = 0$ , and $f = 0 \lor g = 0$ is $f g = 0$ . What is not obvious — and is the content of the theorem — is that exponentiation, and through it the step relation of a Turing machine, is captured this way.

Theorem 5.5 (MRDP: Diophantine equals recursively enumerable, and Hilbert's tenth problem is unsolvable). A set $S \subseteq Z_{\geq 0}^{k}$ is Diophantine if and only if it is recursively enumerable. Consequently there is no algorithm which, given $f \in Z [x_{1}, \dots, x_{n}]$ , decides whether $f = 0$ has a solution in integers.

Proof. Proof sketch — assumes the theory of computability and Matiyasevich's theorem on the exponential; the hard direction is not proved here.

( $\Rightarrow$ ) Easy and complete. Given a Diophantine definition of $S$ , enumerate all tuples $(t, x) \in Z_{\geq 0}^{k + n}$ in some computable order, evaluate $f$ , and output $t$ whenever $f (t, x) = 0$ . This enumerates exactly $S$ , so $S$ is recursively enumerable.

( $\Leftarrow$ ) The deep direction. Davis, Putnam and Robinson showed that every recursively enumerable set has an exponential Diophantine definition, one allowing terms $a^{b}$ with $b$ a variable, by encoding a machine's computation history as one large number and extracting its digits by the Chinese remainder theorem. What remained was Robinson's hypothesis, that ${(a, b, c) : c = a^{b}}$ is itself Diophantine; Matiyasevich proved it using the Pell-type equation $x^{2} - (a^{2} - 1) y^{2} = 1$ , whose solutions grow exponentially and can be pinned down by congruences.

The consequence. Let $H$ be the halting set, recursively enumerable but not recursive. By the equivalence there is $f$ with $t \in H$ iff $f (t, x) = 0$ is solvable in non-negative integers. An algorithm deciding solvability of arbitrary Diophantine equations, applied to $f (t, x) = 0$ for each fixed $t$ , would decide membership in $H$ — contradiction. Passing from non-negative to arbitrary integer unknowns costs only the substitution $x_{j} = a_{j}^{2} + b_{j}^{2} + c_{j}^{2} + d_{j}^{2}$ .∎

Remark. The undecidability is not an artefact of allowing many variables or huge degree: nine unknowns suffice over $Z_{\geq 0}$ , and degree $4$ suffices at the cost of more variables. It does depend on the ring: the analogous question over $Q$ is open, and over $R$ or $C$ it is decidable by Tarski's quantifier elimination.

Exercises for §5.2 →

5.3Finiteness: how many solutions can there be

Before asking for solutions it is worth asking how many to expect, and the answer is governed by geometry. A plane curve $f (x, y) = 0$ has a genus, an integer $g \geq 0$ measuring how far it is from being parametrisable by rational functions. Lines and conics have genus $0$ ; a smooth plane cubic has genus $1$ ; a smooth plane curve of degree $d$ has genus $(d - 1) (d - 2) /2$ . The number of integer or rational points is controlled by $g$ with remarkable precision.

Theorem 5.6 (Siegel and Faltings). Let $C : f (x, y) = 0$ be an irreducible curve over $Q$ of genus $g$ .

(Siegel, 1929.) If $g \geq 1$ , then $C$ has only finitely many integer points. The same holds for $g = 0$ if the curve has at least three points at infinity.
(Faltings, 1983; Mordell's conjecture.) If $g \geq 2$ , then $C$ has only finitely many rational points.

Proof. Proof sketch — assumes Diophantine approximation on abelian varieties (Siegel) and the theory of heights on moduli spaces (Faltings); neither argument is reproduced here.

For (1): Siegel embeds the curve in its Jacobian. An infinite sequence of integer points must escape to infinity, and pulling back along multiplication-by- $m$ on the Jacobian produces from it algebraic numbers approximated by rationals far better than the theorem Thue's approximation theorem, and Thue–Siegel–Roth permits.

For (2): Faltings deduced Mordell's conjecture from the Shafarevich conjecture on abelian varieties with good reduction outside a finite set of primes, itself obtained from the Tate conjecture by a height-descent argument on a moduli space. Vojta later reproved it directly in the language of Diophantine approximation.

Both results are ineffective: they bound the number of solutions but give no computable bound on their size, so neither can certify that a list of found solutions is complete.∎

Genus $0$ is where infinitude is the rule: a conic with one rational point has infinitely many, cut out by the pencil of rational lines through it, which is exactly the mechanism behind the theorem Parametrisation of primitive Pythagorean triples. Genus $1$ is the delicate middle — infinitely many rational points are possible while integer points are always finite. Genus $\geq 2$ is rigid, and $x^{n} + y^{n} = 1$ has genus $\geq 3$ for $n \geq 4$ , so Faltings already gives finiteness for Fermat's equation at each fixed $n$ — which nevertheless falls short of the theorem Fermat's Last Theorem, because "finitely many" is not "none".

Exercises for §5.3 →

5.4Linear equations: when is $a x + b y = c$ solvable

The linear case is the one place where the theory is complete, algorithmic, and short. Everything rests on a single structural fact about $Z$ : the set of integer combinations of $a$ and $b$ is not merely closed under addition, it is the set of multiples of one number.

Theorem 5.7 (Bézout's identity). Let $a, b \in Z$ , not both zero, and put $d = g cd (a, b)$ . Then

{a x + b y : x, y \in Z} = d Z,

and in particular there exist $u, v \in Z$ with $a u + b v = d$ .

Proof. Let $I = {a x + b y : x, y \in Z}$ . It is closed under addition and under multiplication by any integer, and it contains a positive element (one of $\pm a, \pm b$ is positive since not both are zero). Let $e$ be the least positive element of $I$ , say $e = a u + b v$ .

Every element of $I$ is a multiple of $e$ . Take $n = a x + b y \in I$ and divide: $n = q e + r$ with $0 \leq r < e$ . Then

r = n - q e = a (x - q u) + b (y - q v) \in I .

If $r > 0$ this contradicts minimality of $e$ , so $r = 0$ and $e ∣ n$ . Since $a, b \in I$ we get $e ∣ a$ and $e ∣ b$ , so $e$ is a common divisor and $e \leq d$ .

Conversely $d ∣ e$ . As $d ∣ a$ and $d ∣ b$ , $d$ divides $a u + b v = e$ , hence $d \leq e$ because $e > 0$ .

Therefore $e = d$ , and $I = e Z = d Z$ . The element $e = a u + b v$ furnishes the identity.∎

The proof never factors and never mentions primes. It uses only that a non-empty set of positive integers has a least element and that division with remainder exists — which is why the same argument gives Bézout identities in $F [x]$ and $Z [i]$ , as developed in Polynomial Rings and Unique Factorization.

Theorem 5.8 (Solvability criterion for $a x + b y = c$ ). Let $a, b, c \in Z$ with $a, b$ not both zero, and $d = g cd (a, b)$ . The equation

a x + b y = c

has an integer solution if and only if $d ∣ c$ .

Proof. ( $\Rightarrow$ ) If $a x_{0} + b y_{0} = c$ then, since $d ∣ a$ and $d ∣ b$ , $d$ divides $a x_{0} + b y_{0} = c$ .

( $\Leftarrow$ ) Suppose $c = d k$ . By the theorem Bézout's identity choose $u, v$ with $a u + b v = d$ . Multiplying by $k$ ,

a (u k) + b (v k) = d k = c,

so $(x_{0}, y_{0}) = (u k, v k)$ is a solution.

Equivalently and more briefly: the set of representable $c$ is exactly ${a x + b y} = d Z$ by the theorem Bézout's identity, and $c \in d Z$ says $d ∣ c$ .∎

Figure 5.9. The integer points of

6 x + 15 y = 9

are the lattice points on the line, spaced by the vector

(15/3, - 6/3) = (5, - 2)

. The parallel line

6 x + 15 y = 8

misses every lattice point, because

3 ∤ 8

Example 5.10 (Two nearly identical equations). Decide whether $6 x + 15 y = 8$ and $6 x + 15 y = 9$ are solvable, and solve the one that is.

Solution.

$g cd (6, 15) = 3$ .
$3 ∤ 8$ , so by the theorem Solvability criterion for $a x + b y = c$ the first equation has no integer solution. (Directly: the left side is always a multiple of $3$ .)
$3 ∣ 9$ , so the second is solvable. Bézout for $(6, 15)$ : $6 \cdot 3 + 15 \cdot (- 1) = 3$ .
Multiply by $9/3 = 3$ : $6 \cdot 9 + 15 \cdot (- 3) = 9$ , so $(x, y) = (9, - 3)$ .
Check: $54 - 45 = 9$ . ✓

□

Exercises for §5.4 →

5.5The complete solution set

Because the equation is linear its solution set is a coset: one particular solution plus every solution of the homogeneous equation, and the homogeneous equation is easy to solve outright.

Theorem 5.11 (All solutions of a linear Diophantine equation). Let $d = g cd (a, b)$ with $a, b \neq = 0$ , suppose $d ∣ c$ , and let $(x_{0}, y_{0})$ be any one solution of $a x + b y = c$ . Then the complete solution set is

{(x_{0} + \frac{b}{d} t, y_{0} - \frac{a}{d} t) : t \in Z},

and distinct $t$ give distinct solutions.

Proof. These are solutions. For any $t$ ,

a (x_{0} + \frac{b}{d} t) + b (y_{0} - \frac{a}{d} t) = a x_{0} + b y_{0} + \frac{ab}{d} t - \frac{ab}{d} t = c .

Note $b / d$ and $a / d$ are integers, so these are integer points.

Every solution has this form. Let $(x, y)$ be any solution. Subtracting $a x_{0} + b y_{0} = c$ from $a x + b y = c$ gives

a (x - x_{0}) = - b (y - y_{0}) .

Write $a = d a^{'}$ , $b = d b^{'}$ with $g cd (a^{'}, b^{'}) = 1$ — this is where the gcd is divided out, and it is the only step that needs an idea. Cancelling $d$ ,

a^{'} (x - x_{0}) = - b^{'} (y - y_{0}) .

Thus $b^{'} ∣ a^{'} (x - x_{0})$ , and since $g cd (a^{'}, b^{'}) = 1$ , Euclid's lemma gives $b^{'} ∣ (x - x_{0})$ . Write $x - x_{0} = b^{'} t$ for some $t \in Z$ . Substituting, $a^{'} b^{'} t = - b^{'} (y - y_{0})$ , and $b^{'} \neq = 0$ cancels to $y - y_{0} = - a^{'} t$ . Hence

x = x_{0} + \frac{b}{d} t, y = y_{0} - \frac{a}{d} t,

as claimed.

Distinctness. If $t \neq = s$ gave the same point then $\frac{b}{d} (t - s) = 0$ , impossible since $b \neq = 0$ .∎

Geometrically, the integer points on $a x + b y = c$ form a one-dimensional lattice with step vector $(b / d, - a / d)$ — the primitive integer direction of the line — which is what the figure The integer points of $6 x + 15 y = 9$ … draws. The step is not $(b, - a)$ : dividing out $d$ is exactly what makes the vector primitive, and a non-primitive step skips solutions.

Method 5.12 (Solving $a x + b y = c$ completely).

Compute $d = g cd (a, b)$ by the Euclidean algorithm, keeping the quotients.
If $d ∤ c$ , stop: there is no solution.
Back-substitute through the algorithm to get $u, v$ with $a u + b v = d$ .
Scale: $(x_{0}, y_{0}) = (u \cdot c / d, v \cdot c / d)$ is a particular solution.
Write the general solution $x = x_{0} + (b / d) t$ , $y = y_{0} - (a / d) t$ .
If a constraint such as $x, y \geq 0$ is imposed, translate it into an inequality on $t$ and count the integers in the resulting interval.

Example 5.13 (Every solution, and the ones in a box). Find all integer solutions of $34 x + 55 y = 1$ , and then all with $∣ x ∣ \leq 100$ .

Solution.

$g cd (34, 55) = 1$ (consecutive Fibonacci numbers), so it is solvable.
The extended algorithm gives $34 \cdot (- 21) + 55 \cdot 13 = - 714 + 715 = 1$ , so $(x_{0}, y_{0}) = (- 21, 13)$ .
General solution: $x = - 21 + 55 t$ , $y = 13 - 34 t$ , $t \in Z$ .
$∣ x ∣ \leq 100$ means $- 100 \leq - 21 + 55 t \leq 100$ , i.e. $- 79/55 \leq t \leq 121/55$ , i.e. $- 1.436 \leq t \leq 2.2$ , so $t \in {- 1, 0, 1, 2}$ .
Those give $(- 76, 47), (- 21, 13), (34, - 21), (89, - 55)$ — four solutions. ✓

□

Example 5.14 (Counting non-negative solutions). How many solutions of $7 x + 11 y = 1000$ have $x \geq 0$ and $y \geq 0$ ?

Solution.

$g cd (7, 11) = 1 ∣ 1000$ , so solutions exist. Bézout: $7 \cdot (- 3) + 11 \cdot 2 = 1$ , so $(x_{0}, y_{0}) = (- 3000, 2000)$ .
General solution: $x = - 3000 + 11 t$ , $y = 2000 - 7 t$ .
$x \geq 0$ gives $t \geq 3000/11 = 272.72 \dots$ , so $t \geq 273$ .
$y \geq 0$ gives $t \leq 2000/7 = 285.71 \dots$ , so $t \leq 285$ .
The count is $285 - 273 + 1 = 13$ .
Sanity check at the endpoints: $t = 273$ gives $(3, 89)$ and $7 \cdot 3 + 11 \cdot 89 = 21 + 979 = 1000$ ✓; $t = 285$ gives $(135, 5)$ and $945 + 55 = 1000$ ✓.

□

Remark. In general the number of non-negative solutions of $a x + b y = N$ with $g cd (a, b) = 1$ is $⌊ N / (ab)⌋$ or $⌊ N / (ab)⌋ + 1$ , since the admissible range of $t$ has length exactly $N / (ab)$ . Above, $1000/77 = 12.98 \dots$ and the count was $13$ .

Exercises for §5.5 →

5.6Frobenius: what cannot be represented

If $a, b$ are coprime positive integers then $a x + b y = N$ is solvable in integers for every $N$ . Restricting to $x, y \geq 0$ — buying $N$ nuggets in boxes of $a$ and $b$ — changes the answer completely, and the failures stop after a computable point.

Theorem 5.15 (Frobenius number of two coprime denominations). Let $a, b \geq 2$ be coprime integers. Call $N \geq 0$ representable if $N = a x + b y$ for some integers $x, y \geq 0$ . Then:

$ab - a - b$ is not representable;
every integer $N > ab - a - b$ is representable;
exactly $(a - 1) (b - 1) /2$ non-negative integers are not representable.

Proof. Since $g cd (a, b) = 1$ , every $N$ has integer solutions, and by the theorem All solutions of a linear Diophantine equation they are $x = x_{0} + b t$ , $y = y_{0} - a t$ . Exactly one of them has $0 \leq x \leq b - 1$ ; call it $(x_{N}, y_{N})$ . Then

N is representable ⟺ y_{N} \geq 0. (*)

If $y_{N} \geq 0$ we have a non-negative representation; conversely any representation with $x \geq 0$ has $x \geq x_{N}$ , since $x \equiv x_{N} mod b$ and $x_{N}$ is least non-negative, so $y \leq y_{N}$ and $y \geq 0$ forces $y_{N} \geq 0$ .

(1) Suppose $ab - a - b = a x + b y$ with $x, y \geq 0$ . Reduce mod $a$ : $- b \equiv b y (mod a)$ , so $b (y + 1) \equiv 0 (mod a)$ , and $g cd (a, b) = 1$ gives $a ∣ y + 1$ . Since $y \geq 0$ , $y + 1 \geq 1$ , so $y + 1 \geq a$ , i.e. $y \geq a - 1$ . Symmetrically $x \geq b - 1$ . But then

a x + b y \geq a (b - 1) + b (a - 1) = 2 ab - a - b > ab - a - b,

since $ab > 0$ . Contradiction.

(2) Let $N > ab - a - b$ and take the representative with $0 \leq x_{N} \leq b - 1$ . Then

b y_{N} = N - a x_{N} > (ab - a - b) - a (b - 1) = - b,

so $y_{N} > - 1$ , and being an integer, $y_{N} \geq 0$ . By $(*)$ , $N$ is representable.

(3) Let $F = ab - a - b$ . By (2) every non-representable $N$ lies in $[0, F]$ , a set of $F + 1 = (a - 1) (b - 1)$ integers, an even count since $a, b$ are not both even. We show the involution $N \mapsto F - N$ of $[0, F]$ swaps representable with non-representable; exactly half the range is then non-representable, giving $(a - 1) (b - 1) /2$ .

If both $N$ and $F - N$ were representable, adding the two representations would represent $ab - a - b$ , contradicting (1). So at most one of $N, F - N$ is representable.

Conversely suppose $N$ is not representable, $0 \leq N \leq F$ , with representative $(x_{N}, y_{N})$ , $0 \leq x_{N} \leq b - 1$ ; by $(*)$ , $y_{N} \leq - 1$ . Then

F - N = ab - a - b - a x_{N} - b y_{N} = a (b - 1 - x_{N}) + b (- 1 - y_{N}),

and both coefficients are $\geq 0$ . So $F - N$ is representable. The involution therefore swaps the two classes exactly, completing the count.∎

Intuition. Picture the non-negative multiples of $a$ arranged in $b$ columns according to their residue mod $b$ . Each residue class mod $b$ first becomes reachable at some multiple of $a$ , and after that it is reachable forever, since one may keep adding $b$ . The Frobenius number is the largest of those $b$ thresholds, minus $b$ — the last gap before all $b$ columns have switched on.

Example 5.16 (Chicken nuggets in boxes of $6$ and $11$ ). With coprime box sizes $6$ and $11$ , what is the largest unattainable order, and how many orders are unattainable?

Solution.

$g cd (6, 11) = 1$ , so the theorem Frobenius number of two coprime denominations applies.
Largest unattainable: $6 \cdot 11 - 6 - 11 = 66 - 17 = 49$ .
Count unattainable: $(6 - 1) (11 - 1) /2 = 50/2 = 25$ .
Check $49$ directly: $49 - 11 y$ for $y = 0, 1, 2, 3, 4$ is $49, 38, 27, 16, 5$ , none divisible by $6$ . ✓ And $50 = 6 \cdot 4 + 11 \cdot 2 = 24 + 22$ ✓, $51 = 6 \cdot 5 + 11 \cdot 2$ ? $30 + 22 = 52$ no — try $51 = 11 \cdot 3 + 6 \cdot 3 = 33 + 18$ ✓.

□

Exercises for §5.6 →

5.7Pythagorean triples: the objects

Definition 5.17 (Pythagorean triple). A Pythagorean triple is a triple $(x, y, z)$ of positive integers with

x^{2} + y^{2} = z^{2} .

It is primitive if $g cd (x, y, z) = 1$ .

Every triple is a multiple of a primitive one: if $g = g cd (x, y, z)$ then dividing the equation by $g^{2}$ shows $(x / g, y / g, z / g)$ is a primitive triple, and conversely $k$ times a primitive triple is a triple. So the classification problem is exactly the primitive one.

Lemma 5.18 (Coprimality and parity in a primitive triple). Let $(x, y, z)$ be a primitive Pythagorean triple. Then $x, y, z$ are pairwise coprime, exactly one of $x, y$ is even, and $z$ is odd.

Proof. Pairwise coprime. Suppose a prime $p$ divides two of them. If $p ∣ x$ and $p ∣ y$ then $p^{2} ∣ x^{2} + y^{2} = z^{2}$ , so $p ∣ z$ , contradicting primitivity. If $p ∣ x$ and $p ∣ z$ then $p^{2} ∣ z^{2} - x^{2} = y^{2}$ , so $p ∣ y$ , again a contradiction. The case $p ∣ y, p ∣ z$ is symmetric.

Not both odd. By pairwise coprimality $x, y$ are not both even. Suppose both are odd. Every odd square is $1 mod 4$ , since $(2 k + 1)^{2} = 4 k (k + 1) + 1$ . Then $z^{2} = x^{2} + y^{2} \equiv 1 + 1 = 2 (mod 4)$ . But a square is $0$ or $1$ mod $4$ , never $2$ . Contradiction.

Hence exactly one of $x, y$ is even, and then $z^{2} = x^{2} + y^{2}$ is odd $+$ even $=$ odd, so $z$ is odd.∎

Notation. Having shown exactly one leg is even, we fix the convention throughout: in a primitive triple $(x, y, z)$ the entry $x$ is odd and $y$ is even. Every primitive triple can be written this way after swapping the legs, and the swap is the only ambiguity.

Example 5.19 (Sorting triples with hypotenuse $25$ ). Find all Pythagorean triples with $z = 25$ and say which are primitive.

Solution.

Need $x^{2} + y^{2} = 625$ with $x, y \geq 1$ . Testing $x = 7$ : $625 - 49 = 576 = 2 4^{2}$ ✓. $x = 15$ : $625 - 225 = 400 = 2 0^{2}$ ✓. $x = 20, 24$ repeat these with legs swapped.
So the triples are $(7, 24, 25)$ and $(15, 20, 25)$ , up to order.
$g cd (7, 24, 25) = 1$ : primitive. $g cd (15, 20, 25) = 5$ : not primitive — it is $5 \cdot (3, 4, 5)$ .
Consistency with the lemma Coprimality and parity in a primitive triple: in $(7, 24, 25)$ one leg is odd, one even, $z$ odd ✓. In $(15, 20, 25)$ the entries are not pairwise coprime, as the lemma predicts for a non-primitive triple.

□

Exercises for §5.7 →

5.8The parametrisation theorem

Generating triples is easy; proving that a formula catches all of them is the real content. The engine is a divisibility principle about squares, used again below for Fermat.

Lemma 5.20 (Coprime factors of a square are squares). Let $u, v, w$ be positive integers with $uv = w^{2}$ and $g cd (u, v) = 1$ . Then $u$ and $v$ are each perfect squares.

Proof. Let $p$ be a prime and let $α, β, γ$ be the exponents of $p$ in $u, v, w$ . Unique factorisation gives $α + β = 2 γ$ . Coprimality gives $min (α, β) = 0$ , so one of $α, β$ is $0$ and the other equals $2 γ$ , which is even. Hence every prime occurs to an even power in $u$ , and likewise in $v$ ; a positive integer all of whose prime exponents are even is a square, namely $\prod p^{α_{p} /2}$ squared.∎

Theorem 5.21 (Parametrisation of primitive Pythagorean triples). The primitive Pythagorean triples with $x$ odd and $y$ even are exactly

x = m^{2} - n^{2}, y = 2 mn, z = m^{2} + n^{2},

where $m > n \geq 1$ are integers with $g cd (m, n) = 1$ and $m \neq \equiv n (mod 2)$ . Moreover distinct such pairs $(m, n)$ give distinct triples.

Proof. Every such $(m, n)$ gives a primitive triple. First,

(m^{2} - n^{2})^{2} + (2 mn)^{2} = m^{4} - 2 m^{2} n^{2} + n^{4} + 4 m^{2} n^{2} = m^{4} + 2 m^{2} n^{2} + n^{4} = (m^{2} + n^{2})^{2},

so the triple satisfies the equation, and $m > n \geq 1$ makes all three entries positive. Since $m, n$ have opposite parity, $m^{2} - n^{2}$ and $m^{2} + n^{2}$ are odd and $2 mn$ is even, so the parity convention holds. For primitivity, suppose an odd prime $p$ divides $x = m^{2} - n^{2}$ and $z = m^{2} + n^{2}$ . Then $p$ divides their sum $2 m^{2}$ and difference $2 n^{2}$ , and $p$ being odd gives $p ∣ m^{2}$ and $p ∣ n^{2}$ , so $p ∣ m$ and $p ∣ n$ , contradicting $g cd (m, n) = 1$ . The prime $2$ cannot divide $z$ , which is odd. So $g cd (x, z) = 1$ and a fortiori $g cd (x, y, z) = 1$ .

Every primitive triple arises this way. This is the substantial half. Let $(x, y, z)$ be primitive with $x$ odd, $y$ even, as allowed by the lemma Coprimality and parity in a primitive triple; then $z$ is odd. Rewrite the equation as

y^{2} = z^{2} - x^{2} = (z - x) (z + x) .

Both $z - x$ and $z + x$ are even, being differences and sums of two odd numbers, so write $z - x = 2 s$ , $z + x = 2 r$ with $r, s$ positive integers ( $z > x$ because $y \geq 1$ ). Also $y = 2 q$ with $q$ a positive integer. Substituting and dividing by $4$ ,

q^{2} = rs .

Claim: $g cd (r, s) = 1$ . A common divisor $e$ of $r$ and $s$ divides $r + s = z$ and $r - s = x$ . But $g cd (x, z) = 1$ by the lemma, so $e = 1$ .

By the lemma Coprime factors of a square are squares applied to $rs = q^{2}$ , there are positive integers $m, n$ with

r = m^{2}, s = n^{2} .

Now unwind:

z = r + s = m^{2} + n^{2}, x = r - s = m^{2} - n^{2}, y^{2} = 4 rs = 4 m^{2} n^{2} \Rightarrow y = 2 mn,

taking positive square roots. Finally $m > n \geq 1$ because $x = m^{2} - n^{2} > 0$ and $s = n^{2} \geq 1$ ; $g cd (m, n) = 1$ because a common prime divisor of $m$ and $n$ would divide $r$ and $s$ ; and $m \neq \equiv n (mod 2)$ because $z = m^{2} + n^{2}$ is odd, which forces exactly one of $m^{2}, n^{2}$ to be odd.

Distinctness. From the triple one recovers $m^{2} = (z + x) /2$ and $n^{2} = (z - x) /2$ , so $(m, n)$ is determined by $(x, y, z)$ among positive pairs. Hence the correspondence is a bijection.∎

The proof is a template: rearrange into "a square equals a product of coprime factors", apply the lemma Coprime factors of a square are squares to conclude each factor is a square, substitute. The same three steps, applied twice in succession, drive the descent in the theorem No solutions to $x^{4} + y^{4} = z^{2}$ .

Figure 5.22. Primitive triples

(m^{2} - n^{2}, 2 mn)

for coprime

m > n

of opposite parity, plotted as points

(x, y)

; the imprimitive multiples of

(3, 4, 5)

lie along the ray through

(3, 4)

Example 5.23 (Generating a triple from $(m, n)$ ). Compute the primitive triple attached to $m = 7$ , $n = 4$ , and check the hypotheses.

Solution.

$g cd (7, 4) = 1$ ✓, $7$ odd and $4$ even so opposite parity ✓, $7 > 4 \geq 1$ ✓.
$x = 49 - 16 = 33$ , $y = 2 \cdot 7 \cdot 4 = 56$ , $z = 49 + 16 = 65$ .
Check: $3 3^{2} + 5 6^{2} = 1089 + 3136 = 4225 = 6 5^{2}$ ✓.
Primitive: $g cd (33, 56) = 1$ since $33 = 3 \cdot 11$ and $56 = 2^{3} \cdot 7$ . ✓

□

Exercises for §5.8 →

5.9The same theorem from $Z [i]$

The parity juggling above looks like a trick. It is not: it is the shadow of a factorisation. Over $Z$ the form $x^{2} + y^{2}$ is irreducible, but over the Gaussian integers $Z [i] = {a + bi : a, b \in Z}$ it splits as $(x + i y) (x - i y)$ , and $Z [i]$ has unique factorisation. The equation then reads "a product of two coprime Gaussian integers is a square".

Recall from Polynomial Rings and Unique Factorization that $Z [i]$ is Euclidean for the norm $N (a + bi) = a^{2} + b^{2}$ , hence a UFD; that $N$ is multiplicative; and that $α$ is a unit iff $N (α) = 1$ , so $Z [i]^{\times} = {1, - 1, i, - i}$ .

Theorem 5.24 (Gaussian derivation of the Pythagorean parametrisation). Let $(x, y, z)$ be a primitive Pythagorean triple with $x$ odd and $y$ even. Then in $Z [i]$ there are coprime integers $m > n \geq 1$ of opposite parity and a unit $ε$ with

x + i y = ε (m + ni)^{2},

and expanding this identity reproduces $x = m^{2} - n^{2}$ , $y = 2 mn$ , $z = m^{2} + n^{2}$ .

Proof. Set $α = x + i y$ and $\overset{α}{ˉ} = x - i y$ . Then

α \overset{α}{ˉ} = x^{2} + y^{2} = z^{2} .

Step 1: $α$ and $\overset{α}{ˉ}$ are coprime in $Z [i]$ . Let $δ$ be a common divisor. Then $δ$ divides $α + \overset{α}{ˉ} = 2 x$ and $α - \overset{α}{ˉ} = 2 i y$ , hence divides $g cd (2 x, 2 i y)$ ; since $g cd (x, y) = 1$ in $Z$ by the lemma Coprimality and parity in a primitive triple, and $i$ is a unit, $δ ∣ 2$ . Now $2 = - i (1 + i)^{2}$ , so the only Gaussian primes dividing $2$ are associates of $1 + i$ , of norm $2$ . If $(1 + i) ∣ α$ then $2 = N (1 + i)$ divides $N (α) = z^{2}$ , forcing $z$ even — but $z$ is odd. So $δ$ is a unit.

Step 2: a square splits into squares. In the UFD $Z [i]$ , write $z^{2} = α \overset{α}{ˉ}$ and compare factorisations. Every Gaussian prime $π$ occurs in $z^{2}$ to an even exponent. Because $α$ and $\overset{α}{ˉ}$ share no prime, all of that exponent sits in one of the two factors. Hence every prime occurs to an even exponent in $α$ , and therefore

α = ε β^{2} for some β \in Z [i] and unit ε .

(The unit appears because a UFD determines factorisations only up to units.)

Step 3: absorb the unit. The squares of units are ${1, - 1}$ , since $(\pm 1)^{2} = 1$ and $(\pm i)^{2} = - 1$ ; so modulo squares of units only $ε \in {1, i}$ need be considered, the cases $ε = - 1$ and $ε = - i$ being absorbed into $β$ by replacing $β$ with $i β$ . Write $β = m + ni$ . If $ε = i$ then

α = i (m + ni)^{2} = - 2 mn + (m^{2} - n^{2}) i

has even real part, contradicting $x$ odd. Hence $ε = 1$ , and replacing $(m, n)$ by $(- m, - n)$ if necessary we may take $m > 0$ .

Step 4: expand.

x + i y = (m + ni)^{2} = (m^{2} - n^{2}) + 2 mn i,

so $x = m^{2} - n^{2}$ and $y = 2 mn$ , whence $z^{2} = N (α) = N (β)^{2} = (m^{2} + n^{2})^{2}$ and $z = m^{2} + n^{2}$ as $z > 0$ . Finally $g cd (m, n) = 1$ (a common factor would divide $α$ and contradict Step 1 via $N$ ), $m > n \geq 1$ since $x > 0$ and $y > 0$ , and $m \neq \equiv n (mod 2)$ since $x$ is odd.∎

Remark. Compare the two proofs. The elementary one factored $y^{2} = (z - x) (z + x)$ over $Z$ , with the parity analysis doing all the work of proving the factors coprime. The Gaussian one factored $z^{2} = (x + i y) (x - i y)$ over $Z [i]$ , needed the same coprimality statement, and then got the parametrisation for free as $(m + ni)^{2}$ . The lesson generalises — and so does its limit: Kummer's discovery that $Z [ζ_{p}]$ can fail to be a UFD is exactly why the naive factorisation proof of Fermat's Last Theorem collapses.

Example 5.25 (Factoring a Gaussian integer to read off a triple). Factor $α = 3 + 4 i$ in $Z [i]$ and identify the Pythagorean triple.

Solution.

$N (3 + 4 i) = 9 + 16 = 25 = 5^{2}$ , so the factors have norms multiplying to $25$ .
$5 = (2 + i) (2 - i)$ with $N (2 \pm i) = 5$ , and these are non-associate Gaussian primes.
Try $(2 + i)^{2} = 4 + 4 i + i^{2} = 3 + 4 i$ ✓. So $α = (2 + i)^{2}$ exactly, with $ε = 1$ , $m = 2$ , $n = 1$ .
The theorem then reads off $x = 4 - 1 = 3$ , $y = 2 \cdot 2 \cdot 1 = 4$ , $z = 4 + 1 = 5$ : the triple $(3, 4, 5)$ .

□

Exercises for §5.9 →

5.10Pell's equation

Definition 5.26 (Pell's equation). Let $d$ be a positive integer. Pell's equation for $d$ is

x^{2} - d y^{2} = 1, x, y \in Z .

The solutions $(\pm 1, 0)$ are trivial; any other is nontrivial. A nontrivial solution with $x, y > 0$ and $x$ minimal is called the fundamental solution.

The name is a historical accident — Euler attributed to Pell an equation solved by Brouncker and studied centuries earlier by Brahmagupta — but the equation is central: it is the multiplicative structure hiding in a quadratic form, it powers Matiyasevich's proof of the theorem MRDP, and it computes the unit group of a real quadratic order.

Proposition 5.27 (Square $d$ collapses the equation). If $d = k^{2}$ is a perfect square, then $x^{2} - d y^{2} = 1$ has only the trivial solutions.

Proof. The equation factors over $Z$ :

1 = x^{2} - k^{2} y^{2} = (x - k y) (x + k y) .

Two integers multiplying to $1$ are both $1$ or both $- 1$ . In the first case $x - k y = x + k y = 1$ gives $2 k y = 0$ ; in the second, $x = - 1$ and again $k y = 0$ . Since $d > 0$ we have $k \neq = 0$ , so $y = 0$ and $x = \pm 1$ .∎

So the interesting case is $d$ not a perfect square, which is assumed from here on. Then $d$ is irrational and $x^{2} - d y^{2}$ does not factor over $Z$ — it factors over $Z [d]$ , and that is the whole point. The following identity, due to Brahmagupta in the seventh century and usually called Brahmagupta's composition law, is the statement that the solution set is closed under a multiplication.

Proposition 5.28 (Brahmagupta composition). If $x_{1}^{2} - d y_{1}^{2} = 1$ and $x_{2}^{2} - d y_{2}^{2} = 1$ , then

(x_{1} x_{2} + d y_{1} y_{2})^{2} - d (x_{1} y_{2} + x_{2} y_{1})^{2} = 1.

Equivalently, $(x_{1} + y_{1} d) (x_{2} + y_{2} d) = (x_{1} x_{2} + d y_{1} y_{2}) + (x_{1} y_{2} + x_{2} y_{1}) d$ is again a solution.

Proof. Expand both sides. Writing $X = x_{1} x_{2} + d y_{1} y_{2}$ and $Y = x_{1} y_{2} + x_{2} y_{1}$ ,

X^{2} - d Y^{2} = x_{1}^{2} x_{2}^{2} + 2 d x_{1} x_{2} y_{1} y_{2} + d^{2} y_{1}^{2} y_{2}^{2} - d (x_{1}^{2} y_{2}^{2} + 2 x_{1} x_{2} y_{1} y_{2} + x_{2}^{2} y_{1}^{2}) .

The cross terms $2 d x_{1} x_{2} y_{1} y_{2}$ cancel, leaving

X^{2} - d Y^{2} = x_{1}^{2} x_{2}^{2} + d^{2} y_{1}^{2} y_{2}^{2} - d x_{1}^{2} y_{2}^{2} - d x_{2}^{2} y_{1}^{2} = (x_{1}^{2} - d y_{1}^{2}) (x_{2}^{2} - d y_{2}^{2}) = 1 \cdot 1 = 1.

The factorisation in the last step is just $(A - B) (C - D)$ regrouped; it is the multiplicativity of the norm $N (x + y d) = x^{2} - d y^{2}$ on $Z [d]$ , which is the conceptual reason the identity exists at all.∎

Exercises for §5.10 →

5.11Existence: continued fractions and the pigeonhole

Composition manufactures infinitely many solutions from one, but only if one exists. That is the hard part, and it is genuinely a theorem: for $d = 61$ the fundamental solution is $x = 1766319049$ , $y = 226153980$ , so no search that stops early will find it. The proof below is complete and rests on nothing beyond the pigeonhole principle.

Lemma 5.29 (Dirichlet's approximation theorem). Let $θ$ be irrational. Then there are infinitely many pairs of integers $(p, q)$ with $q \geq 1$ and

θ - \frac{p}{q} < \frac{1}{q ^{2}}, equivalently ∣ qθ - p ∣ < \frac{1}{q} .

Proof. Fix $Q \geq 1$ . Consider the $Q + 1$ numbers ${qθ}$ for $q = 0, 1, \dots, Q$ , where ${\cdot}$ is the fractional part, all lying in $[0, 1)$ . Partition $[0, 1)$ into the $Q$ intervals $[\frac{j}{Q}, \frac{j + 1}{Q})$ , $j = 0, \dots, Q - 1$ . By the pigeonhole principle two of the $Q + 1$ numbers lie in the same interval, say ${q_{1} θ}$ and ${q_{2} θ}$ with $q_{1} < q_{2}$ . Put $q = q_{2} - q_{1} \in [1, Q]$ and $p = ⌊ q_{2} θ ⌋ - ⌊ q_{1} θ ⌋$ . Then

∣ qθ - p ∣ = {q_{2} θ} - {q_{1} θ} < \frac{1}{Q} \leq \frac{1}{q} .

Dividing by $q$ gives $∣ θ - p / q ∣ < 1/ (qQ) \leq 1/ q^{2}$ .

For infinitude: since $θ$ is irrational, $∣ qθ - p ∣ > 0$ for each such pair, so we may choose $Q^{'} > 1/∣ qθ - p ∣$ and repeat, obtaining a pair $(p^{'}, q^{'})$ with $∣ q^{'} θ - p^{'} ∣ < 1/ Q^{'} < ∣ qθ - p ∣$ , hence a genuinely new pair. Iterating produces infinitely many.∎

Theorem 5.30 (Pell's equation always has a nontrivial solution). Let $d > 0$ be a non-square integer. Then $x^{2} - d y^{2} = 1$ has a solution with $y \neq = 0$ .

Proof. Step 1: many pairs with $∣ x^{2} - d y^{2} ∣$ small. Apply the lemma Dirichlet's approximation theorem to $θ = d$ , which is irrational because $d$ is not a square. It gives infinitely many $(p, q)$ , $q \geq 1$ , with $∣ p - q d ∣ < 1/ q$ . For each,

∣ p + q d ∣ \leq ∣ p - q d ∣ + 2 q d < \frac{1}{q} + 2 q d \leq q (1 + 2 d),

using $1/ q \leq q$ . Multiplying the two bounds,

∣ p^{2} - d q^{2} ∣ = ∣ p - q d ∣ \cdot ∣ p + q d ∣ < \frac{1}{q} \cdot q (1 + 2 d) = 1 + 2 d .

So infinitely many pairs $(p, q)$ satisfy $∣ p^{2} - d q^{2} ∣ < 1 + 2 d$ , a bound independent of $p, q$ .

Step 2: pigeonhole on the value. The integer $k = p^{2} - d q^{2}$ is nonzero (else $d$ would be a square) and lies in a finite set, so some fixed $k \neq = 0$ occurs for infinitely many pairs.

Step 3: pigeonhole on residues. Among those pairs, $(p mod ∣ k ∣, q mod ∣ k ∣)$ takes at most $k^{2}$ values, so two distinct pairs $(p_{1}, q_{1}) \neq = (p_{2}, q_{2})$ agree in both residues:

p_{1} \equiv p_{2}, q_{1} \equiv q_{2} (mod ∣ k ∣) .

We may also assume $(p_{1}, q_{1}) \neq = \pm (p_{2}, q_{2})$ , since infinitely many pairs are available and each $\pm$ class is finite.

Step 4: divide. Work in $Z [d]$ with norm $N (u + v d) = u^{2} - d v^{2}$ . Compute

(p_{1} + q_{1} d) (p_{2} - q_{2} d) = (p_{1} p_{2} - d q_{1} q_{2}) + (q_{1} p_{2} - p_{1} q_{2}) d =: X + Y d .

Its norm is $N (p_{1} + q_{1} d) N (p_{2} - q_{2} d) = k \cdot k = k^{2}$ , so

X^{2} - d Y^{2} = k^{2} .

Now the congruences: $p_{1} p_{2} - d q_{1} q_{2} \equiv p_{1}^{2} - d q_{1}^{2} = k \equiv 0 (mod ∣ k ∣)$ , and $q_{1} p_{2} - p_{1} q_{2} \equiv q_{1} p_{1} - p_{1} q_{1} = 0 (mod ∣ k ∣)$ . Hence $X = k x$ and $Y = k y$ for integers $x, y$ , and dividing $X^{2} - d Y^{2} = k^{2}$ by $k^{2}$ gives

x^{2} - d y^{2} = 1.

Step 5: nontriviality. If $y = 0$ then $x = \pm 1$ and $X + Y d = \pm k$ , so $p_{1} + q_{1} d = \pm k / (p_{2} - q_{2} d) = \pm (p_{2} + q_{2} d)$ , using $N (p_{2} + q_{2} d) = k$ . That contradicts $(p_{1}, q_{1}) \neq = \pm (p_{2}, q_{2})$ . Hence $y \neq = 0$ .∎

Theorem 5.31 (Continued fractions locate the fundamental solution). Let $d > 0$ be a non-square, and let $d = [a_{0}; \overline{a_{1}, \dots, a_{ℓ}}]$ be its (purely periodic after the first term) continued fraction expansion, with convergents $p_{k} / q_{k}$ . Then the fundamental solution of $x^{2} - d y^{2} = 1$ is

(x, y) = {(p_{ℓ - 1}, q_{ℓ - 1}) (p_{2 ℓ - 1}, q_{2 ℓ - 1}) if ℓ is even, if ℓ is odd,

and every solution of $x^{2} - d y^{2} = \pm 1$ in positive integers arises as a convergent of $d$ .

Proof. Proof sketch — assumes the standard theory of continued fractions (best-approximation property, periodicity of quadratic irrationals); only the shape of the argument is given.

Two classical facts do the work. First, Lagrange's theorem: the expansion of $d$ is periodic of the palindromic shape $[a_{0}; \overline{a_{1}, \dots, a_{ℓ - 1}, 2 a_{0}}]$ . Second, best approximation: if $∣ x^{2} - d y^{2} ∣ < d$ with $x, y > 0$ then $∣ x / y - d ∣ < 1/ (2 y^{2})$ , and by Legendre's theorem every such rational is a convergent — so for $d \geq 2$ a solution of $x^{2} - d y^{2} = 1$ can only be a convergent. Running the convergent recursion with the periodicity gives $p_{k}^{2} - d q_{k}^{2} = (- 1)^{k + 1} Q_{k + 1}$ for the auxiliary quantities $Q_{k}$ of the expansion, with $Q_{k + 1} = 1$ exactly when $ℓ ∣ k + 1$ ; the sign selects the stated index.∎

Example 5.32 (Fundamental solutions for small $d$ ). Find the fundamental solutions for $d = 2, 3, 5, 6, 7, 13$ .

Solution.

For small $d$ one can simply increase $y$ until $d y^{2} + 1$ is a square.
$d = 2$ : $y = 2 \Rightarrow 9 = 3^{2}$ , so $(3, 2)$ .
$d = 3$ : $y = 1 \Rightarrow 4 = 2^{2}$ , so $(2, 1)$ .
$d = 5$ : $y = 1, 2, 3$ give $6, 21, 46$ ; $y = 4$ gives $81 = 9^{2}$ , so $(9, 4)$ .
$d = 6$ : $y = 2 \Rightarrow 25 = 5^{2}$ , so $(5, 2)$ .
$d = 7$ : $y = 3 \Rightarrow 64 = 8^{2}$ , so $(8, 3)$ .
$d = 13$ : the search runs to $y = 180$ , giving $x = 649$ ; check $64 9^{2} = 421201$ and $13 \cdot 18 0^{2} = 421200$ ✓. The jump from $d = 7$ to $d = 13$ is the phenomenon the theorem Continued fractions locate the fundamental solution explains: the period of $13$ is $5$ , odd, so one must go to index $2 ℓ - 1 = 9$ .

□

Figure 5.33. Integer points on the hyperbola

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

: the trivial

(1, 0)

and the solutions

(3, 2)

(17, 12)

generated by powers of

3 + 22

. The asymptote

y = x / 2

is the line the points crowd against.

Exercises for §5.11 →

5.12Pell solutions as a group of units

The composition law of the proposition Brahmagupta composition is not an identity that happens to hold; it is multiplication in a ring, and once that is said, the structure of the solution set is forced.

Notation. For a non-square $d > 0$ set $Z [d] = {u + v d : u, v \in Z}$ , a subring of $R$ . Its conjugation is $\overline{u + v d} = u - v d$ and its norm is

N (u + v d) = (u + v d) (u - v d) = u^{2} - d v^{2} \in Z .

Conjugation is a ring automorphism, so $N$ is multiplicative: $N (α β) = N (α) N (β)$ .

Theorem 5.34 (Every solution is a power of the fundamental one). Let $d > 0$ be a non-square and let $ε = x_{1} + y_{1} d$ correspond to the fundamental solution, i.e. the solution with $x_{1}, y_{1} > 0$ and $x_{1}$ least. Write $U_{1} = {α \in Z [d] : N (α) = 1}$ . Then every solution of $x^{2} - d y^{2} = 1$ is

x + y d = \pm ε^{n} for a unique n \in Z,

so that $U_{1} = {\pm ε^{n}} ≅ Z /2 Z \times Z$ .

Proof. Step 0: $U_{1}$ is a group, identified with the solution set by $(x, y) \mapsto x + y d$ . The map is injective because $d$ is irrational, and surjective onto $U_{1}$ by definition of $N$ . Multiplicativity of $N$ makes $U_{1}$ closed under products, and $N (α) = 1$ means $α \overset{α}{ˉ} = 1$ , so $α^{- 1} = \overset{α}{ˉ} \in U_{1}$ . Hence $U_{1}$ is a subgroup of $Z [d]^{\times}$ .

A fundamental solution exists: nontrivial solutions exist by the theorem Pell's equation always has a nontrivial solution, and if $(x, y)$ is one then so are $(\pm x, \pm y)$ , so there is one with $x, y > 0$ ; among these $x$ takes a least value, and that $x$ determines $y = (x^{2} - 1) / d$ uniquely.

Monotonicity. For solutions with $x, y > 0$ , the quantity $α = x + y d$ increases with $x$ : if $x < x^{'}$ then $y < y^{'}$ too (since $y = (x^{2} - 1) / d$ is increasing in $x$ ), so $α < α^{'}$ . Thus $ε$ is the smallest element of $U_{1}$ that exceeds $1$ : any $α \in U_{1}$ with $α > 1$ has $α^{- 1} = \overset{α}{ˉ} = x - y d \in (0, 1)$ , so $x = \frac{1}{2} (α + α^{- 1}) > 0$ and $y = \frac{1}{2 d} (α - α^{- 1}) > 0$ , making $(x, y)$ a positive solution; minimality of $x_{1}$ then gives $α \geq ε$ .

Generation. Let $α \in U_{1}$ with $α > 1$ ; we show $α = ε^{n}$ for some $n \geq 1$ . Since $ε > 1$ , the powers $ε^{n} \to \infty$ , so there is a unique $n \geq 1$ with

ε^{n} \leq α < ε^{n + 1} .

Put $β = α ε^{- n}$ . By Step 0, $β \in U_{1}$ , and by construction $1 \leq β < ε$ . If $β > 1$ then $β$ is an element of $U_{1}$ strictly between $1$ and $ε$ , contradicting the minimality established above. Hence $β = 1$ and $α = ε^{n}$ .

All of $U_{1}$ . Let $α \in U_{1}$ . If $α = \pm 1$ take $n = 0$ . Otherwise $∣ α ∣$ and $∣ α ∣^{- 1}$ are reciprocal positive reals, so exactly one of $\pm α, \pm α^{- 1}$ exceeds $1$ ; by the previous paragraph it equals $ε^{n}$ for some $n \geq 1$ , so $α = \pm ε^{\pm n}$ .

Uniqueness and structure. If $\pm ε^{n} = \pm ε^{m}$ then comparing signs and taking logarithms of absolute values gives $n lo g ε = m lo g ε$ with $lo g ε > 0$ , so $n = m$ . Hence $\pm ε^{n} \mapsto (\pm 1, n)$ is an isomorphism $U_{1} \to {\pm 1} \times Z$ .∎

Example 5.35 (The first four solutions for $d = 3$ ). List the four smallest positive solutions of $x^{2} - 3 y^{2} = 1$ .

Solution.

Fundamental: $y = 1$ gives $3 + 1 = 4 = 2^{2}$ , so $ε = 2 + 3$ , $(x_{1}, y_{1}) = (2, 1)$ .
Recursion with $x_{1} = 2, y_{1} = 1, d = 3$ : $x_{n + 1} = 2 x_{n} + 3 y_{n}$ , $y_{n + 1} = 2 y_{n} + x_{n}$ .
$(2, 1) \to (4 + 3, 2 + 2) = (7, 4)$ . Check $49 - 48 = 1$ ✓.
$(7, 4) \to (14 + 12, 8 + 7) = (26, 15)$ . Check $676 - 675 = 1$ ✓.
$(26, 15) \to (52 + 45, 30 + 26) = (97, 56)$ . Check $9409 - 3 \cdot 3136 = 9409 - 9408 = 1$ ✓.

□

Remark. Dirichlet's unit theorem, in this smallest interesting case, asserts that the unit group of $Z [d]$ has rank $1$ ; the theorem Every solution is a power of the fundamental one is the concrete form of that statement. The generator $ε$ is the fundamental unit and $lo g ε$ the regulator, an invariant that grows erratically with $d$ — which is why $d = 61$ is so much worse than $d = 60$ .

Exercises for §5.12 →

5.13The local–global principle

Congruence conditions give necessary criteria for solvability. The remarkable fact, for quadratic forms, is that they are also sufficient — together with the obvious real condition. Making this precise needs a way to speak of "all congruences at $p$ at once", which is what the $p$ -adic numbers $Q_{p}$ provide.

Notation. A homogeneous $f \in Q [x_{1}, \dots, x_{n}]$ is locally soluble if it has a nontrivial zero in $R$ and one in $Q_{p}$ for every prime $p$ , and globally soluble if it has a nontrivial zero in $Q$ . The local–global (Hasse) principle holds for a family of equations if, within it, local solubility implies global solubility.

Solubility in $Q_{p}$ is decidable by a finite computation: by Hensel's lemma a nonsingular solution of the congruence modulo a sufficiently high, explicit power of $p$ lifts to $Q_{p}$ . So local solubility is checkable, which is what makes the principle useful when it holds.

Theorem 5.36 (Hasse–Minkowski). Let $q (x_{1}, \dots, x_{n})$ be a nondegenerate quadratic form over $Q$ . Then $q$ has a nontrivial zero over $Q$ if and only if it has a nontrivial zero over $R$ and over $Q_{p}$ for every prime $p$ .

Proof. Proof sketch — assumes $p$ -adic numbers, the theory of the Hilbert symbol, Dirichlet's theorem on primes in arithmetic progressions, and (for $n = 4$ ) the Hasse–Minkowski statement for $n = 3$ ; the induction is described but the cases are not carried out.

One direction is trivial: $Q$ embeds in $R$ and in each $Q_{p}$ , so a rational zero is a zero everywhere locally.

The converse is an induction on $n$ after diagonalising $q$ as $a_{1} x_{1}^{2} + \dots + a_{n} x_{n}^{2}$ .

$n = 1$ : only the trivial zero, locally as well as globally.
$n = 2$ : $a_{1} x_{1}^{2} + a_{2} x_{2}^{2}$ is isotropic iff $- a_{2} / a_{1}$ is a square, and a rational that is a square in every $Q_{p}$ and in $R$ is a square, by comparing valuation parities and the sign.
$n = 3$ : Legendre's theorem — $a x^{2} + b y^{2} + c z^{2} = 0$ with $a, b, c$ squarefree and pairwise coprime is soluble iff the signs are not all equal and $- b c, - a c, - ab$ are quadratic residues modulo $∣ a ∣, ∣ b ∣, ∣ c ∣$ . The classical proof is a descent using the geometry of numbers.
$n = 4$ : the hard case. Split $q = (a_{1} x_{1}^{2} + a_{2} x_{2}^{2}) - (- a_{3} x_{3}^{2} - a_{4} x_{4}^{2})$ and ask which rationals are represented by both binary forms. Hilbert symbols describe the two sets, and Dirichlet's theorem on primes in arithmetic progressions produces a rational represented by both.
$n \geq 5$ : every $p$ -adic form in five variables is isotropic, so only the real condition survives; an indefinite rational form in $\geq 5$ variables splits off a hyperbolic plane, and one inducts.

Dirichlet's theorem is not a formal device here: it is where the arithmetic of $Q$ enters.∎

Example 5.37 (A conic with no rational points). Decide whether $3 x^{2} + 5 y^{2} = 7 z^{2}$ has a nontrivial rational solution.

Solution.

Rewrite as the form $q = 3 x^{2} + 5 y^{2} - 7 z^{2}$ . Over $R$ it is indefinite, so it is soluble there.
Check $p = 7$ . If $7 ∤ x, y$ then modulo $7$ : $3 x^{2} + 5 y^{2} \equiv 0$ , i.e. $y^{2} \equiv - 3 \cdot 5^{- 1} x^{2}$ . Now $5^{- 1} \equiv 3 (mod 7)$ since $15 \equiv 1$ , so $y^{2} \equiv - 9 x^{2} \equiv - 2 x^{2} \equiv 5 x^{2} (mod 7)$ .
So we need $5$ to be a quadratic residue mod $7$ . The squares mod $7$ are ${1, 2, 4}$ , and $5 \in / {1, 2, 4}$ .
Hence $7 ∣ x$ and $7 ∣ y$ ; then $49 ∣ 3 x^{2} + 5 y^{2} = 7 z^{2}$ , so $7 ∣ z^{2}$ , so $7 ∣ z$ . Scaling down by $7$ repeats forever — a descent — so the only $7$ -adic solution is trivial.
The form is not locally soluble at $7$ , so by the theorem Hasse–Minkowski (the easy direction suffices) it has no nontrivial rational solution.

□

Exercises for §5.13 →

5.14Hilbert symbols: making the check finite

Hasse–Minkowski demands a check at infinitely many primes, which would be useless without a bookkeeping device. For $a, b \in Q^{\times}$ and a place $v$ of $Q$ — a prime $p$ , or $\infty$ standing for $R$ — the Hilbert symbol is

(a, b)_{v} = {+ 1 - 1 if a x^{2} + b y^{2} = z^{2} has a nontrivial solution in Q_{v}, otherwise.

It is multiplicative in each argument and symmetric, and for odd $p$ with $a, b$ $p$ -adic units it equals $+ 1$ — so only finitely many places can possibly give $- 1$ .

Theorem 5.38 (Hilbert's product formula). For all $a, b \in Q^{\times}$ , the symbol $(a, b)_{v}$ equals $+ 1$ for all but finitely many places $v$ , and

v \prod (a, b)_{v} = 1,

the product running over $\infty$ and all primes.

Proof. Proof sketch — assumes the explicit formulas for $(a, b)_{p}$ in terms of Legendre symbols, and quadratic reciprocity; the reduction is given, the case-checking is not.

By bimultiplicativity it suffices to treat $a, b$ each ranging over $- 1$ and the primes. For odd $p$ and $p$ -adic units $a, b$ one has $(a, b)_{p} = 1$ , which already gives finiteness: only $\infty$ , the prime $2$ , and the primes occurring in $a$ and $b$ can contribute.

The rest is a handful of cases. For $a = p$ , $b = q$ distinct odd primes the explicit formulas give $(p, q)_{p} = (\frac{q}{p})$ , $(p, q)_{q} = (\frac{p}{q})$ , $(p, q)_{2} = (- 1)^{\frac{p - 1}{2} \frac{q - 1}{2}}$ and $(p, q)_{v} = 1$ elsewhere. The product formula in this case therefore reads

(\frac{q}{p}) (\frac{p}{q}) (- 1)^{\frac{p - 1}{2} \frac{q - 1}{2}} = 1,

which is exactly quadratic reciprocity; the cases $a = - 1$ and $a = 2$ reproduce the two supplementary laws. The product formula is a repackaging of reciprocity, and conversely.∎

Intuition. Think of $(a, b)_{v}$ as a local "obstruction sign". The product formula says the signs cannot be assigned independently: if you know all but one of them, the last is determined. That is precisely what makes Hasse–Minkowski in four variables work, and it is also why, when checking a conic for solubility, it is enough to check all places but one.

Exercises for §5.14 →

5.15Where the principle fails

Hasse–Minkowski is a theorem about quadratic forms, and the hypothesis is not decorative: in degree three the principle is false, and the counterexample is explicit.

Theorem 5.39 (Selmer's counterexample to the local–global principle). The cubic curve

3 x^{3} + 4 y^{3} + 5 z^{3} = 0

has a nontrivial solution in $R$ and in $Q_{p}$ for every prime $p$ , but its only rational solution is $(0, 0, 0)$ .

Proof. Local solubility, proved. Over $R$ take $(- 33, 1, 1)$ , since $3 (- 3) + 4 + 5 = 0$ . For $p \geq 7$ the projective plane cubic $C$ is smooth over $F_{p}$ and the Hasse–Weil bound gives $# C (F_{p}) \geq p + 1 - 2 p > 0$ , so a smooth $F_{p}$ -point exists and Hensel lifts it. For $p \in {2, 5}$ cubing is a bijection on $F_{p}^{\times}$ , since $3 ∤ p - 1$ , so any $x, y$ with $3 x^{3} + 4 y^{3} \neq = 0$ is completed by a unique $z$ , again nonsingular. For $p = 3$ one exhibits a nonsingular solution modulo $27$ directly.

Global insolubility — proof sketch, assumes the arithmetic of the cubic field $K = Q (360)$ ; Selmer's computation is not reproduced. Scale a nonzero rational solution to coprime integers; substituting converts the equation into a norm equation $N_{K / Q} (α) = c$ with $α$ confined to a specific coset. Selmer computed the class and unit groups of $K$ and showed the required $α$ would force a relation among the units that does not hold. In modern language the Tate–Shafarevich group of the associated elliptic curve has a nontrivial $3$ -part, and that element is the obstruction the local conditions cannot see; it is captured by the Brauer–Manin pairing, since every rational point pairs to zero against the Brauer group while here some Brauer class kills the entire local adelic set.∎

Remark. The moral is sharp. Local solubility is a cheap necessary condition which for quadratic forms happens also to be sufficient; past degree two it is merely necessary, and the failure is measured by a cohomological invariant. Even the Brauer–Manin obstruction is not always the whole story: Skorobogatov produced a surface with no rational points and no Brauer–Manin obstruction.

Example 5.40 (Checking local solubility is not hard). Verify that $3 x^{3} + 4 y^{3} + 5 z^{3} \equiv 0$ has a nontrivial solution modulo $7$ , and explain why that implies solubility in $Q_{7}$ .

Solution.

Cubes mod $7$ : since $g cd (3, 6) = 3$ , the cubes are the cubic residues ${0, 1, 6}$ , each nonzero one hit three times.
Try $z = 0$ : need $3 x^{3} \equiv - 4 y^{3} \equiv 3 y^{3} (mod 7)$ , i.e. $x^{3} \equiv y^{3}$ . Take $x = y = 1$ : $3 + 4 = 7 \equiv 0$ ✓. So $(1, 1, 0)$ is a nontrivial solution mod $7$ .
Smoothness: the partial derivatives are $9 x^{2}, 12 y^{2}, 15 z^{2}$ , and at $(1, 1, 0)$ the first is $9 \equiv 2 \neq \equiv 0 (mod 7)$ , so the point is a nonsingular zero.
Hensel's lemma lifts a nonsingular zero modulo $p$ to a zero in $Z_{p}$ , hence a nontrivial $Q_{7}$ -point. ✓ The equation passes every such test and still has no rational point — that is the content of the theorem Selmer's counterexample to the local–global principle.

□

Exercises for §5.15 →

5.16Thue's theorem

Past degree two, the governing result for two-variable equations is Thue's. It says that a homogeneous form of degree at least three, set equal to a constant, has only finitely many integer solutions — an enormous strengthening of anything congruences could give.

Theorem 5.41 (Thue's theorem). Let $F (x, y) \in Z [x, y]$ be homogeneous of degree $k \geq 3$ , irreducible over $Q$ . Then for every nonzero $c \in Z$ the Thue equation

F (x, y) = c

has only finitely many solutions $(x, y) \in Z^{2}$ .

Proof. Proof — complete, assuming the theorem Thue's approximation theorem stated in the next section. Write $F (x, y) = a_{0} \prod_{j = 1}^{k} (x - α_{j} y)$ where $α_{1}, \dots, α_{k}$ are the (distinct, since $F$ is irreducible and separable) roots of $F (t, 1)$ , algebraic numbers of degree $k$ over $Q$ .

Suppose there were infinitely many solutions. Since for fixed $y$ there are at most $k$ values of $x$ , the values $∣ y ∣$ must be unbounded; pass to a subsequence with $∣ y ∣ \to \infty$ . Then

∣ c ∣ = ∣ F (x, y) ∣ = ∣ a_{0} ∣ ∣ y ∣^{k} j = 1 \prod k \frac{x}{y} - α_{j} .

Because $∣ c ∣$ is fixed and $∣ y ∣^{k} \to \infty$ , the product of the $k$ factors tends to $0$ , so $x / y$ approaches one of the $α_{j}$ ; passing to a further subsequence, say $x / y \to α_{1}$ . Then the other factors $∣ x / y - α_{j} ∣$ , $j \geq 2$ , are bounded below by a positive constant $δ$ (half the minimal distance from $α_{1}$ to the others, eventually). Hence

\frac{x}{y} - α_{1} \leq \frac{∣ c ∣}{∣ a _{0} ∣ δ ^{k - 1}} \cdot \frac{1}{∣ y ∣ ^{k}} = \frac{C}{∣ y ∣ ^{k}} .

But $α_{1}$ is an algebraic number of degree $k \geq 3$ , so the theorem Thue's approximation theorem says there are only finitely many rationals $x / y$ with

\frac{x}{y} - α_{1} < \frac{1}{∣ y ∣ ^{k /2 + 1 + ϵ}},

and since $k > k /2 + 1$ for $k \geq 3$ , the displayed inequality is eventually stronger than this. That contradicts having infinitely many solutions.∎

Remark. The deduction is genuine but inherits the ineffectivity of its input: "finitely many" says nothing about how large they can be, so the argument cannot certify a found list as complete. Repairing that is what Baker's method below is for.

Example 5.42 (A Thue equation solved by hand). Find all integer solutions of $x^{3} - 2 y^{3} = 1$ .

Solution.

$F (x, y) = x^{3} - 2 y^{3}$ is homogeneous of degree $3$ and irreducible (its root $32$ has degree $3$ ), so the theorem Thue's theorem applies and there are finitely many solutions.
Obvious solution: $(1, 0)$ .
Small search: $y = 1$ needs $x^{3} = 3$ , no; $y = - 1$ needs $x^{3} = - 1$ , so $x = - 1$ : check $- 1 - 2 (- 1) = - 1 + 2 = 1$ ✓, giving $(- 1, - 1)$ .
$y = \pm 2$ : $x^{3} = 1 \pm 16$ , i.e. $17$ or $- 15$ , neither a cube. $y = \pm 3$ : $x^{3} = 1 \pm 54 = 55$ or $- 53$ , neither.
In fact $(1, 0)$ and $(- 1, - 1)$ are the only solutions — a result of Delone and Nagell, who proved that $x^{3} - d y^{3} = 1$ has at most one nontrivial solution. Thue's theorem guarantees finiteness; this sharper theorem supplies the count.

□

Exercises for §5.16 →

5.17Approximation: Liouville, Thue, Roth

The engine behind Thue is one principle: algebraic numbers are badly approximable by rationals. The elementary version is Liouville's, short enough to prove in full.

Theorem 5.43 (Liouville's approximation theorem). Let $α$ be an irrational algebraic number of degree $k \geq 2$ over $Q$ . Then there is a constant $C = C (α) > 0$ such that for all integers $p, q$ with $q \geq 1$ ,

α - \frac{p}{q} > \frac{C}{q ^{k}} .

Proof. Let $f (t) = a_{k} t^{k} + \dots + a_{0} \in Z [t]$ be a minimal polynomial of $α$ ; being irreducible of degree $k \geq 2$ it has no rational root.

Fix $p / q$ . If $∣ α - p / q ∣ \geq 1$ the bound holds with $C \leq 1$ , so assume $p / q \in [α - 1, α + 1]$ , and set $M = max_{∣ t - α ∣ \leq 1} ∣ f^{'} (t) ∣$ , finite by continuity on a compact interval and positive after enlarging if necessary.

Lower bound on $∣ f (p / q) ∣$ . Since $f$ has no rational root, $f (p / q) \neq = 0$ . Clearing denominators,

q^{k} f (p / q) = a_{k} p^{k} + a_{k - 1} p^{k - 1} q + \dots + a_{0} q^{k}

is a nonzero integer, so $∣ q^{k} f (p / q) ∣ \geq 1$ , i.e.

f (\frac{p}{q}) \geq \frac{1}{q ^{k}} .

Upper bound via the mean value theorem. There is $ξ$ between $α$ and $p / q$ , hence in $[α - 1, α + 1]$ , with

f (\frac{p}{q}) = f (\frac{p}{q}) - f (α) = f^{'} (ξ) (\frac{p}{q} - α),

so $∣ f (p / q) ∣ \leq M ∣ α - p / q ∣$ .

Combine. $M ∣ α - p / q ∣ \geq 1/ q^{k}$ , giving $∣ α - p / q ∣ \geq \frac{1}{M} q^{- k}$ . Taking $C = min (1, 1/ (2 M))$ makes the inequality strict and covers the discarded case.∎

Liouville's exponent $k$ is the trivial one, and lowering it is the entire subject of Diophantine approximation: Thue reached roughly $k /2$ , Siegel, Dyson and Gelfond pushed further, and Roth reached the optimal $2$ .

Theorem 5.44 (Thue's approximation theorem, and Thue–Siegel–Roth). Let $α$ be algebraic of degree $k \geq 2$ .

(Thue, 1909.) For every $ϵ > 0$ there are only finitely many rationals $p / q$ with $α - \frac{p}{q} < q^{- (k /2 + 1 + ϵ)}$ .
(Roth, 1955.) For every $ϵ > 0$ there are only finitely many rationals $p / q$ with $α - \frac{p}{q} < q^{- (2 + ϵ)}$ . The exponent $2$ is optimal, since the lemma Dirichlet's approximation theorem produces infinitely many $p / q$ with $∣ α - p / q ∣ < q^{- 2}$ .

Proof. Proof sketch — assumes the theory of auxiliary polynomials in many variables, Siegel's lemma, and Roth's index/Wronskian machinery; none of these is developed here.

Both are contradiction arguments of the same shape. Assume infinitely many very good approximations $p_{1} / q_{1}, \dots, p_{m} / q_{m}$ with rapidly increasing denominators. By Siegel's lemma — a pigeonhole statement about integer solutions of underdetermined linear systems — construct a nonzero auxiliary polynomial $P (t_{1}, \dots, t_{m}) \in Z [t]$ of controlled height vanishing to high order at $(α, \dots, α)$ . The approximations force $P$ to be extremely small at $(p_{1} / q_{1}, \dots, p_{m} / q_{m})$ , while clearing denominators makes it a nonzero integer, hence at least $1$ . Tuning the parameters makes the two bounds conflict — provided $P$ really is nonzero there, which is the technical heart (Roth's lemma, via generalised Wronskians). Thue uses $m = 2$ ; Roth needs $m$ growing with $1/ ϵ$ .

The ineffectivity is intrinsic: the argument shows a second very good approximation cannot exist once a first does, but never locates the first.∎

Example 5.45 (Liouville's bound applied to $32$ ). Give an explicit lower bound for $∣ 32 - p / q ∣$ .

Solution.

$α = 2^{1/3}$ has minimal polynomial $f (t) = t^{3} - 2$ , of degree $k = 3$ .
$f^{'} (t) = 3 t^{2}$ , and on $[α - 1, α + 1] \subseteq [0.26, 2.26]$ we have $∣ f^{'} (t) ∣ \leq 3 (2.26)^{2} = 15.33$ , so take $M = 16$ .
The proof gives $∣ α - p / q ∣ \geq \frac{1}{16} q^{- 3}$ for every rational $p / q$ .
Sanity check with $p / q = 5/4 = 1.25$ : $∣ 2^{1/3} - 1.25∣ = ∣1.2599 - 1.25∣ = 0.0099$ , while $\frac{1}{16} \cdot 4^{- 3} = 1/1024 = 0.00098$ . The bound holds with room to spare ✓.
Roth's theorem improves the exponent from $3$ to $2 + ϵ$ but with a constant nobody can write down — the trade-off in one line.

□

Exercises for §5.17 →

5.18Effective versions and Baker's method

An ineffective finiteness theorem bounds the number of solutions without bounding their size; an effective one supplies a computable $B$ with $max (∣ x ∣, ∣ y ∣) \leq B$ for every solution, so that a finite search settles the equation. Thue's theorem is ineffective; the repair came sixty years later, from transcendence theory.

Theorem 5.46 (Baker's bound and effective Thue equations). (Baker, 1966–68.) Let $α_{1}, \dots, α_{n}$ be nonzero algebraic numbers with $lo g α_{1}, \dots, lo g α_{n}$ linearly independent over $Q$ , and let $b_{1}, \dots, b_{n}$ be integers, not all zero, with $B = max ∣ b_{i} ∣$ . Then there are effectively computable $C, κ > 0$ depending only on the $α_{i}$ and their degrees with

∣ b_{1} lo g α_{1} + \dots + b_{n} lo g α_{n} ∣ > C B^{- κ}, whenever the left side is nonzero.

Consequently, for a Thue equation $F (x, y) = c$ of degree $k \geq 3$ every solution satisfies an effectively computable bound $max (∣ x ∣, ∣ y ∣) \leq B (F, c)$ .

Proof. Proof sketch — assumes transcendence methods (auxiliary functions, Siegel's lemma, extrapolation) and the unit theorem for number fields; the two halves are outlined only.

The linear-forms bound. Assume $Λ = \sum b_{i} lo g α_{i}$ is very small and build an auxiliary analytic function out of the $α_{i}^{z}$ , vanishing to high order on a grid of integer points. Smallness of $Λ$ extrapolates that vanishing to a larger grid, until the function vanishes identically, contradicting linear independence of the logarithms. Every constant is explicit, which is why the conclusion is effective.

The application to Thue. Factor $F (x, y) = a_{0} \prod (x - α_{j} y) = c$ . Each $β_{j} = x - α_{j} y$ is an algebraic integer of bounded norm, hence lies in one of finitely many classes modulo units; writing $β_{j} = γ_{j} η_{1}^{b_{1}} \dots η_{r}^{b_{r}}$ in fundamental units and feeding this into Siegel's identity $(α_{1} - α_{2}) β_{3} + (α_{2} - α_{3}) β_{1} + (α_{3} - α_{1}) β_{2} = 0$ forces a linear form in logarithms to be exponentially small in $B = max ∣ b_{i} ∣$ . Baker's bound caps $B$ , hence $x$ and $y$ .

The resulting bounds are astronomically large, typically iterated exponentials, but they are bounds, and lattice reduction (LLL) routinely brings them down to a searchable range.∎

Exercises for §5.18 →

5.19Thue's theorem and Fermat's equation

Fermat's equation has three unknowns, so Thue does not apply to it. It applies at once to the two-variable family alongside it, with a consequence that was out of reach before 1909.

Theorem 5.47 ( $x^{n} + y^{n} = c$ has finitely many solutions). Let $n \geq 3$ and let $c$ be a nonzero integer. Then $x^{n} + y^{n} = c$ has only finitely many integer solutions.

Proof. The form $F (x, y) = x^{n} + y^{n}$ is homogeneous of degree $n \geq 3$ . Over $Q$ it factors as

x^{n} + y^{n} = j \prod Φ_{j} (x, y)

into irreducible homogeneous factors, corresponding to the factorisation of $t^{n} + 1$ into cyclotomic-type irreducibles over $Q$ . If $n$ is odd, $x + y$ is one such factor and the complementary factor $x^{n - 1} - x^{n - 2} y + \dots + y^{n - 1}$ has degree $n - 1 \geq 2$ ; if $n$ is even there is no linear factor at all, since $t^{n} + 1$ has no real root.

Each solution gives a factorisation $c = \prod_{j} Φ_{j} (x, y)$ into integers, and $c$ has only finitely many such factorisations. Fix one, so that $Φ_{j} (x, y) = c_{j}$ for each $j$ . A factor with $de g Φ_{j} \geq 3$ gives a Thue equation, finite by the theorem Thue's theorem. A factor of degree $2$ is definite — $x^{2} - x y + y^{2}$ and its analogues are positive definite, being $\frac{1}{2} (x^{2} + y^{2} + (x - y)^{2})$ up to scaling — so $Φ_{j} = c_{j}$ describes an ellipse, containing finitely many lattice points. A factor of degree $1$ , $x + y = c_{1}$ , can be substituted into any other factor equation, which is then a nonconstant one-variable polynomial equation with finitely many roots; and at least one other factor exists whenever $n \geq 3$ , since $de g (x^{n} + y^{n}) \geq 3$ . Every branch gives finitely many solutions and there are finitely many branches.∎

Example 5.48 (Sums of two cubes equal to $9$ ). Find the integer solutions of $x^{3} + y^{3} = 9$ and explain the role of the factorisation.

Solution.

Factor: $x^{3} + y^{3} = (x + y) (x^{2} - x y + y^{2}) = 9$ . Both factors are integers.
Note $x^{2} - x y + y^{2} = \frac{1}{2} (x^{2} + y^{2} + (x - y)^{2}) \geq 0$ , so both factors have the same sign, and their product is $9 > 0$ , so both are positive.
The positive factorisations of $9$ are $1 \cdot 9$ , $3 \cdot 3$ , $9 \cdot 1$ .
$x + y = 1$ , $x^{2} - x y + y^{2} = 9$ : substituting $y = 1 - x$ gives $x^{2} - x (1 - x) + (1 - x)^{2} = 3 x^{2} - 3 x + 1 = 9$ , i.e. $3 x^{2} - 3 x - 8 = 0$ , discriminant $9 + 96 = 105$ , not a square. No integer solution.
$x + y = 3$ , $x^{2} - x y + y^{2} = 3$ : $3 x^{2} - 9 x + 9 = 3$ , i.e. $x^{2} - 3 x + 2 = 0$ , so $x = 1$ or $2$ , giving $(1, 2)$ and $(2, 1)$ . Check $1 + 8 = 9$ ✓.
$x + y = 9$ , $x^{2} - x y + y^{2} = 1$ : $3 x^{2} - 27 x + 81 = 1$ has no integer root since $3 x^{2} - 27 x + 80 = 0$ has discriminant $729 - 960 < 0$ .
So the only solutions are $(1, 2)$ and $(2, 1)$ — finitely many, as the theorem $x^{n} + y^{n} = c$ has finitely many solutions predicts, and here the factorisation made the finiteness explicit without any appeal to Thue.

□

Exercises for §5.19 →

5.20Fermat's Last Theorem

Theorem 5.49 (Fermat's Last Theorem). For every integer $n \geq 3$ the equation

x^{n} + y^{n} = z^{n}

has no solution in nonzero integers $x, y, z$ .

Proof. By the proposition Reduction to $n = 4$ and odd primes it suffices to rule out $n = 4$ and $n = p$ an odd prime. The case $n = 4$ is the corollary Fermat's Last Theorem for $n = 4$ , proved in full below by descent. The case $p = 3$ is Euler's descent in $Z [ζ_{3}]$ , equivalently Kummer's theorem applied to the regular prime $3$ . Every prime $p \geq 5$ is part (3) of the theorem Modularity, Ribet's theorem, and Fermat. Only the first of the three is proved in this chapter; the other two are quoted, with a sketch, where they are stated.∎

Fermat wrote the statement in about 1637 in the margin of his copy of Diophantus, with the remark that he had a marvellous proof which the margin was too narrow to contain. Whatever he had, the one case he did write out is the descent for $n = 4$ below. The general case resisted for 358 years and was proved by Wiles in 1995, with a crucial step joint with Taylor.

The first move costs nothing and cuts the problem down enormously.

Proposition 5.50 (Reduction to $n = 4$ and odd primes). If Fermat's equation has no nonzero solutions for $n = 4$ and for every odd prime $n = p$ , then it has none for any $n \geq 3$ .

Proof. Let $n \geq 3$ . Either $4 ∣ n$ , or $n$ has an odd prime factor $p$ — indeed if $n$ is not divisible by any odd prime then $n$ is a power of $2$ , and $n \geq 3$ forces $n \geq 4$ , so $4 ∣ n$ .

Suppose first $n = 4 m$ . If $x^{n} + y^{n} = z^{n}$ with $x yz \neq = 0$ , put $X = x^{m}$ , $Y = y^{m}$ , $Z = z^{m}$ ; then $X^{4} + Y^{4} = Z^{4}$ with $X Y Z \neq = 0$ , contradicting the case $n = 4$ .

Otherwise $n = \pm$ with $p$ an odd prime. Put $X = x^{m}, Y = y^{m}, Z = z^{m}$ ; then $X^{p} + Y^{p} = Z^{p}$ with $X Y Z \neq = 0$ , contradicting the case $n = p$ .

So no $n \geq 3$ admits a solution.∎

Remark. The reduction explains the shape of the historical record: Euler did $n = 3$ , Dirichlet and Legendre $n = 5$ , Lamé $n = 7$ , and Kummer — inventing ideal numbers to repair the failure of unique factorisation in $Z [ζ_{p}]$ — every regular prime at once, covering all $p < 100$ except $37$ , $59$ , $67$ . What no nineteenth-century method reached was all $p$ at once, since each argument needed control of the class number of $Q (ζ_{p})$ .

Exercises for §5.20 →

5.21The case $n = 4$ : infinite descent

This is the one case of Fermat's Last Theorem that is elementary, and it is proved here completely. The method is Fermat's own infinite descent: from a putative solution manufacture a strictly smaller one; positive integers cannot decrease forever. It is proved in the stronger form $x^{4} + y^{4} = z^{2}$ , which is what makes the descent close up.

Theorem 5.51 (No solutions to $x^{4} + y^{4} = z^{2}$ ). There are no positive integers $x, y, z$ with

x^{4} + y^{4} = z^{2} .

Proof. Suppose solutions exist. Among all of them choose one, $(x, y, z)$ , with $z$ minimal; this is legitimate because any non-empty set of positive integers has a least element.

Step 1: the triple is primitive. If a prime $p$ divides $x$ and $y$ , then $p^{4} ∣ z^{2}$ , so $p^{2} ∣ z$ , and $(x / p, y / p, z / p^{2})$ is a smaller solution — smaller because $z / p^{2} < z$ . This contradicts minimality, so $g cd (x, y) = 1$ , and then $g cd (x^{2}, y^{2}) = 1$ .

Step 2: apply the Pythagorean parametrisation. $(x^{2}, y^{2}, z)$ is a Pythagorean triple, primitive by Step 1. By the lemma Coprimality and parity in a primitive triple exactly one of $x^{2}, y^{2}$ is even; relabel so that $x^{2}$ is odd and $y^{2}$ is even. The theorem Parametrisation of primitive Pythagorean triples gives coprime $m > n \geq 1$ of opposite parity with

x^{2} = m^{2} - n^{2}, y^{2} = 2 mn, z = m^{2} + n^{2} .

Step 3: a second Pythagorean triple. Rewrite the first equation as

x^{2} + n^{2} = m^{2} .

Since $g cd (m, n) = 1$ , this triple $(x, n, m)$ is primitive. Its even member must be $n$ : $m$ and $n$ have opposite parity and $x$ is odd, so if $n$ were odd then $m$ would be even and $x^{2} = m^{2} - n^{2} \equiv 0 - 1 \equiv 3 (mod 4)$ , impossible for a square. So $n$ is even and $m$ is odd. Apply the parametrisation again: there are coprime $a > b \geq 1$ of opposite parity with

x = a^{2} - b^{2}, n = 2 ab, m = a^{2} + b^{2} .

Step 4: extract squares. Substitute into $y^{2} = 2 mn$ :

y^{2} = 2 m \cdot 2 ab = 4 abm, so (\frac{y}{2})^{2} = a b m .

(The left side is an integer since $y$ is even.) Now $a, b, m$ are pairwise coprime: $g cd (a, b) = 1$ by construction; and any prime dividing $m = a^{2} + b^{2}$ and $a$ would divide $b^{2}$ , hence $b$ , contradiction — likewise for $b$ . By the lemma Coprime factors of a square are squares, applied twice (first to $a \cdot (bm)$ , then to $b \cdot m$ ), each of $a, b, m$ is a perfect square:

a = X^{2}, b = Y^{2}, m = Z^{2}

for positive integers $X, Y, Z$ .

Step 5: descend. Substituting into $m = a^{2} + b^{2}$ ,

Z^{2} = m = a^{2} + b^{2} = X^{4} + Y^{4} .

So $(X, Y, Z)$ is another solution of the same equation, in positive integers. Compare sizes:

z = m^{2} + n^{2} > m^{2} \geq m = Z^{2} \geq Z,

using $n \geq 1$ and $Z \geq 1$ . Hence $Z < z$ , contradicting the minimality of $z$ .

The assumption that a solution exists is therefore untenable.∎

Figure 5.52. The descent of the theorem *No solutions to

x^{4} + y^{4} = z^{2}

*: each supposed solution with hypotenuse

z

produces a strictly smaller one with

Z^{2} = m < z

. The heights are the successive

z

-values, which must strictly decrease and cannot.

Corollary 5.53 (Fermat's Last Theorem for $n = 4$ ). The equation $x^{4} + y^{4} = z^{4}$ has no solution in nonzero integers.

Proof. A solution with $x yz \neq = 0$ may be taken with $x, y, z > 0$ by changing signs, since every exponent is even. Then $x^{4} + y^{4} = (z^{2})^{2}$ is a solution of $x^{4} + y^{4} = w^{2}$ in positive integers with $w = z^{2}$ , contradicting the theorem No solutions to $x^{4} + y^{4} = z^{2}$ .∎

Remark. The stronger statement is what makes the descent close up, and this is a recurring feature of the method: proving more can be easier, because a stronger conclusion feeds the induction. The same theorem also shows that no right triangle with integer sides has area a perfect square — equivalently, that $1$ is not a congruent number — which is the form in which Fermat himself recorded the argument.

Exercises for §5.21 →

5.22The modularity route to the general case

For odd prime exponents no elementary argument is known, and the successful strategy came from elliptic curves. To a hypothetical solution $a^{p} + b^{p} = c^{p}$ Frey attached the curve

E_{a, b} : Y^{2} = X (X - a^{p}) (X + b^{p}),

now called the Frey curve. Its discriminant $16 (ab c)^{2 p}$ is a constant times a perfect $p$ -th power, which makes the curve's ramification absurdly mild: it is semistable, and at every prime of bad reduction the $p$ -torsion of $E$ is unramified. Serre and Ribet made "absurdly mild" precise; Wiles supplied what was needed to make the contradiction bite.

Theorem 5.54 (Modularity, Ribet's theorem, and Fermat).

(Modularity, Wiles–Taylor 1995 for semistable curves; Breuil–Conrad–Diamond–Taylor 2001 in general.) Every elliptic curve over $Q$ is modular: its $L$ -function coincides with that of a weight- $2$ newform.
(Ribet 1990, the epsilon conjecture.) If the Frey curve $E_{a, b}$ were modular, the associated newform could be taken of level $2$ .
Consequently, Fermat's equation $x^{p} + y^{p} = z^{p}$ has no nonzero solutions for any prime $p \geq 5$ .

Proof. Proof of (3) from (1) and (2) — complete modulo those two inputs, which are not proved here. A sketch of (1) follows.

Suppose $a^{p} + b^{p} = c^{p}$ with $ab c \neq = 0$ and $p \geq 5$ prime; scale so $g cd (a, b, c) = 1$ , and arrange $a \equiv 3 (mod 4)$ and $b$ even (possible after permuting and changing signs, since exactly one of $a, b, c$ is even). Form the Frey curve $E = E_{a, b}$ . Its discriminant $Δ = 16 (ab c)^{2 p}$ and conductor $N = \prod_{ℓ ∣ ab c} ℓ$ make $E$ semistable.

By (1), $E$ corresponds to a weight- $2$ newform of level $N$ . By (2) — Ribet's level-lowering theorem, applicable because the mod- $p$ representation of $E$ is irreducible (Mazur) and unramified outside $2 p$ — that newform may be taken of level $2$ .

But the space of weight- $2$ cusp forms of level $2$ is zero-dimensional: the modular curve $X_{0} (2)$ has genus $0$ , and the dimension of the space of cusp forms of weight $2$ and level $N$ equals the genus of $X_{0} (N)$ . So there is no such newform, and the assumed solution cannot exist.

Sketch of (1) — assumes deformation theory of Galois representations and Hecke algebras. Wiles proved a modularity lifting theorem: if the mod- $p$ representation $\overset{ρ}{ˉ}$ attached to $E$ is modular, so is every lift with prescribed ramification, the $p$ -adic representation of $E$ included. The proof identifies a universal deformation ring $R$ with a Hecke algebra $T$ by showing the natural surjection $R ↠ T$ is an isomorphism. To start, $\overset{ρ}{ˉ}$ must itself be modular: Langlands–Tunnell supplies this for $p = 3$ , and the " $3$ – $5$ switch" handles curves with reducible mod- $3$ representation. The original gap, in an Euler-system bound on a Selmer group, was closed by Taylor and Wiles with a patching argument.∎

Remark. Notice what was not used: no congruence obstruction, no bound on the size of solutions, nothing in the spirit of the first half of this chapter. The proof works by showing that a solution would create a mathematical object — a weight- $2$ newform of level $2$ — which provably does not exist.

Exercises for §5.22 →

Common Mistakes

Concluding solvability from congruences. The proposition Congruence obstruction runs one way only, and the theorem Selmer's counterexample to the local–global principle is the standard witness. The one place where local information suffices is quadratic forms over $Q$ , by the theorem Hasse–Minkowski — and even there the conclusion is about rational, not integral, solubility.

Using the wrong step in the linear general solution. The step vector is $(b / d, - a / d)$ , not $(b, - a)$ . Writing $x = x_{0} + b t$ , $y = y_{0} - a t$ produces valid solutions but misses $d - 1$ out of every $d$ of them. Divide by the gcd.

Forgetting to check $d ∣ c$ before solving. The extended algorithm on $6 x + 15 y = 8$ yields $6 \cdot 3 + 15 \cdot (- 1) = 3$ , and then an irresistible urge to multiply by $8/3$ . The result is not an integer point.

Dropping a hypothesis in the Pythagorean parametrisation. All four conditions on $(m, n)$ matter: $m > n \geq 1$ for positivity, $g cd (m, n) = 1$ and opposite parity for primitivity. Taking $m = 3, n = 1$ (both odd) gives $(8, 6, 10)$ — a genuine triple, but not primitive, and not in the list the theorem enumerates.

Assuming every triple already has $x$ odd. The convention is a labelling, imposed after the lemma Coprimality and parity in a primitive triple. Given $(20, 21, 29)$ , identify $21$ as the odd leg before applying $m^{2} = (z + x) /2$ ; using $x = 20$ gives $m^{2} = 24.5$ .

Assuming every quadratic ring is a UFD. The theorem Gaussian derivation of the Pythagorean parametrisation works because $Z [i]$ has unique factorisation. The same manoeuvre in $Z [- 5]$ is invalid: $6 = 2 \cdot 3 = (1 + - 5) (1 - - 5)$ . Name the ring and justify unique factorisation in it.

Searching for a Pell solution and giving up. For $d = 61$ the fundamental solution has ten digits, for $d = 109$ fifteen. A search that finds nothing up to $y = 1 0^{6}$ has proved nothing: the theorem Pell's equation always has a nontrivial solution guarantees one exists, and continued fractions find it.

Believing $x^{2} - d y^{2} = - 1$ always has a solution. It does not. $x^{2} - 3 y^{2} = - 1$ is insoluble, since modulo $3$ it would need $x^{2} \equiv - 1 \equiv 2$ , and $2$ is not a square mod $3$ . Solubility of the $- 1$ equation depends on the period of $d$ being odd, and is a genuinely different question from the theorem Pell's equation always has a nontrivial solution.

Confusing "finitely many" with "effectively listable". The theorems Thue's theorem and Siegel and Faltings bound the number of solutions, not their size, so they never certify a list as complete. Only the theorem Baker's bound and effective Thue equations supplies a computable bound. In particular Faltings does not settle Fermat: for fixed $n \geq 4$ it gives finitely many rational points on $x^{n} + y^{n} = 1$ , and "finitely many" is not "none".

Attempting the $n = 4$ descent without the stronger statement. The descent works for $x^{4} + y^{4} = z^{2}$ , not for $x^{4} + y^{4} = z^{4}$ : starting from the fourth-power version, Step 2 produces $z^{2} = m^{2} + n^{2}$ with $z$ itself a square, and the induction does not close.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter

Introduction

5.1The shape of the problem

5.2Hilbert's tenth problem

5.3Finiteness: how many solutions can there be

5.4Linear equations: when is ax+by=c solvable

5.5The complete solution set

5.6Frobenius: what cannot be represented

5.7Pythagorean triples: the objects

5.8The parametrisation theorem

5.9The same theorem from Z[i]

5.10Pell's equation

5.11Existence: continued fractions and the pigeonhole

5.12Pell solutions as a group of units

5.13The local–global principle

5.14Hilbert symbols: making the check finite

5.15Where the principle fails

5.16Thue's theorem

5.17Approximation: Liouville, Thue, Roth

5.18Effective versions and Baker's method

5.19Thue's theorem and Fermat's equation

5.20Fermat's Last Theorem

5.21The case n=4: infinite descent

5.22The modularity route to the general case

5.4Linear equations: when is $a x + b y = c$ solvable

5.9The same theorem from $Z [i]$

5.21The case $n = 4$ : infinite descent