Well-Ordering and Infinite Descent

In one sentence

The well-ordering principle: every non-empty set of positive integers has a smallest element.

Put another way, this is infinite descent: there is no infinite strictly decreasing sequence of positive integers $n_{1} > n_{2} > n_{3} > \dots$ . So to prove that something does not exist, you can:

Assume it exists and attach a positive integer to it (a denominator $q$ , say); take the one for which this integer is smallest.
From it, build another one whose attached integer is even smaller.
This contradicts “smallest”. In other words, a staircase cannot go down forever.

The well-ordering principle and induction are two sides of the same coin. If $P (n)$ is not true for every $n$ , take the smallest counterexample $n_{0}$ . Since $P (1)$ holds, $n_{0} > 1$ ; then $P (n_{0} - 1)$ holds but does not give $P (n_{0})$ , which contradicts the inductive step.

Example: √2 is irrational

Step 1 / 4

Assume a solution exists
If $2 = \frac{p}{q}$ (with $p, q$ positive integers), then $p^{2} = 2 q^{2}$ . Among all such fractions, take the one with the smallest denominator $q$ .

$p^{2} = 2 q^{2}, q smallest$
Build a new one
Smaller, and still positive
Contradiction

Predict first

Apply the machine $(p, q) \mapsto (2 q - p, p - q)$ to $(99, 70)$ . What is the next step?

(41, 29)

(29, 41)

(58, 41)

(70, 29)

Choose an answer first; then you can see the result.

Stop 1 · Irrational numbers: replace 2 by another d

The same machine works for any $d$ that is not a perfect square. Take $a = ⌊ d ⌋$ and let

p^{'} = d q - a p, q^{'} = p - a q .

Expanding gives $p^{'2} - d q^{'2} = (a^{2} - d) (p^{2} - d q^{2})$ , and $a < d < a + 1$ guarantees $0 < q^{'} < q$ . So $p^{2} = d q^{2}$ has no positive integer solution, and $d$ is irrational. Try setting $d$ to $3$ , $5$ or $7$ in the figure at the top of the page.

Stop 2 · Diophantine equations

The equation $x^{2} + y^{2} = 3 z^{2}$ has no positive integer solution. This time the descending quantity is $z$ , and the tool for building a smaller solution is remainders.

Example: x² + y² = 3z²

Step 1 / 4

Take the smallest solution
Suppose there is a positive integer solution, and take the one $(x, y, z)$ with the smallest $z$ .

$x^{2} + y^{2} = 3 z^{2}$
Look mod 3
Substitute back
A smaller solution

Stop 3 · The smallest counterexample

You do not always have to “build a smaller solution”. Sometimes it is enough to look hard at the smallest object: its properties give the answer by themselves.

Example: every integer greater than 1 has a prime factor

Step 1 / 3

The set is not empty
The divisors of $n > 1$ that are greater than $1$ form a set. It contains at least $n$ itself, so it is not empty.

${d : d ∣ n, d > 1} ∋ n$
Take the smallest
It must be prime

If d is a perfect square

Break it

Counterexample lab: remove one condition

Conclusion: $p^{2} = d q^{2}$ has no positive integer solution

$d = 3$ : start from $(26, 15)$ (where $2 6^{2} - 3 \cdot 1 5^{2} = 1$ ). Every step satisfies $1 < p / q < 2$ , and $q$ keeps getting smaller until it drops out of the positive integers.

Practice

Exercise 1Basic

Start from $(41, 29)$ and apply $(p, q) \mapsto (2 q - p, p - q)$ again and again. After how many steps does $q$ first become $0$ ?

Exercise 2Basic

Use infinite descent to prove that $3$ is irrational.

Exercise 3Advanced

Prove that the equation $x^{3} + 2 y^{3} = 4 z^{3}$ has no positive integer solution.

Exercise 4Challenge

(IMO 1988) Positive integers $a, b$ are such that $ab + 1$ divides $a^{2} + b^{2}$ . One can prove that the quotient $k = \frac{a ^{2} + b ^{2}}{ab + 1}$ is always a perfect square. First compute $k$ for $a = 8, b = 30$ , then try to explain why using descent.

In one sentence

Example: √2 is irrational

Stop 1 · Irrational numbers: replace 2 by another d

Stop 2 · Diophantine equations

Example: x² + y² = 3z²

Stop 3 · The smallest counterexample

Example: every integer greater than 1 has a prime factor

If d is a perfect square

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

Descending where there is no smallest element