Transcript PPT

Chapter 3: Elementary Number Theory
and Methods of Proofs
3.1-.3.4 Direct Methods and Counterexamples
• Introduction
• Rational Numbers
• Divisibility
• Division Algorithm
Instructor: Hayk Melikya
Introduction to Abstract Mathematics
[email protected]
1
Basic Definitions
Definition: An integer n is an even number if there exists an
integer k such that n = 2k.
Symbolically: Let Even(n) := “an integer n is even”:
E(n) = ( k  Z)( n = 2k) .
Def: An integer n is an odd number if there exists an integer
k such that n = 2k+1.
Symbolically: Let O(n) := “an integer is odd”:
Odd(n) = ( k  Z)( n = 2k +1) .
Def: An integer n is a prime number if and only if n>1
and if n=rs for some positive integers r and s then r=1 or s=1.
Introduction to Abstract Mathematics
2
Primes and Composites
Def: An integer n is a prime number if and only if n>1
and if n=rs for some positive integers r and s then r=1 or s=1.
Symbolically: Prime(n):= n is prime
  positive integers r and s, if n = rs then r =1 or s =1
Def: A positive integer n is a composite if and only if n=rs for some
positive integers r and s then r
≠ 1 and s ≠ 1.
Symbolically: Cpmposite(n):= n is compoeite   positive integers r and s,
such that n = rs and r
≠ 1 and s ≠ 1
The RSA Challenge (up to US$200,000)
http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
Examples: Find the truth value of the following prpopositions
E(6), P(12), C(17)
Introduction to Abstract Mathematics
3
Existential Statements
x P(x)
Proofs:
– Constructive
 Construct an example of such a such that P(a) is true
– Non-constructive
 By contradiction
– Show that if such x does NOT exist than a
contradiction can be derived
Introduction to Abstract Mathematics
4
Example
Let G(n):= a  b ((a+b=n)  Prime(a)  Prime(b))
Prove that (nN)G(n)
Proof:
– n=210
– a=113
– b=97
Piece of cake…
What about (nN) G(n) ( many Million $ baby)
Introduction to Abstract Mathematics
5
Universal Statements



x P(x)
x [Q(x)  R(x)]
Proof techniques:
– Exhaustion
– By contradiction
 Assume the statement is not true
 Arrive at a contradiction
– Direct
 Generalizing from an arbitrary particular member
Introduction to Abstract Mathematics
6
├ (xU)P(x)
To prove a theorem of the form (xU)P(x) (same as ├ (xU)P(x))
which states “for all elements x in a given universe U, the
proposition P(x) is true” we select an arbitrary aU from the
universe, and then prove the assertion P(a).
Then by Universal generalization we conclude P(a)├ (xU)P(x)
For arguments of the form├ x [Q(x)  R(x)]
Introduction to Abstract Mathematics
7
Example 1
Exhaustion:
– Any even number between 4 and 30 can be written as a sum of
two primes:
– 4=2+2
– 6=3+3
– 8=3+5
– …
– 30=11+19
Works for finite domains only
What if I want to prove that for any integer n the product of n
and n+1 is even?
Can I exhaust all integer values of n?
Introduction to Abstract Mathematics
8
Example 2
Theorem: (nZ)( even(n*(n+1)) )
Proof:
– Consider a particular but arbitrary chosen integer n
– n is odd or even
– Case 1: n is odd
 Then n=2k+1, n+1=2k+2
 n(n+1) = (2k+1)(2k+2) = 2(2k+1)(k+1) = 2p for some integer p
 So n(n+1) is even
Case 2: n is even
Then n=2k, n+1=2k+1
n(n+1) = 2k(2k+1) = 2p for some integer p
So n(n+1) is even
Introduction to Abstract Mathematics
9
Fallacy
Generalizing from a particular but NOT arbitrarily chosen example
I.e., using some additional properties of n
Example:
– “all odd numbers are prime”
– “Proof”:
 Consider odd number 3
 It is prime
 Thus for any odd n prime(n) holds
Such “proofs” can be given for correct statements as well!
Introduction to Abstract Mathematics
10
Prevention



Try to stay away from specific instances (e.g., 3)
Make sure that you are not using any additional properties of n
considered
Challenge your proof
– Try to play the devil’s advocate and find holes in it…
•
•
•
•
Using the same letter to mean different things
Jumping to a conclusion
Insufficient justification
Begging the question assuming the claim first
Introduction to Abstract Mathematics
11
Rational Numbers
A real number is rational iff it can be represented
as a ratio/quotient/fraction of integers a and b(b0)
– rR [rQ  a,bZ [r=a/b & b0]]
Notes:
– a is numerator
– b is denominator
– Any rational number can be represented in infinitely many ways
– The fractional part of any rational number written in any natural radix
has a period in it
Introduction to Abstract Mathematics
12
Rational or not?





