Fermat's Method of Infinite Descent

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 $m$ be a positive integer. Suppose that whenever $P(m)$ holds for some $m>k$, there exists a positive integer $j$ such that $m>j>k$ and $P(j)$ holds. Then $P(n)$ is false for all positive integers $n$.

$\textbf{Intuition:}$ If there exists an $n$ for which $P(n)$ was true, one could construct a sequence $n > n_1 > n_2 > \cdots$ all of which would be greater than $k$ 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.

1. There is no sequence of non-negative integers $n_1 > n_2 > \cdots .$
2. If the sequence of non-negative integers $n_i$ with $1 \le i$ satisfies the inequalities $n_1 ≥ n_2 ≥ \cdots,$ then there exists $i$ such that $n_i = n_{i+1} = \cdots.$

Find all positive integral solutions to the system $a^2+6b^2=p^2$ and $b^2+6a^2=q^2$.

---

Adding the equations, we find $7\left(a^2+b^2\right)=p^2+q^2.\qquad (1)$
The left side is divisible by $7$, and hence so should be the right side. So we have $7 \big| p^2+q^2$.

Lemma: For $(x,y)\in\mathbb{N}^2$ we have $7\big| x^2+y^2\Longleftrightarrow 7\big| x, ~7\big| y$.

Proof: Notice that the set of quadratic residues mod 7 is $Q=\{0,1,2,4\}$. Let $x^2\equiv s$ and $y^2\equiv t\pmod 7$ for some $s,t\in Q$. Then we have $x^2+y^2\equiv s+t\equiv 0\pmod 7$. But see that we can't choose two elements from $Q$ so that their sum is divisible by $7$, except for $s=t=0$. That means $x^2\equiv y^2\equiv 0\pmod 7,$ so $7\big| x$ and $7\big| y$ as $7$ is a prime. $_\square$

Since we had $7\big| p^2+q^2$, we now know that $7\big| p$ and $7\big| q$. So we can write $p=7p_1$ and $q=7q_1$ for some $\left(p_1,q_1\right)\in\mathbb{N}^2$. Subbing in $(1),$ we get $7\left(a^2+b^2\right)=\left(7p_1\right)^2+\left(7q_1\right)^2,$ which simplifies to $a^2+b^2=7\left(p_1^2+q_1^2\right)$. Notice that this is the same equation we started with! So given any solution $(a,b,p,q),$ we can find another solution $\left(p_1,q_1,a,b\right)$ with $p_1 < p, ~ q_1 < q$. This gives us an infinite decreasing sequence of positive integral solutions, which is not possible. So this system has no solution in positive integers. $_\square$

Show that $\sqrt{2}$ is irrational.

---

Start out by assuming that $\sqrt{2}=\frac pq,$ where $p$ and $q$ are positive integers that are relatively prime. In a less formal sense, these are the smallest positive integers such that $\sqrt{2}$ can be represented in this rational form. Now, square both sides: $$2=\dfrac{p^2}{q^2}\implies 2q^2=p^2.$$ SInce $\gcd(p, q)=1,$ $2$ must divide $p$. Hence $p=2P$. Substituting, $$2q^2=(2P)^2\implies q^2=2P^2,$$ and hence $q=2Q$ for some $Q$. But then $\frac{p}{q}=\frac{2P}{2Q}=\frac{P}{Q},$ and now note that $P$ and $Q$ must both be smaller then $p$ and $q,$ contradicting the assumption that $p$ and $q$ are the smallest integers such that $\sqrt2$ can be represented in such a form. $_\square$

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 $\sqrt[3]{2}$ is an irrational number. We're going to see a proof of it using FMID.

Prove that $\sqrt[3]{2}$ is irrational

----

Let's assume the contrary and see what happens. Let $\sqrt[3]{2}=\frac{x_1}{y_1},$ where $x_1$ and $y_1$ are positive integers. Cubing and rearranging gives us

$${x_1}^3=2{y_1}^3.$$

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 $\sqrt[3]{2}$. Since the right-hand side is even, it means the left-hand side should be even, too.

In other words, $x_1=2x_2,$ where $x_2 \in \mathbb{Z}_+$ and $x_1>x_2$. Plugging that in and simplifying gives us

$$4{x_2}^3={y_1}^3.$$

