Archive

Posts Tagged ‘contradiction’

Proof by Contradiction

The aim of proof by contradiction is to prove a statement is true by assuming it is false and showing that this leads to a contradiction so that the statement must be true. This is often easier than proving the statement directly.

For example consider the proof √2 is irrational that follows

Assume root 2 is rational, ie that it can be written as r/s where s≠0 and r and s are both integers. We can choose r and s such that they have no common factors, since any common factors can be cancelled out.

then 2=r2/s2
so r2 = 2s2 —(1)
hence 2 is a factor of r2 and since 2 is prime 2 must also be a factor of r so we can write r = 2k where k is an integer.

From (1) we can now write
4k2=2s2
so s = 2k2
so 2 is also a factor of s
But we assumed r and s had no common factors, Contradiction therefore root 2 must be irrational.

So to conclude, here we have taken the statement root 2 is irrational, assumed it to be false, shown this leads to a contradiction and therefore concluded that root 2 must be irrational.

Advertisements
Categories: maths Tags: , , ,

Proof there are infinitley many prime numbers

Introduction

Prime numbers are natural numbers (1,2,3 etc) whose only factors are one and themselves. The first few primes are:

2,3,5,7,11,13……

note that 1 isn’t a prime.

Primes are important because every number can be written uniquely as a product of primes. This idea can also be used to prove that there infinitely many primes. The proof which follows is an example of proof by contradiction.

Proof

Assume that there are a finite number of primes.

Then all these primes can be written in a list

P0, P1, P2 … Pn

Then we could multiply all these numbers together and add one to get a new number Q

Q = P0P1P2…Pn + 1

This means that Q doesn’t have any of the primes as a factor as it will leave a remainder of one when divided by any of the primes, because that was how it was constructed. But every number can be written as a product of primes. Therefore Q is either a new prime or there is a prime which isn’t on the list which is a factor of Q. So the list doesn’t contain all the primes because it doesn’t contain this new prime. This is a contradiction because we assumed that the list contained all the primes, therefore there cant be a finite number of prime so there must be an infinite number of them, hence they cannot be written in a list.

By David Woodford

Categories: maths Tags: , , , ,