Proof By ContradictionYou are currentlybrowsing as guest. Click here to log in 

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.
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.
Last change to this page Full Page history Links to this page 
Edit this page (with sufficient authority) Change password 
Recent changes All pages Search 