-12
– -12/1
3.1459
– 3+1459/10000
0.56895689568956895689…
– 5689/9999
1+1/2+1/4+1/8+…
– 2
0
– 0/1
Introduction to Abstract Mathematics
13
Theorem 1
Any number with a periodic fractional part in a natural
radix representation is rational
Proof:
– Constructive:
– x=0.n1…nmn1…nm…
– x=0.(n1…nm)
– x*10m-x=n1…nm
– x=n1…nm/(10m-1)
Introduction to Abstract Mathematics
14
Theorem 2
Any geometric series:
– S=q0+q1+q2+q3+…
– where -1<q<1
– evaluates to S=1/(1-q)
Proof
– Proof idea
– More formal proof
– Definitions of limits and partial sums
Introduction to Abstract Mathematics
15
ZQ
Every integer is a rational number
Proof : set the denominator to 1

Book : page 127
Q
The set of rational numbers is closed with respect to arithmetic
operations +, -, *, /
Partial proofs : textbook pages 121-131
Formal proof
Introduction to Abstract Mathematics
16
Irrational Numbers

So far all the examples were of rational numbers

How about some irrationals?
– 
– e
– sqrt(2)
Introduction to Abstract Mathematics
17
Simple Exercises
The sum of two even numbers is even.
The product of two odd numbers is odd.
direct proof.
Introduction to Abstract Mathematics
18
Divisibility
a “divides” b or is b divisible by a (a|b ):
b = ak for some integer k
Also we say that
5|15 because 15 = 35
b is multiple of a
n|0 because 0 = n0
a is a factor of b
1|n because n = 1n
b is divisor for a
n|n because n = n1
A number p > 1 with no positive integer divisors other than 1 and itself
is called a prime. Every other number greater than 1 is called composite.
2, 3, 5, 7, 11, and 13 are prime,
4, 6, 8, and 9 are composite.
Introduction to Abstract Mathematics
19
Simple Divisibility Facts
1. If a | b, then a | bc for all c.
2. If a | b and b | c, then a | c.
3. If a | b and a | c, then a | sb + tc for all s and t.
4. For all c ≠ 0, a | b if and only if ca | cb.
Proof of (??)
Introduction to Abstract Mathematics
direct proof.
20
Divisibility by a Prime
Theorem. Any integer n > 1 is divisible by a prime number.
Introduction to Abstract Mathematics
21
Fundamental Theorem of Arithmetic
Every integer, n>1, has a unique factorization into primes:
p0 ≤ p1 ≤ ··· ≤ pk
p0 p1 ··· pk = n
Example:
61394323221 = 3·3·3·7·11·11·37·37·37·53
Introduction to Abstract Mathematics
22
Prime Products
Claim: Every integer > 1 is a product of primes.
Proof: (by contradiction)
Suppose not. Then set of non-products is nonempty.
There is a smallest integer n > 1 that is not a product of primes.
In particular, n is not prime.
So n = k·m for integers k, m where n > k,m >1.
Since k,m smaller than the least nonproduct, both are prime
products, eg.,
k = p1 p2   p94
m = q1 q2   q214
Introduction to Abstract Mathematics
23
Prime Products
Claim: Every integer > 1 is a product of primes.
…So
n = k m = p1 p2   p94 q1 q2   q214
is a prime product, a contradiction.
 The set of nonproducts > 1 must be empty. QED
