Irrational roots and infinitely many primes
Introduit| English | Sens |
|---|---|
| proof by contradiction/pruːf baɪ ˌkɒntrəˈdɪkʃn/ | démonstration par l'absurde |
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$?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
$2 \times 3 \times 5 + 1$.
What remainder does $N = 2 \times 3 \times 5 \times 7 + 1$ leave on division by 7?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Irrational roots and infinitely many primes
To prove √2 irrational, assume √2=p/q for coprime integers p,q with q nonzero
Classify each argument and explain the condition that makes it valid or incomplete.
Put Euclid's argument in order.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
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$"?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.