The concept of proof by contradiction refers to taking a statement and assuming the opposite is true. When assuming the opposite is true we begin to further examine the our ‘opposite’ statement and reach to a conclusion which doesn’t add up or in simple terms is absurd.

Take the case:

Statement: There are infinite number of prime numbers.

Using the concept of proof by contradiction, we will assume the opposite is true.

If an integer (2) divides an integer (6) we say that 2 divides 6 or 2|6. In a more general sense we can say that if any integer ‘a’ divides any other integer ‘b’ then a|b.

Prime numbers: it is an integer (n ≥ 2) that has exactly two positive factors (1 and itself).

eg. 2, 3, 5 …

Composite numbers: it is an integer (n ≥ 2) that has more than two positive factors.

eg. 4, 6, 8 …

Fundamental Theorem of Arithmetic: Every integer n ≥ 2 has a unique (exactly one) prime factorization.

eg: 12 = 2 ∙ 2 ∙ 3  ∴ The prime factorization of 12 is two 2’s and one 3 (order doesn’t matter)

Suppose there are finite number of prime numbers.

Our list of primes includes: P₁ P₂ … P_k (With k being the last of them).

Let N be a common multiple with all these primes plus 1.

∴ N = P₁ P₂ … P_k  + 1

We claim that N is a prime, because when we divide N by P_i (any prime in the list till P_k ) we get a remainder of 1. If it were a composite number then one prime should have divided N.

To further explain carefully we take a look at our examples above of 12.

12 = 2 ∙ 2 ∙ 3 which is saying 12 = 2 ∙ 2 ∙ 3 + 0 thus it being a composite.

However in this case any prime dividing N gives a remainder of 1 which means that P₁∤N (∤ means does not divide). This means that N is a prime. But we have said that we have a list of primes above which go up to P_k but now we are saying that N is also a prime. This is a contradiction (or absurd) as we just found another prime.

This proof shows that there are infinite number of prime as we proved that it can’t be finite.

Image Credit: Vagabomb.com