Most recent change of ProofByContradiction

Edit made on July 07, 2011 by JoCSibley at 21:12:30

Deleted text in red / Inserted text in green

Proof by contradiction normally follows this strategy.

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 EQN:p_1,p_2,p_3,...,p_n

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

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

Now N > EQN:P_n and N is not divisible by any of the primes EQN: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 EQN:P_n and N which divides N.