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_{1} P_{2} … P_{k} (With k being the last of them).

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

∴ N = P_{1} P_{2} … 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_{1}∤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

## Leave a Reply