Deduction, contradiction and induction
Introducido| English | Significado |
|---|---|
| proof by contradiction/pruːf baɪ ˌkɒntrəˈdɪkʃn/ | A proof that assumes the statement is false and shows that this leads to something impossible. |
A prime with 41 million digits, October 2024
- On 12 October 2024, the Great Internet Mersenne Prime Search confirmed a new largest known prime: $2^{136\,279\,841} - 1$, a number with 41,024,320 digits, found by Luke Durant using cloud GPUs. Nobody expects it to be the last. Euclid's proof by contradiction, from about 300 BC, guarantees that there is always another prime beyond any list.
- Proof by contradiction 反证法 assumes the opposite of the statement and shows that this leads to something impossible.
Euclid's proof, step by step
- Assume there are finitely many primes, $p_1, p_2, \dots, p_k$. Let $N = p_1p_2\cdots p_k + 1$.
- Each $p_i$ divides $p_1\cdots p_k$, so dividing $N$ by $p_i$ leaves remainder 1: no listed prime divides $N$.
Suppose the only primes were 2, 3 and 5. What is Euclid's $N$?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$2 \times 3 \times 5 + 1$.
What remainder does $N = 2 \times 3 \times 5 \times 7 + 1$ leave on division by 7?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
7 divides the product exactly.
Reaching the contradiction
- $N > 1$, so $N$ has at least one prime factor — and that factor is not in the list.
- This contradicts "the list contains every prime", so there are infinitely many primes.
Deduction, contradiction and induction
A deductive proof starts from stated definitions or assumptions
Distinguish a proof for all integers from one counterexample.
Put Euclid's argument in order.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Assume, build, divide, contradict.
Worked example: $\sqrt{3}$ is irrational
Prove that $\sqrt{3}$ is irrational.
- Assume: $\sqrt{3} = \dfrac{p}{q}$ in lowest terms, so $p^2 = 3q^2$. Then 3 divides $p^2$, so 3 divides $p$ (3 is prime): $p = 3m$.
- Continue: $9m^2 = 3q^2$, so $q^2 = 3m^2$, and 3 divides $q$.
- Contradiction: 3 divides both $p$ and $q$, but $\tfrac{p}{q}$ was in lowest terms. So $\sqrt{3}$ is irrational.
In the proof that $\sqrt{3}$ is irrational, which fact justifies "3 divides $p^2$, so 3 divides $p$"?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
A prime dividing a product divides a factor.
Why "lowest terms" matters
- Every rational number can be written with no common factor, so the assumption loses nothing.
- Without it, finding a common factor would not contradict anything.
Why does the $\sqrt{3}$ proof assume $\tfrac{p}{q}$ is in lowest terms?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The contradiction is the common factor.
Writing it up
- State the assumption clearly ("Assume, for contradiction, that…"), argue to the impossibility, then name the contradiction.
- End with a sentence that states what has been proved.
$N = p_1p_2\cdots p_k + 1$ need not be prime itself. $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509$. The proof only needs $N$ to have a prime factor outside the list.
Euclid's proof shows that $p_1p_2\cdots p_k + 1$ is always prime.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
30031 = 59 × 509.
To prove by contradiction, assume the opposite, deduce carefully, and reach an impossibility. For infinitely many primes, the product of the list plus one has a prime factor not on the list. For $\sqrt{n}$ irrational, write $\tfrac{p}{q}$ in lowest terms and show both share a factor.
Prove by contradiction that there is no greatest odd integer.
A short proof by contradiction.