Deduction, contradiction and induction
Introduzido| 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$?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
$2 \times 3 \times 5 + 1$.
What remainder does $N = 2 \times 3 \times 5 \times 7 + 1$ leave on division by 7?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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$"?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.