Irrational roots and infinitely many primes
引入| English | 释义 | 拼音 |
|---|---|---|
| proof by contradiction/pruːf baɪ ˌkɒntrəˈdɪkʃn/ | 反证法 | fǎn zhèng fǎ |
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$?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$2 \times 3 \times 5 + 1$.
What remainder does $N = 2 \times 3 \times 5 \times 7 + 1$ leave on division by 7?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
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.
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
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$"?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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.