Transcript Chapter 1 Elementary Number Theory

Elementary Number Theory & Proofs
x
For all x
x
There exists an x

Implication Symbol

Iff : if and only if
There are several methods of mathematical proof but all depend on a series of
logical steps.
All proofs start with an implication or proposition and so it is necessary to
establish whether the implication is true or false.
1. If x  5 then 2 x  10
This is true and can be shown by solving the inequality 2x > 10
2. If x 2  25 then x  5
This is false and can be shown by solving the equation x2 = 25
Implication statements are often called “if…then..” statements but
the notation for this is to use the implication symbol “”.
Example 1 becomes x  5  2 x  10
Example 2 becomes x 2  25  x  5
The converse of an implication
If “statement p statement q”, then the converse will be
“statement q  statement p”
1. Statement:- x  5  2 x  10. True
Converse:- 2x  10  x  5. True
2. Statement:- x 2  25  x  5. False
Converse:- x  5  x 2  25. True
To prove an implication false it is often only necessary to give a single
counter example.
In example 2. x 2  25  x  5. Is false.
Proof:- Counter example x  5.
Two way implications - Equivalence
If p  q and q  p are both true then we can say p is equivalent to q
or
" p iff q " (p, if and only if q) We use the notation
In example 1, we could write x  5  2 x  10.
But we could not say this about example 2.
pq
Existential Statement
An existential Statement, x , refers to at least one member of a set.
An existential statement is proved by one corroborative example.
Statements can be combined to form compound statements.
(i) If A then B is an implication
AB
(ii) If ~A then ~B is its inverse
~A ~B
(iii) If B then A is its converse
BA
(iv) If ~B then ~A is its contrapositive
~B  ~A
If both the implication and its converse is true, then the statements
are said to be equivalent.
AB
If ABC is right angled at C, then c  a  b
2
Inverse: c  a  b
2
2
2
2
2
Converse: if c  a  b then ABC is right angled at C
2
2
2
Contrapositive: if c  a  b then ABC is not right angled at C
2
2
2
If the implication is true then the contrapositive is true.
BUT the inverse and converse need not be true.
If the shape is a square then it has four sides.
Inverse:
If the shape is not a square then it does not have four sides
Converse: If it has four sides then the shape is a square
Contrapositive:
If it does not have four sides then the shape is not a square
If the implication is true then the contrapositive is true.
BUT the inverse and converse need not be true.
Page 3 Exercise 1A
TJ Exercise 1, 2 and 3
Proof by Contradiction
Reductio ad absurdum
Reduce to an absurdity.
Direct Proof. This method is one that we have used at various
points in the course. The equation of a straight line, Pythagoras
theorem etc.
To prove an implication p  q is sometimes difficult if not
impossible to prove directly.
In this case, we prove by contradiction (or by contrapositive)
The contrapositive (negation) of p  q is ~q  ~p. (not q implies
not p)
When ~q  ~p is true so is p  q.
(i) Whatever statement we wish to prove, we assume its
negation to be true.
(ii) By a series of steps (valid implications) we arrive at a
contradiction.
(iii) Since the steps are valid, it can only be the assumption
that is false.
(iv) If the negation is false, the original statement must be
true.
ab
Pr ove
 ab a, b 
2
ab
Assume
 ab
2
 a  b  2 ab
 (a  b)2  4ab
 a 2  2ab  b 2  4ab
 a 2  2ab  b 2  0
 (a  b)2  0
Since a, b  , (a  b)2  0 is false
 the assumption is false
ab
Hence
 ab a, b 
2
Example: Prove that the set of primes is infinite.
This is impossible to prove directly.
Suppose that the set of primes is finite having n numbers.
P1, p2, p3, ……pn. Hence a number exists that is the product of all
primes.
N = P1 p2  p3 ……  pn
Now consider the number after N N + 1
( N  1)  p1  p2  p3  .......  pn  1
If we attempt to divide (N + 1) by any of the know primes P1 to pn
there will always be a remainder 1.
Hence (N + 1) is not divisible by any prime number greater than 1
apart from (N + 1) so must be prime and is greater than the largest
prime number pn meaning our supposition is false.
Hence the set of primes is infinite.
Prove that 2 is irrational.
Begin by supposing that 2 is rational.(ie can be written as a fraction)
m
Let 2 =
where m and n have no common factor.
n
m2
 2  2  m 2  2n 2  m 2 is even
n
PROOF
If m2 is even  m is even  m  2k (k  )
 2n2  m2  4k 2  n2  2k 2  n2 is even
