A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. For example, the set of prime numbers begins as

Notice that 1 is not included in this list because it has only one positive divisor (namely, itself), and thus does not meet the definition.

Example

Prove by contradiction that there are infinitely many primes.

Assume for contradiction that there are only finitely many primes, say

Now, define

If Q is prime, then Q is a prime number that is not among the listed primes p1​,p2​,…,pn​ (since Q>pi​ for each i), which contradicts the assumption that all primes have been listed.

If Q is not prime, then it must have a prime divisor, say p, in our finite list. Thus p divides the product p1​⋅p2​⋯pn​:

So

and

for some k,n∈Z.

Thus

Thus, p must also divide the difference

But no prime divides 1. This is a contradiction.

Therefore, there are infinitely many prime numbers. Q.E.D.