Proof by infinite descent

In mathematics, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of proof by contradiction^[1] used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold for a number, then the same would be true for a smaller number, leading to an infinite descent and ultimately a contradiction.^[2] It is a method which relies on the well-ordering principle, and is often used to show that a given equation, such as a Diophantine equation, has no solutions.^[3][4]

Typically, one shows that if a solution to a problem existed, which in some sense was related to one or more natural numbers, it would necessarily imply that a second solution existed, which was related to one or more 'smaller' natural numbers. This in turn would imply a third solution related to smaller natural numbers, implying a fourth solution, therefore a fifth solution, and so on. However, there cannot be an infinity of ever-smaller natural numbers, and therefore by mathematical induction, the original premise—that any solution exists—is incorrect: its correctness produces a contradiction.

An alternative way to express this is to assume one or more solutions or examples exists, from which a smallest solution or example—a minimal counterexample—can then be inferred. Once there, one would try to prove that if a smallest solution exists, then it must imply the existence of a smaller solution (in some sense), which again proves that the existence of any solution would lead to a contradiction.

The earliest uses of the method of infinite descent appear in Euclid's Elements.^[3] A typical example is Proposition 31 of Book 7, in which Euclid proves that every composite integer is divided (in Euclid's terminology "measured") by some prime number.^[2]

The method was much later developed by Fermat, who coined the term and often used it for Diophantine equations.^[4][5] Two typical examples are showing the non-solvability of the Diophantine equation ${\displaystyle r^{2}+s^{4}=t^{4}}$ and proving Fermat's theorem on sums of two squares, which states that an odd prime p can be expressed as a sum of two squares when ${\displaystyle p\equiv 1{\pmod {4}}}$ (see Modular arithmetic and proof by infinite descent). In this way Fermat was able to show the non-existence of solutions in many cases of Diophantine equations of classical interest (for example, the problem of four perfect squares in arithmetic progression).

In some cases, to the modern eye, his "method of infinite descent" is an exploitation of the inversion of the doubling function for rational points on an elliptic curve E. The context is of a hypothetical non-trivial rational point on E. Doubling a point on E roughly doubles the length of the numbers required to write it (as number of digits), so that "halving" a point gives a rational with smaller terms. Since the terms are positive, they cannot decrease forever.