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\)