Chapter

Infinite Descent

Infinite descent, parity lemmas, minimal counterexamples, primitive solutions, and contradiction by smaller solutions.

Back to Course Practice Ladders
Theory Examples Practice Ladders

Theory

1. The Main Idea

Infinite descent is a proof method. We assume that a positive integer solution exists, then construct a smaller positive integer solution of the same type. Repeating this forever is impossible, because positive integers cannot decrease forever.

The typical structure is:

  1. Assume a solution exists.
  2. Choose one with a smallest positive measure.
  3. Prove that this solution forces a smaller solution.
  4. Contradiction.

2. Descent and Parity

Many descent arguments begin with parity. If \(x^2\) is even, then \(x\) is even. This can force both variables to be divisible by \(2\), creating a smaller solution after division.

3. Example: \(x^2=2y^2\)

Suppose \(x^2=2y^2\) has a nonzero integer solution. Then \(x^2\) is even, so \(x=2k\). Substituting:

\[ 4k^2=2y^2,\qquad y^2=2k^2. \]

So \(y\) is even too. Thus both \(x\) and \(y\) are even, and dividing by \(2\) gives a smaller solution. Repeating is impossible. Therefore the only integer solution is \((0,0)\).

4. Minimal Counterexample

Often we assume a smallest counterexample. If the argument creates a smaller counterexample, the original one could not have existed.

5. Descent in Olympiad Problems

Descent usually appears when:

  • an equation forces all variables to share a factor;
  • a minimal solution can be transformed into a smaller one;
  • parity or modular residues repeat after scaling;
  • a "smallest" object produces an even smaller object.

Examples

Example 1. Even Square

This lemma is used repeatedly in descent arguments.

Problem. Prove that if \(n^2\) is even, then \(n\) is even.
Solution. If \(n\) is odd, then \(n=2k+1\). Hence \(n^2=4k^2+4k+1\), which is odd. Therefore if \(n^2\) is even, \(n\) cannot be odd, so \(n\) is even.

Example 2. First Descent

This is the model descent proof for the whole module.

Problem. Show that the only integer solution of \(x^2=2y^2\) is \((0,0)\).
Solution. Suppose a nonzero solution exists. Since \(x^2=2y^2\), \(x^2\) is even, so \(x=2k\). Then \(4k^2=2y^2\), hence \(y^2=2k^2\), so \(y\) is even. Thus both \(x\) and \(y\) are even, and dividing by \(2\) gives a smaller nonzero solution. Repeating forever is impossible. Hence only \((0,0)\) works.

Example 3. Irrational Square Root

Make explicit that lowest terms means not both even.

Problem. Use infinite descent to prove that \(\sqrt2\) is irrational.
Solution. If \(\sqrt2=a/b\), then \(a^2=2b^2\). By the previous descent idea, \(a\) and \(b\) must both be even. This contradicts the assumption that the fraction was in lowest terms. Therefore \(\sqrt2\) is irrational.

Example 4. Descent by Three

Use this to generalize the \(2\)-descent idea.

Problem. Prove that the only integer solution of \(x^2=3y^2\) is \((0,0)\).
Solution. If \(x^2=3y^2\), then \(3\mid x^2\), so \(3\mid x\). Write \(x=3k\). Then \(9k^2=3y^2\), so \(y^2=3k^2\), hence \(3\mid y\). Dividing both variables by \(3\) gives a smaller nonzero solution, impossible by descent. Thus only \((0,0)\) works.

Example 5. No Sum of Squares

This is the first three-variable descent in the course.

Problem. Prove that the only integer solution of \(x^2+y^2=3z^2\) is \((0,0,0)\).
Solution. Modulo \(3\), the right side is \(0\). Since square residues are \(0\) and \(1\), the only way \(x^2+y^2\equiv0\pmod3\) is \(x^2\equiv y^2\equiv0\pmod3\). Thus \(3\mid x\) and \(3\mid y\). Then the equation gives \(3\mid z\) as well. Dividing all variables by \(3\) gives a smaller nonzero solution, impossible by descent. Hence only \((0,0,0)\) works.

Example 6. Minimal Counterexample

This is the logic foundation behind the method.

Problem. Explain why there cannot be a nonempty set of positive integers with no smallest element.
Solution. The positive integers are well ordered: every nonempty set of positive integers has a smallest element. Infinite descent uses the contrapositive spirit: if every supposed element produces a smaller positive element, no such set can exist.

Example 7. Descent Chain

This abstract problem helps students name the proof skeleton.

Problem. Suppose a positive integer \(n\) has a property \(P\), and every positive integer with property \(P\) gives a smaller positive integer with property \(P\). Prove that no positive integer has property \(P\).
Solution. If such integers exist, choose the smallest one, say \(n\). By the property, \(n\) gives a smaller positive integer with property \(P\), contradicting the minimality of \(n\). Therefore no positive integer has property \(P\).

Example 8. Divisible by All Powers

This justifies the phrase divisible by arbitrarily large powers.

Problem. Prove that if an integer \(n\) is divisible by \(2^k\) for every positive integer \(k\), then \(n=0\).
Solution. If \(n\ne0\), choose \(k\) with \(2^k>|n|\). A nonzero multiple of \(2^k\) has absolute value at least \(2^k\), impossible because \(|n|<2^k\). Thus \(n=0\).

Problems

Problems

No published problems are available yet.

Ladders

No published ladders were found.
Previous Chapter
Next Chapter