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