Prove It!

We can prove there are infintely many primes by contradiction. If there were finitely primes, let be $P$ be the complete set of primes, containing $n$ members.

Then ${p_1, p_2, p_3, p_4 \cdots p_{n-1}, p_n} \in P$

Now we can multiply all the members of the set and add 1:

$Q = p_1p_2p_3p_4p_5\cdots p_n +1$

We do not know whether Q is prime or composite but we can make deductions on either case:

Case 1: Q is composite:

If Q is composite, then it must have at least 2 prime factors but none of its prime factors are in the complete set of primes $P$ :

$Q \equiv 1(mod p_1)$

$Q \equiv 1(mod p_2)$

$Q \equiv 1(mod p_3)$

$Q \equiv 1(mod p_4)$

$\vdots$

$Q \equiv 1(mod p_n)$

So there must be a new prime number that is a prime factor of Q which should be added to the set P.

Case 2: Q is prime:

Obviously the set of primes is incomplete if we have found a new prime Q, therefore Q must be added to set P.

Therefore by contradiction, there is no such set $P$ that contains all the prime numbers since it can always be expanded.

Since this process can be repeated in a cycle to the new set P, then there are infinitely many primes and the set $P$ is infinitely large.