(The proof of the fundamental theorem will be given later.)
Introduction to Abstract Mathematics
24
The Quotient-Reminder Theorem
For b > 0 and any a, there are unique numbers
q : quotient(a,b), r : remainder(a,b), such that
a = qb + r
and
We also say
0  r < b.
q = a div b
r = a mod b.
When b=2, this says that for any a,
there is a unique q such that a=2q or a=2q+1.
When b=3, this says that for any a,
there is a unique q such that a=3q or a=3q+1 or a=3q+2.
Introduction to Abstract Mathematics
25
The Division Theorem
For b > 0 and any a, there are unique numbers
q : quotient(a,b), r : remainder(a,b), such that
a = qb + r
and
0  r < b.
Given any b, we can divide the integers into many blocks of b numbers.
For any a, there is a unique “position” for a in this line.
q = the block where a is in
-b
0
b
2b
r = the offset in this block
kb
a
(k+1)b
Clearly, given a and b, q and r are uniquely defined.
Introduction to Abstract Mathematics
26
The Square of an Odd Integer
Idea 0: find counterexample.
32 = 9 = 8+1,
52 = 25 = 3x8+1
……
1312 = 17161 = 2145x8 + 1, ………
Idea 1: prove that n2 – 1 is divisible by 8.
Idea 2: consider (2k+1)2
Idea 3: Use quotient-remainder theorem.
Introduction to Abstract Mathematics
27
Contrapositive Proof
Statement:
If m2 is even, then m is even
Contrapositive: If m is odd, then m2 is odd.
Proof (the contrapositive):
Since m is an odd number, m = 2l+1 for some natural number l.
So m2 = (2l+1)2 = (2l)2 + 2(2l) + 1
So m2 is an odd number.
Introduction to Abstract Mathematics
Proof by contrapositive.
28
Irrational Number
Theorem:
2
is irrational.
Proof (by contradiction):
• Suppose
2 was rational.
• Choose m, n integers without common prime factors (always possible)
such that
m
2
n
• Show that m and n are both even, thus having a common factor 2,
a contradiction!
Introduction to Abstract Mathematics
29
Irrational Number
Theorem:
2
is irrational.
Proof (by contradiction):
Want to prove both m and n are even.
so can assume
m
2
n
m  2l
m 2  4l 2
2n  m
2n  4l
2
2n  m
2
2
2
n 2  2l 2
so m is even.
so n is even.
Introduction to Abstract Mathematics
Proof by contradiction.
30
Infinitude of the Primes
Theorem. There are infinitely many prime numbers.
Let p1, p2, …, pN be all the primes.
Consider p1p2…pN + 1.
Claim: if p divides a, then p does not divide a+1.
Introduction to Abstract Mathematics
Proof by contradiction.
31
Floor and Ceiling
Def: For any real number x, the floor of x, written x, is the unique
integer n such that n  x < n + 1.
It is the largest integer not exceeding x ( x).
Def: For any real number x, the ceiling of x, written x, is the
unique integer n such that n – 1 < x  n. What is n?
If k is an integer, what are x and x + 1/2 ?
Is x + y = x + y?
( what if x = 0.6 and y = 0.7)
For all real numbers x and all integers m, x + m = x + m
For any integer n, n/2 is n/2 for even n and (n–1)/2 for odd n
Introduction to Abstract Mathematics
32
Exercises
Is it true that for all real numbers x and y:
x – y = x - y
x – 1 = x - 1
x + y = x + y
x + 1 = x + 1
For positive integers n and d, n = d * q + r,
where d = n / d and r = n – d * n / d
with 0  r < d
Introduction to Abstract Mathematics
33
Greatest Common Divisors
Given a and b, how to compute gcd(a,b)?
Can try every number, but can we do it more efficiently?
Let’s say a>b.
1. If a=kb, then gcd(a,b)=b, and we are done.
2. Otherwise, by the Division Theorem, a = qb + r for r>0.
Introduction to Abstract Mathematics
34
Greatest Common Divisors
Let’s say a>b.
1. If a=kb, then gcd(a,b)=b, and we are done.
2. Otherwise, by the Division Theorem, a = qb + r for r>0.
a=12, b=8 => 12 = 8 + 4
gcd(12,8) = 4
gcd(8,4) = 4
a=21, b=9 => 21 = 2x9 + 3
gcd(21,9) = 3
gcd(9,3) = 3
a=99, b=27 => 99 = 3x27 + 18
gcd(99,27) = 9
gcd(27,18) = 9
Euclid: gcd(a,b) = gcd(b,r)!
Introduction to Abstract Mathematics
35
Euclid’s GCD Algorithm
a = qb + r
Euclid: gcd(a,b) = gcd(b,r)
gcd(a,b)
if b = 0, then answer = a.
else
write a = qb + r
answer = gcd(b,r)
Introduction to Abstract Mathematics
36
Example 1
gcd(a,b)
if b = 0, then answer = a.
GCD(102, 70)
102 = 70 + 32
= GCD(70, 32)
70 = 2x32 + 6
write a = qb + r
= GCD(32, 6)
32 = 5x6 + 2
answer = gcd(b,r)
= GCD(6, 2)
6 = 3x2 + 0
else
= GCD(2, 0)
Return value: 2.
Example 3
Example 2
GCD(662, 414)
662 = 1x414 + 248
= GCD(414, 248)
414 = 1x248 + 166
= GCD(189, 63)
= GCD(248, 166)
248 = 1x166 + 82
= GCD(63, 0)
= GCD(166, 82)
166 = 2x82 + 2
= GCD(82, 2)
82 = 41x2 + 0
GCD(252, 189)
252 = 1x189 + 63
189 = 3x63 + 0
Return value: 63.
= GCD(2, 0)
Return value: 2.
Introduction to Abstract Mathematics
37
Practice problems
Study the Sections 3.1- 3.4 from your
textbook.
2. Be sure that you understand all the
examples discussed in class and in textbook.
3. Do the following problems from the
textbook:
Exercise 3.1 # 13, 16, 32, 36, 45
Exercise 3.2 # 15, 19, 21, 32,
Exercise 3.3 # 13, 16, 25, 26,
Exercise 3.4 # 4, 6, 8, 10, 18, 33
1.
Introduction to Abstract Mathematics
39