Proof by infinite descent
Tonight's idea
A list of positive whole numbers cannot keep getting smaller for ever. Start at 50 and you have at most 49 steps down. That plain fact is a method of proof.
Infinite descent. Suppose a solution in positive whole numbers exists. Show how to build a strictly smaller one. The same recipe then gives a smaller one again, without end. That cannot happen, so there was no solution.
Pierre de Fermat named the method. Try it on \(\sqrt2\). If \(\sqrt2\) were a fraction \(a/b\), then \(a^2 = 2b^2\) with \(a\), \(b\) positive whole numbers. The right side is even, so \(a\) is even (an odd number has an odd square). Write \(a = 2k\). Then \(4k^2 = 2b^2\), so
\[b^2 = 2k^2.\]
So \((b, k)\) solves the same equation as \((a, b)\). And \(b \lt a\), because \(a^2 = 2b^2 > b^2\). From any solution we have made a smaller one, so we get \(a > b > k > \dots\), an endless falling list of positive whole numbers. No such list exists. So \(a^2 = 2b^2\) has no solution, and \(\sqrt2\) is not a fraction.
Grade 10's Proof by contradiction proved this by assuming lowest terms. Descent needs no such assumption.
Watch one: \(a^2 + b^2 = 3c^2\)
Claim: the only whole-number solution is \(a = b = c = 0\). The tool is exercise 1: a square leaves remainder 0 or 1 on division by 3, and remainder 0 only if the number itself is a multiple of 3.
Suppose there is a solution that is not all zeros. Squaring hides signs, so take \(a, b, c \ge 0\). Then \(c \ge 1\), since \(c = 0\) would force \(a^2 + b^2 = 0\) and so \(a = b = 0\).
Now \(a^2 + b^2\) is a multiple of 3. The two remainders are each 0 or 1, and \(0 + 1\) and \(1 + 1\) are not multiples of 3. So both are 0: \(a = 3A\) and \(b = 3B\). Substitute:
\[9A^2 + 9B^2 = 3c^2 \quad\Longrightarrow\quad c^2 = 3(A^2 + B^2).\]
So \(c^2\) is a multiple of 3, hence \(c = 3C\). Divide by 9: \(A^2 + B^2 = 3C^2\). A new solution, with \(C = c/3\) a whole number and \(1 \le C \lt c\). Repeat, and \(c\) falls for ever.
Your turn
- Every whole number is \(3k\), \(3k + 1\) or \(3k - 1\). Square each. Show that the remainder on division by 3 is 0 or 1, and is 0 only for \(3k\).
- Show that \(a^3 = 2b^3\) has no solution in positive whole numbers. (Show \(a = 2k\), then \(b = 2m\), and find a smaller solution.) What does this say about \(\sqrt[3]{2}\)?
- Show that the only whole-number solution of \(x^3 + 2y^3 = 4z^3\) is \(x = y = z = 0\). Start by showing \(x\) is even.
- Find positive whole numbers with \(a^2 + b^2 = 5c^2\). So descent must fail here. Which step of the proof for \(3c^2\) breaks when 3 becomes 5?
Stretch: descent without odd and even
Suppose \(a^2 = 2b^2\) with \(a\), \(b\) positive whole numbers. Show that \((2b - a)^2 = 2(a - b)^2\), and that \(0 \lt a - b \lt b\). Why does that prove \(\sqrt2\) is irrational?
Answers
- \((3k)^2 = 9k^2\), remainder 0. \((3k \pm 1)^2 = 9k^2 \pm 6k + 1 = 3(3k^2 \pm 2k) + 1\), remainder 1. So remainder 0 happens only for multiples of 3, and remainder 2 never happens.
- \(2b^3\) is even, so \(a^3\) is even, so \(a\) is even (an odd number has an odd cube): \(a = 2k\). Then \(8k^3 = 2b^3\), so \(b^3 = 4k^3\), so \(b\) is even: \(b = 2m\). Then \(8m^3 = 4k^3\), so \(k^3 = 2m^3\). So \((k, m)\) is a solution in positive whole numbers with \(k = a/2 \lt a\). Descent: no solution exists. So \(\sqrt[3]{2}\) is not a fraction \(a/b\); it is irrational.
- \(x^3 = 4z^3 - 2y^3\) is even, so \(x = 2X\). Then \(8X^3 + 2y^3 = 4z^3\), so \(y^3 = 2z^3 - 4X^3\) is even and \(y = 2Y\). Then \(8X^3 + 16Y^3 = 4z^3\), so \(z^3 = 2X^3 + 4Y^3\) is even and \(z = 2Z\). Divide \(8X^3 + 16Y^3 = 32Z^3\) by 8: \(X^3 + 2Y^3 = 4Z^3\). So halving a solution gives a solution in whole numbers. If the solution were not all zeros, \(|x| + |y| + |z|\) would be a positive whole number that halves every round, for ever. Impossible, so \(x = y = z = 0\).
- \(1^2 + 2^2 = 5 \times 1^2\). On division by 5 a square leaves remainder 0, 1 or 4, and \(1 + 4 = 5\). So \(a^2 + b^2\) can be a multiple of 5 without \(a\) and \(b\) being multiples of 5. The step "both remainders are 0" fails, and nothing can be divided out.
Stretch. \((2b - a)^2 = 4b^2 - 4ab + a^2 = 6b^2 - 4ab\), using \(a^2 = 2b^2\). And \(2(a - b)^2 = 2a^2 - 4ab + 2b^2 = 6b^2 - 4ab\). Equal. Since \(b^2 \lt a^2 = 2b^2 \lt 4b^2\), we have \(b \lt a \lt 2b\), so \(0 \lt a - b \lt b\) and \(2b - a > 0\). So \((2b - a,\ a - b)\) is a solution in positive whole numbers with a smaller second number. Descent again: no solution can exist.