Proof By Contradiction

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

To prove Statement P is true:

First assume the inverse of statement P to be true and show that this leads to two conflicting statements

(a) Statement R is true and (b) Statement R is false.

This is a contradiction, therefore the original statement P must be true.

Discussion

One proof of the Infinity of Prime Numbers uses proof by contradiction.

Assume that there exist a finite number of primes $p_1,p_2,p_3,...,p_n$

That is to say that every number greater than $P_n$ is a multiple of at least one of the numbers $p_1,p_2,p_3,...,p_n$

Consider the number $N=p_1.p_2.p_3...p_n$ + 1

Now N > $P_n$ and N is not divisible by any of the primes $p_1,p_2,p_3,...,p_n$ as the remainder is always 1.

This is a contradiction, therefore the initial assumption that there exists a finite number of primes must be wrong.

Please note: This does not mean that N is prime as there may exist a prime between $P_n$ and N which divides N.