Main Index Foundation of mathematics Relations
 Subject Index
comment on the page

Infinite descent

The main idea of infinite descent is: If the existence of a given positive integer possessing certain properties implies that there exists a smaller one with these properties, then there are infinitely many of such numbers, which is impossible.

Fermat invented this method of infinite descent and used it mainly in Diophantine equations: Assuming a solution exists, he showed that another smaller also exists what is impossible, and therefore no such initial solution could exist.

A proof by infinite descent is a particular kind of proof by contradiction which relies on the fact that the natural numbers are well ordered .

For instance Euclid in Proposition 31 of Book VII of his Elements states   :

Any composite number is measured by some prime number.

We would reformulate this as follows:

Theorem. Every positive integer is divisible by at least one prime number.  

Euclid’s idea of the proof very natural. If is prime, the proof is done. If is composite, it is divisible an integer, say , such that . If is a prime the proof again stops. If not is divisible by a such that , etc. The only problem is that Euclid does not explain why this process must stop. Clearly, the last number in this sequence of divisors is prime. If not, then ...

Actually we can prove a more precise result:

Lemma. The smallest divisor of any positive integer is a prime.

If is not a prime, then with , and both are divisors of , what contradicts the choice of divisor .

Cite this web-page as: