Proof By Contradiction

Question 1

Prove that there is no greatest (odd/even) integer

Answer 1

Assume that there is a greatest odd/even integer, n
But n+2 is also odd/even and is greater than n
Hence a contradiction and assumption is wrong
So there is no greatest odd/even integer

Question 2

What is the negation of ‘if a then b’

Answer 2

‘If a then not b ‘

Question 3

Prove by contradiction that if n^2 is even then n must be even

Answer 3

Assume that if n^2 is even then n is odd
A number is off when n = 2k+1 where k is integer
n^2 = (2k+1)^2= 4k^2+4k+1
=2(2k^2+2k+1 which is odd
Contradiction and assumption is wrong
Hence is n^2 is even then n must be even

Question 4

Prove by contradiction to show that there are no integers a and b for which 25a + 15b = 1

Answer 4

Assume that there are integers a and b for which 25a+15b=1
25a+15b=1
5(5a+3b)=1
5a+3b=1/5
Cannot have two integers multiplied by two integers (3,5) to give a fraction
Have contradiction and assumption is wrong
Hence no integers exist a and b such that 25a+15b=1

Question 5

What is a rational number

Answer 5

Expressed in form a/b where a and b integers

Question 6

What is an irrational number

Answer 6

Can’t be expressed in a/b

Question 7

Use proof by contradiction to show that given a rational number a and an irrational number b, a-b is irrational

Answer 7

Assume given rational number a and irrational number b, a-b is rational
Rational number so a=c/d
Rational number so a-b=e/f
a - b = e/f
c/d - b = e/f
c/d - e/f = b
(cf-de)/df = b
B is rational as can be represented as a fraction
This contradicts that b is irrational and assumption is wrong g
Original statement is true

Question 8

Prove that square root of 2 is irrationals using contradiction

Answer 8

Assume that the square root of 2 is rational
Rational number = a/b where a and b are integers in simplest form and coprime
Root2 =a/b
2=a^2/b^2
2b^2 = a^2 so a^2 must be even as equal to multiple of 2
2b^2 =(2k)^2 as a even
2b^2 = 4 k^2
B^2 = 2k^2 so b must be even
If a and b even have a common factor of 2
A/b not in simplest form have contradiction so assumption wrong
Hence root 2 is irrational

Question 9

Prove by contradiction that there are infinitely many primes

Answer 9

Assume that there are a finite number primes
Therefor can list all prime numbers p1,p2,p3,…,pn
Consider number N=(p1 x p2 x p3 x …. x pn) +1
When divide N by and p1,p2,p3,…,pn remainder a;ways 1
Therefore N not divisible by any f these primes
Therefore N must itself be prime or its prime factorisation contains only prime not in lour original list
Contradicts the assumption
Therefore infinite umber of primes