2 - chapter 1 - proof

Question 1

proof by contradiction steps

Answer 1

• assume the opposite of what your proving
• use this assumption to then get to a condtradiction
• the contradiction means your original statement was flase proving the question

Question 2

prove there are infinite primes

Answer 2

• assume there is a larges prime number P
• there is anothe number N that is a product of all prime number up to and including P
• consider N+1 - this is one greater than a number divisible by all the prrimes up to and including P so its not divisible by any of them
• either N+1 is prime or is divisible by primes larger than P
• so there is a prime larger than P - contraction
• therefore there are an infinite number of primes

Question 3

prove √2 is irrational

Answer 3

assume √2 = p/q
where p and q are integers with no common factors
2 = p²/q²
p² = 2q²
so p² is even therefore p is even so p = 2k and p² = 4k²
subbing into p² = 2q²
4k² = 2q²
q² = 2k² so q² is even so q is even
so p and q share a factor of 2 - contradiction
therefore √2 is irrational

Question 4

prove log2 3 is irrational

Answer 4

assume log2 3 = p/q
2^p/q = 3
2^p = 3^q
there is no integer power of 3 which is also a multiple of 2 so this is only true if p=q=0 - contradiction

Question 5

prove n has a prime factor less than or = to √n if n is a composite integer

Answer 5

n has at least one prime factor (p) where 1<p<n
assume it has no prime factors <=√n
p>√n
since p is a factor of n that doesnt = n there is an integer q so pq = n
q = n/p <n/√n so q<√n
if q is prime this is a contradiction
if q is not prime it must have a prime factor r<q
as r is a factor of q its also a factor of n so r<q<√n - contradicition