Table of Contents
1 Proof there is infinite number of primes
Proof by contradition (Assume there are finite number of primes)
- Assume there are \(k\) primes and let \( p_1, p_2, \dots p_k \) are all prime numbers
- let \( n = p_1 p_2 \dots p_k + 1 \), then \(n\) is not a prime, otherwise there is \(k + 1\) primes
- \( \Rightarrow n - p_1 p_2 \dots p_k = 1 \)
- let p is a prime and \( p \mid n \) \(\because\) n is not a prime there exists \(p\) such as \( p \mid n \)
- left side must be an integer becase of \( p \mid n \) and \( p \mid p_1 p_2 \dots p_k \)
- but right side is NOT an integer.
- The contradition implies our assumption is False \(\square\)