In mathematics, the method of infinite descent is a proof technique that uses the fact that there are a finite number of positive integers less than any given positive integer. The method relies on the fact that the set of non-negative integers follows the well-ordering principle, so only a finite number of non-negative integers are smaller than any given one. In other words, there is no infinite sequence of strictly decreasing non-negative integers. This intuition can lead to the solution of a lot of challenging problems, particularly in Diophantine equations.
Although Euclid makes use of it in his Elements, the method of infinite descent is attributed to Pierre de Fermat for stating it explicitly. In a letter to Christian Huygens, Fermat claimed infinite descent as his own:
"I have finally organized this according to my method and shown that if a given number is not of this nature there will be a smaller number which also is not, then a third less than the second, etc., to infinity, from which one infers that all numbers are of this nature."
Fermat's method of infinite descent is an offshoot of mathematical induction that can be used to disprove statements. In the metaphor of climbing down a ladder, if a higher rung cannot be reached without first reaching a lower rung coupled with the notion that no lowest rung exists, then no rung can ever be reached.
Let be a positive integer. Suppose that whenever holds for some , there exists a positive integer such that and holds. Then is false for all positive integers .
If there exists an for which was true, one could construct a sequence all of which would be greater than but for the non-negative integers; no such infinite descending sequence exists.
The method of descent has two variants that can be useful especially in the solution of Diophantine equations.
- There is no sequence of non-negative integers
- If the sequence of non-negative integers with satisfies the inequalities then there exists such that
Find all positive integral solutions to the system and .
Adding the equations, we find
The left side is divisible by , and hence so should be the right side. So we have .
Lemma: For we have .
Proof: Notice that the set of quadratic residues mod 7 is . Let and for some . Then we have . But see that we can't choose two elements from so that their sum is divisible by , except for . That means so and as is a prime.
Since we had , we now know that and . So we can write and for some . Subbing in we get which simplifies to . Notice that this is the same equation we started with! So given any solution we can find another solution with . This gives us an infinite decreasing sequence of positive integral solutions, which is not possible. So this system has no solution in positive integers.
Show that is irrational.
Start out by assuming that where and are positive integers that are relatively prime. In a less formal sense, these are the smallest positive integers such that can be represented in this rational form. Now, square both sides: SInce must divide . Hence . Substituting, and hence for some . But then and now note that and must both be smaller then and contradicting the assumption that and are the smallest integers such that can be represented in such a form.
Note that the above proof is informal and a bit vague, but it hopefully illustrates the idea. The above proof should be written in more formal terms and is left to the reader.
FMID may seem confusing at first, so let's see it in action with an example problem. We all know that is an irrational number. We're going to see a proof of it using FMID.
Prove that is irrational
Let's assume the contrary and see what happens. Let where and are positive integers. Cubing and rearranging gives us
Now, this is a Diophantine equation. Finding the solutions to it will give us the denominators and numerators of all the rational numbers that equal . Since the right-hand side is even, it means the left-hand side should be even, too.
In other words, where and . Plugging that in and simplifying gives us
This time the left side is even. So by a similar argument, where and . What happens when we plug this in?
A little simplification gives us something like these:
Looks familiar? Well, it's the same equation we started with. This means if we have a solution , it is possible to find another solution to it.
But by repeating this procedure, we can generate an infinite sequence of strictly decreasing positive integers and that is not possible. This is the key to FMID. You have to show that if one solution exists, there exist infinitely many solutions which are strictly decreasing. That way you're done. Because you can never have an infinite sequence of strictly decreasing, non-negative integers. So, there was never a solution, to begin with.
In our case, the Diophantine equation has no solution in positive integers.
So, can not be equal to where and are positive integers, and that completes our proof.
Now that we've gotten a little hang of what FMID is all about, we can proceed to a more formal formulation of it. But before that, let's get some notations straight.
Let be a property concerning non-negative integers. We use to say that the non-negative integer satisfies property .
For example, let be the property of being divisible by . Then is true, but isn't.
Solve in non-negative integers.
Notice that is a solution. Let be a non-trivial solution. It's not hard to see that are all greater than .
From , it follows that divides . Let where . Plugging that in, we get which simplifies to . By a similar argument, and . Plugging these in and simplifying gives us . This way, we obtain a new solution to our equation with and . But by repeating the procedure, we can construct infinitely many solutions where which contradicts FMID variant--1.
So there can be no other solutions.
Now that we know a bit about the proof method, let's talk about how we can identify FMID. Of course, in many cases, you won't recognize FMID problems straight away. But if you see that after manipulating an equation, you are left with an equation that is quite similar to the one that you started with; then you can think about applying FMID. This is illustrated in the first paragraph of the above example. We didn't have any idea about what to start with at first. So we made substitutions to see if we can advance. But we were then left with an equation identical to the one we started out with. This nudged us to look at the problem from a new perspective and hinted that a nice simple use of FMID will end the problem.
FMID can be used in various instances. Popular uses of this theorem include the non-solvability of which is a general case of Fermat's last theorem for Vieta root jumping is also a proof method relying on infinite descent.
Prove that has no solution when .
Assume that such triples exist. We can further assume that are coprime (if they are not, then cancelling the common factors leaves us with a coprime triplet). Note that and thus is a Pythagorean triplet. . There exist coprime of opposite parity such that Note that the equation gives rise to another Pythagorean triplet and hence with the same restrictions on as . Substituting, Now note that if or then it cannot divide since are coprime. So and are coprime. Hence, and are all perfect squares. Since is a perfect square, and are relatively prime, both and are perfect squares, i. e. As is a perfect square, Recall that and hence , and it is evident that an infinite descent has occured. All that remains is to write up the proof formally from the start.
Note: Why does the result not hold if
Corollary: Fermat's last theorem for