If n2 is even then using the proof above n must also be even.
 m and n have a common factor of 2
But we stated that m and n have no common factors.
This is a contradiction.
m
Therefore 2 can not be written in the form
and must be irrational.
n
Page 14 Exercise 3A Questions 1, 2, 3, 6, 11 and 12
TJ exercise 4
Proof by Induction
Proof by induction is a method of proof in which we establish the truth
of the implication for some starting value and then prove it for the
succeeding values. This method is used in proving summation
examples, the Binomial Theorem and de Moivre’s Theorem.
i.e. prove the statement true for 1
Then assume true for some value k
Then prove true for k + 1
If the statement is true for 1 and if true for k is also true for k + 1
then the statement must be true for all values in N.
Example 1.
n
1
Prove that  r  n(n  1), where
2
r 1
n
 r  1  2  3  ...  (n  1)  n
r 1
Part A: Prove true for n = 1.
n
1
for n  1,  r   r  1
r 1
also,
r 1
1
1
n(n  1)  1 2  1
2
2
Hence the statement is true for n = 1.
k
Part B: Assume true for n = k where k  1
1
  r  k (k  1)
2
r 1
Let us consider n = k + 1
k 1
1
i.e show  r  (k  1)((k  1)  1)
2
r 1
GOAL
n
1
r  n(n  1)

2
r 1
k 1
k
r 1
r 1
 r   r  (k  1)
1
 k (k  1)  (k  1)
2
1 2 1
 k  k  k 1
2
2
1
 (k 2  k  2k  2)
2
1
 (k 2  3k  2)
2
1
 (k  1)(k  2)
2
k 1
1
r

(k  1)((k  1)  1)

2
r 1
Hence, if true for n = k, then true for n = k + 1
The statement is true for n = 1, and if true for n = k implies true for
n = (k + 1), then by induction it is true for all values of n  1.
Example 2.
Prove n3  2n is divisable by 3 n  1, n 
Part A: Prove true for n = 1.
When n  1, n3  2n  1  2  3  True
Part B: Assume true for n = k where k  1
 k  2k  3m for some m 
3
Goal: 3 (k  1)3  2(k  1)
Let us consider n  (k  1)
(k  1)3  2(k  1)  k 3  3k 2  3k  1  2k  2
 (k 3  2k )  3k 2  3k  3
 3m  3(k 2  k  1)
 3(m  k 2  k  1)  True
The statement is true for n = 1, and since if true for n = k implies true for
n = (k + 1), then by induction it is true for all values of n  1.
Prove 2n  n n 
Part A: Prove true for n = 1. When n  1,
Part B: Assume true for n = k where k  1
Let us consider n  (k  1)
Since 2k  k
21  1  True
 2k  k
Goal: 2k 1  k  1
( both sides by 2)
 2k 1  2k
 2k 1  k  k
Since k  1
 2k 1  k  1
The statement is true for n = 1, and since if true for n = k implies true for
n = (k + 1), then by induction it is true for all values of n  1.
n
1
Prove that  (1) r  (1) n1 n(n  1)
2
r 1
r 1 2
Part A: Prove true for n = 1.
n
1
for n  1,  (1) r   (1)012  1
r 1 2
r 1
r 1
1
1
n1
Also (1) n(n  1)  (1) 01(2)  1
2
2
Hence the statement is true for n = 1.
Part B: Assume true for n = k where k  1
k
1
  (1) r  (1) k 1 k (k  1)
2
r 1
r 1 2
Now show that it is true for n = k + 1
k 1
k
r 1
r 1
1
Goal (1) k ( k  1)( k  2)
2
r 1 2
r 1 2
( k 11)
2
(

1)
r

(

1)
r

(

1)

(
k

1)


1
 (1) k 1 k (k  1)  (1) k (k  1) 2
2
1
 (1) k (k  1)  k  2(k  1) 
2
(factorise)
1
 (1) k (k  1)(k  2)
2
The statement is true for n = 1, and since if true for n = k implies true for
n = (k + 1), then by induction it is true for all values of n  1.
Page 20 Exercise 4 Questions 6, 7, 8, 9, 11, 12, 13
TJ Exercise 5
Fundamental Theorem of
Arithmetic
The fundamental theorem of arithmetic states that any integer n > 1
can be expressed uniquely as a product of prime numbers apart
from the order of primes.
6  3  2 or 36  2  2  3  3
Express 430 as a product of prime numbers.
430  2  215
215  5  43
43  43  1
 430  2  5  43
TJ Exercise 6