- #1

- 19,446

- 25,378

No, sorry kids, not Pythagoras. Euclid's (##\approx 300\, BC##) proof about the number of primes.

For any finite set ##\{p_1,\ldots,p_r\}## of primes, consider the number ##n = p_1p_2 \cdots p_r + 1.## This ##n## has a prime divisor ##p##. But ##p## is not one of the ##p_k## : otherwise ##p## would be a divisor of ##n## and of the product ##p_1p_2 \cdots p_r##, and thus also of the difference ##n − p_1p_2 \cdots p_r = 1,## which is impossible. So a finite set ##\{p_1,\ldots,p_r\}## cannot be the collection of all prime numbers.

Can you phrase the statement which is proven, and rephrase this proof, such that

- it is clearly an indirect proof
- it is clearly a proof by contradiction

Can you find all the hidden assumptions in the above proof?

Hint: There are many.