Euclid's proof of infinitely many primes

(In progress)

Consider any finite list of prime numbers, \(p_1, p_2, \dots , p_n\)

We can construct a new number \(Q\) by multiplying all these primes together and adding 1:

\[ Q = p_1 \cdot p_2 \cdot ... \cdot p_n + 1 \]

Now, there are two possibilities for \(Q\):

1. \(Q\) is prime. In this case, \(Q\) is a new prime number not in our original list.

2. \(Q\) is not prime. If so, then any prime factor of \(Q\) cannot be in our original list. This is because dividing \(Q\) by any of \(p_1, p_2, \dots , p_n\) leaves a remainder of 1. Thus, \(Q\) has a prime factor that is not in our original list.

In either case, we have found a prime not in our original list. This proves that there are infinitely many prime numbers.