This time the left side is even. So by a similar argument, $y_1=2y_2,$ where $y_2\in \mathbb{Z}_+$ and $y_1>y_2$. What happens when we plug this in?

A little simplification gives us something like these:

$${x_2}^3=2{y_2}^3.$$

Looks familiar? Well, it's the same equation we started with. This means if we have a solution $(x_1, y_1)$, it is possible to find another solution $(x_2, y_2)$ to it.

But by repeating this procedure, we can generate an infinite sequence of strictly decreasing positive integers $x_1>x_2>x_3>\cdots,$ 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 ${x_1}^3=2{y_1}^3$ has no solution in positive integers.

So, $\sqrt[3]{2}$ can not be equal to $\frac{x}{y},$ where $x$ and $y$ are positive integers, and that completes our proof. $_\square$

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 $P$ be a property concerning non-negative integers. We use $P(n)$ to say that the non-negative integer $n$ satisfies property $P$.

For example, let $P$ be the property of being divisible by $3$. Then $P(15)$ is true, but $P(13)$ isn't.

Solve $x^3+2y^3=4z^3$ in non-negative integers.

----
Notice that $(0, 0, 0)$ is a solution. Let $(x_1, y_1, z_1)$ be a non-trivial solution. It's not hard to see that $x_1, y_1, z_1$ are all greater than $0$.

From ${x_1}^3+2{y_1}^3=4{z_1}^3$, it follows that $2$ divides $x_1$. Let $x_1=2x_2,$ where $x_2 \in \mathbb{Z}_+$. Plugging that in, we get $8{x_2}^3+ 2{y_1}^3=4{z_1}^3,$ which simplifies to $4{x_2}^3+ {y_1}^3=2{z_1}^3$. By a similar argument, $y_1=2y_2$ and $z_1=2z_2$. Plugging these in and simplifying gives us ${x_2}^3+ 2{y_2}^3=4{z_2}^3$. This way, we obtain a new solution $(x_2, y_2, z_2)$ to our equation with $x_1>x_2, y_1>y_2,$ and $z_1>z_2$. But by repeating the procedure, we can construct infinitely many solutions $(x_i, y_i, z_i),$ where $x_1>x_2>x_3>\cdots,$ which contradicts FMID variant--1.

So there can be no other solutions. $_\square$

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 $x^4+y^4=z^2$ $($which is a general case of Fermat's last theorem for $n=4).$ Vieta root jumping is also a proof method relying on infinite descent.

Prove that $x^4+y^4=z^2$ has no solution when $xyz\neq 0$.

---

Assume that such triples exist. We can further assume that $x^2, y^2, z$ are coprime (if they are not, then cancelling the common factors leaves us with a coprime triplet). Note that $x^4+y^4=z^2=\big(x^2\big)^2+\big(y^2\big)^2=z^2$ and thus $\big(x^2, y^2, z\big)$ is a Pythagorean triplet. . There exist coprime $p, q$ of opposite parity such that $$\begin{aligned} x^2&=2pq\\ y^2&=p^2-q^2\\ z&=p^2+q^2. \end{aligned}$$ Note that the equation $$y^2=p^2-q^2$$ gives rise to another Pythagorean triplet and hence $$\begin{aligned} q&=2ab\\ y&=a^2-b^2\\ p&=a^2+b^2 \end{aligned}$$ with the same restrictions on $a, b$ as $p, q$. Substituting,$$x^2=2pq=4ab\big(a^2+b^2\big).$$ Now note that if $p\mid a$ or $p\mid b,$ then it cannot divide $a^2+b^2$ since $a, b$ are coprime. So $a^2+b^2$ and $ab$ are coprime. Hence, $ab$ and $a^2+b^2$ are all perfect squares. Since $ab$ is a perfect square, and $a, b$ are relatively prime, both $a$ and $b$ are perfect squares, i. e. $a=A^2, b=B^2.$ As $a^2+b^2$ is a perfect square, $$P^2=a^2+b^2=A^4+B^4.$$ Recall that $P^2=a^2+b^2=p<p^2+q^2=z$ and hence $P<z$, and it is evident that an infinite descent has occured. All that remains is to write up the proof formally from the start. $_\square$

Note: Why does the result not hold if $xyz=0?$

Corollary: Fermat's last theorem for $n=4k.$