Transcript a ® m

Section 3.1
Direct Proof and Counterexample I:
Introduction
• A definition gives meaning to a term.
• A non-primitive term is defined using previously defined
terms.
• A primitive term is undefined.
• Example
– A function f : R  R is increasing if f(x)  f(y) whenever x  y.
– Previously defined terms: function, real numbers, greater than.
• Definitions are not theorems.
• Example
– Def: A number n is a perfect square if n = k2 for some
integer k.
– Now suppose t is a perfect square.
– Then t = k2 for some integer k.
Definitions are automatically “if and only if,” even
though they don’t say so.
a.
An integer x is even iff n = 2k for some integer k.
"x, Int(x)  (Even(x)  k, Int(k)  x = 2k )
b.
An integer x is odd iff x = 2k + 1 for some integer k.
"x, Int(x)  (Odd(x)  k, Int(k)  x = 2k +1)
c.
An integer x is a perfect square iff x = k2 for some integer k.
"x, Int(x)  (PfSq(x)  k, Int(k)  x = k2)
d.
Any number x is positive iff x > 0.
"x, Positive(x)  x > 0
e.
Any number x is negative iff x < 0.
"x, Negative(x)  x < 0
g.
An integer x is prime iff x > 1 and, for all positive integers r
and s, if x = r . s, then r = 1 or s = 1.
"x, Int(x)  ( Prime(x) 
(x > 1  ("r,"s, (Int(r)  Int(s)  r > 0  s > 0  x = r.s)  r = 1  s =
1))
)
h.
An integer x is composite iff x > 1 and, there are positive
integers r and s, x = r  s, r  1 and s  1.
"x, Int(x)  (
Composite(x) 
(x > 1  (r,s, Int(r)  Int(s)  r > 0  s > 0  x = r.s  r  1  s  1))
)
Q: Is 2/0 a rational number?
A: No.
Go back to the definition:
"q, ( Rational(q)  a,b, Int(a)  Int(b)  b  0  q = a/b )
Q: Is 0 an even number?
A: Yes.
Go back to the definition:
"x, Int(x)  (Even(x)  k, Int(k)  x = 2k )
2.3.3 Q: Is 0 a positive number?
A: No.
0 > 0???
Go back to the definition:
"x, Positive(x)  x > 0
Q: Is 1 a prime number?
A: No.
Go back to the definition:
"x, Int(x)  (
Prime(x) 
(x > 1  ("r,"s, (Int(r)  Int(s)  r > 0  s > 0  x = r.s)  r = 1  s =
1))
)
Q: Is 2 a prime number?
A: Yes.
Go back to the definition:
"x, Int(x)  (
Prime(x) 
(x > 1  ("r,"s, (Int(r)  Int(s)  r > 0  s > 0  x = r.s)  r = 1  s =
1))
)
2 > 1???
2=21=12
Q: Is 3 a composite number?
A: No.
Go back to the definition:
"x, Int(x)  (
Composite(x) 
(x > 1  (r,s, Int(r)  Int(s)  r > 0  s > 0  x = r.s  r  1  s  1))
)
3=31=13
NOTES
1. Is 365 odd? Prove it
2. Page 115, example 3.1.3 b
• A proof is an argument leading from a
hypothesis to a conclusion in which each step
is so simple that its validity is beyond doubt.
… yeah right
•That is a subjective judgment – what is simple
to one person may not be so simple to another.
Proofs – Some guidelines
• Interpret the statement logically. If you are unable to interpret
the statement in your mind, then translate it into predicate
calculus.
• Go back to the definitions for the various terminologies used.
• Try a few small and varied examples to get a feel of the
problem – ‘play around with the problem’.
– “Whenever you are presented with a statement to be proved, explore it
a bit to see whether you believe it to be true.” (Textbook p117)
As you ‘play around with the problem’, you will begin to
understand (and experience) the problem. When you are
asked to prove something, purposely try to find an example to
disprove it. In the process of trying (and failing) to find a
counter-example, you will understand why the statement is
true in general.
• When trying to prove: Break down the problem into
smaller bits (work backwards as well as forwards).
– Go back to the definitions for the various terminologies that are
used.
– Use theorems that you know.
– Use the logical rules / proof techniques that you have been taught.
What are your premises? What must you assume and what to you
work towards?
• Proving universal statements
– Prove something is true in every instance
• Proving existential statements
– Prove something is true in at least one instance
• Disproving universal statements
– Prove something is false in at least one instance
• Disproving existential statements
– Prove something is false in every instance
• The statement is generally of the form
"x  D, P(x)  Q(x)
• Use the method of generalizing from the
generic particular.
– Select an arbitrary x in D (generic particular).
– Assume that P(x) is true (hypothesis).
– Argue that Q(x) is true (conclusion).
Direct Proof
We need to use DIRECT PROOF to prove universal quantifiers.
•What are universal quantifiers? Think of an example
•If you were to prove its truth how would you do it by brute
force?
•Is there a simpler way?
•The name of the simpler way is DIRECT PROOF
Page 117, blue box
Prove that every integer is a rational number.
i.e. Prove: "x, Int(x)  Rational(x)
Proof:
 Let n be an integer.
 Now, n = n/1, and n/1 is a rational number (defn of
rational number).
 So n is a rational number.
 Therefore every integer is a rational number.
Prove that every integer is a rational number.
i.e. Prove: "x, Int(x)  Rational(x)
Proof:
 Let n be an integer.
 Now, n = n/1, and n/1 is
a rational number
(defn of rational
number).
 So n is a rational
number.
 Therefore every
integer is a rational
number.
High-Level: C/Java Programming
"q, ( Rational(q) 
a,b, Int(a)  Int(b)  b  0  q = a/b )
Int(n)
n = n/1
a,b, Int(a)  Int(b)  b  0  n = a/b
Rational(n)
Int(n)  Rational(n)
All Definitions and
theorems become
Premises!!
"x, Int(x)  Rational(x)
Low-Level: Assembly Programming
THEOREM:If the sum of two integers is even then so is the
difference
i.e. Prove: "x,"y, Even(x + y)  Even(x - y)
An integer x is even iff n = 2k for some integer k.
If x + y is even , then
x + y = 2k for some integer k
x = 2k - y
x–y=
(2k - y) – y = 2k – y – y= 2(k – y)
= 2m where m = (k-y)
Is (k – y) an integer? Why?
• Theorem: The sum of two consecutive
triangle numbers is a perfect square.
– Definition: Let n be a positive integer. The nth
triangle number Tn is the number n(n + 1)/2.
– Definition: Let n be a positive integer. The nth
perfect square Sn is the number n2.
• Proof:
– Let n be a positive integer.
– Tn + Tn + 1
= n(n + 1)/2 + (n + 1)(n + 2)/2
= (n2 + n + n2 + 3n + 2)/2
= (2n2 + 4n + 2)/2
= (n + 1)2
= Sn + 1.
Therefore, Tn + Tn + 1 = Sn + 1 for all n  1.
By Cases (LEM)
Prove that either x is even or x + 1 is even, for any integer x.
i.e. Prove: "x, Int(x)  Even(x)  Even(x+1)
Proof:
•
Let n be an integer.
•
Now, either n is even or n is NOT even.
•
(Case 1) If n is even, then we are done! (since it is indeed true that either n is
even or n+1 is even.)
•
(Case 2) If n is NOT even, then n is odd.
– Therefore n = 2k+1 for some integer k. (Defn of ‘odd’).
– Therefore n+1 = 2k+2 = 2(k+1).
– So n+1 is even. (Defn of ‘even’)
– So again, it is true that either n is even or n+1 is even.
•
In either case, it is true that either n is even or n+1 is even.
IFF; By Cases; Disj Syllogism
Prove that the product of any 2 integers is odd iff both the
integers are odd.
i.e. Prove: "x,"y, Odd(x  y)  Odd(x)  Odd(y)
Proof ()
•
Let m and n be 2 integers. Assume that m  n is odd. Need to show : m is odd
and n is odd.
•
Now, either (1) m, n are both even, or (2) one is even and one is odd, or (3)
both are odd.
•
(Case 1?) Assume m, n are both even. Then m=2k and n=2j, for some k and j.
And so m  n = 2(2kj) which is even. (But m  n must be odd: ^)
•
So it cannot be case (1). Therefore it has to be either case (2) or (3).
•
(Case 2?) Let be m even and n be odd. Then m=2k and n=2j+1, for some k
and j. And so m  n = 2k(2j+1) which is even. (But m  n must be odd: ^).
•
So it cannot be case (2). Therefore it has to be case (3): both m and n are odd.
Prove that the product of any 2 integers is odd iff both the
integers are odd.
i.e. Prove: "x,"y, Odd(x  y)  Odd(x)  Odd(y)
Proof ()
•
Let m and n be 2 integers. Assume that m is odd and n is odd. Need to show :
m  n is odd.
•
Since m is odd and n is odd, let m=2k+1 and n=2j+1, for some k and j.
•
Therefore m  n = (2k+1)(2j+1)
= 4kj + 2k + 2j + 1
= 2(2kj + k + j) + 1 which is odd.
(Because, by definition, a number is odd iff it can be expressed in the form 2k
+ 1 for some integer k).
•
Therefore if m and n are odd, then m  n is odd.
Therefore, the product of any 2 integers is odd iff both the integers are odd.
By proving the Contra-positive
Prove that if x2 is even then x is even.
i.e. Prove: "x, Even(x2)  Even(x)
Proof:
 We prove the contra-positive of this statement:
If is x NOT even, then x2 is NOT even.
 Let n be an integer.
• Assume that is n not even (i.e. n is odd)
• Therefore n = 2k+1 for some integer k.
• Therefore n2 = (2k+1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 which is
odd.

Therefore for any integer x, if x is NOT even then x2 is
NOT even.
By Contradiction
Disprove: Every integer greater than 0 is either prime or composite.
i.e. Disprove: "x, Int(x)  (x > 0)  Prime(x)  Composite(x)
Proof:




Disprove : "x, Int(x)  (x > 0)  Prime(x)  Composite(x)
Prove
: ~ ( "x, Int(x)  (x > 0)  Prime(x)  Composite(x) )
Prove
: x, Int(x)  (x > 0)  ~Prime(x)  ~Composite(x)
(Note: ~" reduces to a constructive proof, known specially as
the counter-example)
Find that integer!!!
1
is an integer which is greater than 0.
1 is not prime (because prime numbers are greater than 1)
1 is not composite (because composite numbers are also greater
than 1… besides 1 cannot be broken up into 2 factors which are
not equal to 1).
Prove that there exists an integer x such that x > 1 x2 + x + 1
is not a prime number.
i.e. Prove: x, Int(x)  ~Prime(x2 + x + 1)
Proof:






Prove : x, Int(x)  ~Prime(x2 + x + 1)
Constructive Proof: Find that integer!!!
x = 2 ? 22 + 2 + 1 = 7 (Prime! But I must find a non-prime…)
x = 3 ? 32 + 3 + 1 = 13 (Prime! But I must find a non-prime…)
x = 4 ? 42 + 4 + 1 = 21 = 3  7 (Not a prime! Found it!)
Therefore, there exists an integer x (x = 4) such that x2 + x + 1
is not a prime number.
Note: Disprove ‘stmt’ = Prove ‘~stmt’
… and you are asked to …
Prove
"x,P(x)
When
you
are
given
a stmt
in the
form…
Disprove
Which means prove that
the OPPOSITE IS TRUE.

Direct Proof.


Usually the statement
will be: "x,P(x)  Q(x)

Reason, in general that
it is true for all cases.

Constructive proof. Find
the ‘x’. Also known as…

Counter-example: An
example to counter the "

Which means prove that
the OPPOSITE IS TRUE.


Constructive Proof. Find
that ‘x’.

x,P(x)

i.e. Prove: ~("x,P(x))… i.e.
Prove: x, (~P(x))
i.e. Prove: ~(x,P(x))… i.e.
Prove: "x, (~P(x))
Direct proof.
Rational Numbers
• A rational number is a number that equals the
quotient of two integers.
• Let Q denote the set of rational numbers.
• An irrational number is a number that is not
rational and any other definition of irrational numbers? Page
126
• Theorem: The sum of two rational numbers is
rational.
• Proof:
– Let r = a/b and s = c/d be rational.
– Then r + s = (ad + bc)/bd, which is rational.
• Disprove( by counterexample ): The sum of two
irrationals is irrational.
•Counterexample:
–Let α be irrational.
–Then –α is irrational.
–α + (–α) = 0, which is rational.
• Theorem: Between every two distinct rationals,
there is a rational.
• Proof:
– Let r, s  Q. Assume that r < s.
– Let t = (r + s)/2.
– Then t  Q.
– We must show that r < t < s.
Given: r < s.
Add r: 2r < r + s.
Divide by 2: r < (r + s)/2 = t.
Given: r < s.
Add s: r + s < 2s.
Divide by 2: t = (r + s)/2 < s.
Therefore, r < t < s.
Divisibilty
Definition (Divisibility):
– Let m and n be integers, with m  0.
m divides n iff k, km=n.
– “m divides n” can also be expressed as
•
•
•
•
“m is a divisor of n”
“m is a factor of n”
“n is a multiple of m”
“n is divisible by m”
– Notation:
We write m|n to signify “m divides n”
Theorems: The following can be proven:
1. If m and n be positive integers, then
m|nmn
1. m | 1  m = 1 or m = -1
2. m | n  m | kn (for any integer k)
3. m | n  m | -n
4. If m | a and m | b then
•
•
m|a+b
m | ab
5. m | (a + b)  m | a  m | b
If m and n be positive integers, then m | n  m  n
Proof:
Let m | n .
Then km = n for some integer k (by defn of the ‘|’)
Either (1) k < 0, or (2) k = 0, or (3) k > 0.
k cannot be negative (because LHS: km < 0, RHS: n > 0)
k cannot be 0
(because LHS: km = 0, RHS: n > 0)
So k is positive, meaning that k  1
Therefore km  m (multiply both sides by m)
So n  m
But n = km
If m and n be positive integers, then
n
m|nm
Proof:
Let m | n .
Then km = n for some integer k (by defn of the ‘|’)
Either (1) k < 0, or (2) k = 0, or (3) k > 0.
k cannot be negative (because LHS: km < 0, RHS: n > 0)
k cannot be 0
(because LHS: km = 0, RHS: n > 0)
So k is positive, meaning that k  1
Therefore km  m (multiply both sides by m)
But n = km
So n  m
Given any integers m and n,
m|n
m | kn (where k is any integer)
Proof:
Let m | n.
Then there is some integer j such that jm = n.
definition of ‘|’)
Therefore (kj)m = kn (for any integer k).
Therefore m | kn (for any integer k).
(by
Given any integers m and n,
m | n  m | -n
Proof:
Let m | n
Therefore there is some integer k such that
km = n (by defn of ‘|’).
Therefore (-k)m = -n.
(by defn of ‘|’).
Therefore m | -n
Given any integers m, a, b,
i. m | a  m | b  m | a + b
ii. m | a  m | b  m | ab
Proof of (i):
Assume: m | a  m | b.
Therefore km = a and jm = b (for some integers k
and j – defn of ‘|’)
Therefore km + jm = a + b
Therefore (k+j)m = a + b
Therefore m | a + b. (by defn of ‘divides’)
Given any integers m, a, b,
i. m | a  m | b  m | a + b
ii. m | a  m | b  m | ab
Proof of (ii) left as an exercise
Given any integers m, a, b,
m | (a + b)  m | a  m | b
Proof left as an exercise
(Fundamental Theorem of Arithmetic / Unique
Factorization Theorem.)
Informally stated:
“Any positive integer that is greater than 1 can be
written as a product of primes, where this product is
unique (except for the arrangement of the primes).”
– You need not know the proof to this theorem.
– Please refer to recommended text p136-p137 for details, since it gives a
more formal/precise definition.
Primes are the atomic building blocks of numbers.
3.3.1 Examples
• 2 = 21
• 3 = 31
• 4 = 22
• 5 = 51
• 6 = 2131
• 7 = 71
• 8 = 23
• 9 = 32
• 10 = 2151
•
•
•
•
•
•
•
•
•
11 = 111
12 = 22 31
13 = 131
14 = 2171
15 = 3151
16 = 24
17 = 171
18 = 2132
19 = 191
• 10000 = 2454
• 19500 =
233154131
• 39616304 =
2472133231
(Quotient-Remainder Theorem)
Given any integer n, and positive integer d, there
exists unique integers q and r such that n = qd + r
and 0  r < d.
(Proof not needed for the moment)
The Q-R thm is useful for a starting point to
reason by cases.
Div and mod
n div d = the integer quotient obtained when n is divided by d
n mod d = the integer remainder obtained when n is divided by d
n div d = q and n mod d = r
0r <d
Page 142-146, all examples

n = d.q + r, where q and r are integers and
Prove that the square of any odd integer has the form of 8m + 1
for some integer m.
Proof:
Let n be any odd integer.
By the Q-R thm, n can be written in one of the forms:
4q or 4q + 1 or 4q + 2 or 4q + 3.
n cannot be in the form 4q or 4q + 2 (because n would then be even).
So n has to be either (1) 4q+1 or (2) 4q+3.
Case 1: n = 4q + 1, n2 = (4q+1)2
= 16q2 + 8q + 1
= 8(2q2 + q) + 1. (which is in the form of 8m + 1)
Case 2: n = 4q + 3, n2 = (4q+3)2
= 16q2 + 24q + 9
= 16q2 + 24q + 8 + 1
= 8(2q2 + 3q + 1) + 1. (which is in the form of 8m + 1)
In either case, n2 has the form of 8m + 1.
Definition (Common Divisor):
– Let m and n be integers.
d is the common divisor of m and n
Iff
d | m and d | n
Definition (Greatest Common Divisor):
– Let m and n be integers.
d is the greatest common divisor (gcd) of m and n
Iff
d is the common divisor of m and n
and ("k, k | m  k | n  k  d)
– Notation: if d is the gcd of m and n, we write:
gcd(m,n) = d
• Why study mathematical theory?
– Application of theory to programming makes a
difference between a fast algorithm and a slow
one.
– You don’t just want to ‘write a program’, but you
want to ‘write a good program’.
• Example: Write a program to compute the gcd
of two numbers.
int gcd(int m, int n) {
int greatest_so_far = 1;
for (int d = 1; d <= m; d++) {
if (m % d == 0 && n % d == 0)
greatest_so_far = d;
}
return greatest_so_far;
}
• Yes, it works… but there’s a faster way of
doing it… But first, you need to have some
mathematical theory.
Theorem:
If we are given integers a, b, q, r (a  b) such that a = bq + r, and
0  r < q, then (1) gcd(a,b) = gcd(b,r)= gcd(b,a mod b); (2) r <
a/2
Proof of (1):
Let gcd(a,b) = d and gcd(b,r) = e.
d = gcd(a,b)
 d | a  d | b (by defn of gcd)
 d | bq
(since d | b and by thm3.2.3: m|n  m|kn)
 d | bq + r (since d | a and a = bq + r)
d|r
(by thm3.2.6: m | a + b  m | a  m | b)
d|bd|r
 d is a common divisor of b and r
 d  e (by defn: e is the greatest common divisor of b and r)
Theorem:
If we are given integers a, b, q, r such that a = bq + r, and 0  r < b,
then (1) gcd(a,b) = gcd(b,r); (2) r < a/2
Let gcd(a,b) = d and gcd(b,r) = e.
e = gcd(b,r)
 e | b  e | r (by defn of gcd)
 e | bq
(since e | b and by thm3.2.3: m|n  m|kn)
 e | bq + r (since e | bq and e | r and by thm3.2.5(i):
m|a  m|b  m|(a+b))
e|a
(since: a = bq + r)
e|ae|b
 e is a common divisor of a and b
 e  d (by defn: d is the greatest common divisor of a and b)
Theorem:
If we are given integers a, b, q, r such that a = bq + r, and 0  r < q,
then (1) gcd(a,b) = gcd(b,r); (2) r < a/2
Proof of (1) (Continued):
Let gcd(a,b) = d and gcd(b,r) = e.
d = gcd(a,b)
 
de
e = gcd(b,r)
 
ed
d  e and e  d
Therefore d = e.
And so gcd(a,b) = gcd(b,r)
Theorem:
If we are given integers a, b, q, r such that a = bq + r, and 0  r < b,
then (1) gcd(a,b) = gcd(b,r); (2) r < a/2
Proof of (2) left as an exercise.
• A better program to compute the gcd of two numbers
int gcd(int a, int b) {
// assume a >= b, otherwise swap the numbers
if (b != 0) {
// We know that a = qb + r…
// …and that gcd(a,b) = gcd(b,r)
return gcd(b,a % b)
} else {
return a;
}
}
• Why is it better? Because theorem 3.4 states that r < a/2.
This means we are reducing the numbers by at least half,
for every two iterations: Faster program!!!
• See how theory is used to improve programming?
• Theorem: For any integer n, n3 – n is a multiple of 6.
• Proof:
– Divide n by 6 to get q and r: n = 6q + r, where 0  r < 6.
– Substitute: n3 – n = (6q + r)3 – (6q + r).
– Expand and rearrange:
n3 – n = 6(36q3 + 18q2r + 3qr2 – q) + (r3 – r).
3
3
 Therefore, 6 | (n – n) if and only if 6 | (r – r).
 Consider the 6 possible cases:
3
3
 Case 1: r = 0. r – r = 0 – 0 = 0 = 60.
3
3
 Case 2: r = 1. r – r = 1 – 1 = 0 = 60.
3
3
 Case 3: r = 2. r – r = 2 – 2 = 6 = 61.
3
3
 Case 4: r = 3. r – r = 3 – 3 = 24 = 64.
3
3
 Case 5: r = 4. r – r = 4 – 4 = 60 = 610.
3
3
 Case 6: r = 5. r – r = 5 – 5 = 120 = 620.
3
 In every case, 6 | (r – r).

Therefore, 6 | (r3 – r) in general.

Therefore, 6 | (n3 – n) for all integers n.
Positive and Negative Statements
• A positive statement asserts the existence of a
number.
• A negative statement asserts the nonexistence
of a number.
• It is much easier to use a positive hypothesis
than a negative hypothesis.
• It is much easier to prove a positive conclusion
than a negative conclusion.
• “r is rational” is a positive statement.
– It asserts the existence of integers a and b such that r
= a/b.
• “α is irrational” is a negative statement.
– It asserts the nonexistence of integers a and b such
that α = a/b.
Form of Proof by Contraposition
• Theorem: p  q.
• This is logically equivalent to ~q  ~p.
• Outline of the proof of the theorem:
– Assume ~q.
– Prove ~p.
– Conclude that p  q.
• This is a direct proof of the contrapositive.
Benefit of Proof by
Contraposition
• If p and q are negative statements, then ~p
and ~q are positive statements.
• We may be able to give a direct proof that
~q  ~p.
Example: Proof by
Contraposition
• Theorem: The sum of a rational and an
irrational is irrational.
• Restate the theorem: Let r be a rational
number and let α be a number. If α is
irrational, then r + α is irrational.
• Restate again: Let r be a rational number
and let α be a number. If r + α is rational,
then α is rational.
• Proof:
–
–
–
–
–
Let r be rational and α be a number.
Suppose that r + α is rational.
Let s = r + α. Then α = s – r, which is rational.
Therefore, if r + α is rational, then α is rational.
It follows that if α is irrational, then r + α is
irrational.
• Definition: An integer u is a unit if u | 1.
• The only units are 1 and –1.
 Definition: An integer n is composite if there exist non-units a
and b such that
n = ab.
 A composite number factors in a non-trivial way.
 An integer p is prime if p is not a unit and p is not composite.
 Page 132, 135, 138
• Theorem: If u and v are units, then uv is a unit.
• Proof:
– Let u and v be units.
– There exist integers r and s such that ur = 1 and vs = 1.
– Therefore, (ur)(vs) = 1.
– Rearrange: (uv)(rs) = 1.
– Therefore, uv is a unit.
• Theorem: Let a and b be integers. If a | b and
b | a, then a/b and
b/a are units.
• Proof:
– Let a and b be integers.
– Suppose a | b and b | a.
– There exist integers c and d such that ac = b and bd = a.
– Therefore, acd = bd = a.
– Therefore, cd = 1.
– Thus, c and d are units.
• Corollary: If a | b and b | a, then a = b or a = –b.
Example: Proof by Contraposition
• Theorem: If u is a unit and p is prime, then up is prime.
• Restatement: Let u be unit and p be an integer. If p is a prime, then
up is a prime.
• 2nd Restatement: Let u be unit and p be an integer. If up is not a
prime, then p is not a prime.

Case 1: up is a unit.





Case 2: up is composite.
There exist non-units b and c such that up = bc.
 Then p = (uv)p = (up)v = (bc)v = (bv)c.
 bv and c are non-units.
 Therefore, p is composite.
 Therefore, p is not a prime.
In both cases p is not a prime.
Therefore p is not a prime in general.
Therefore, if p is prime, then up is prime.




Then (up)v is a unit.
However, (up)v = (uv)p = p.
Therefore, p is a unit.
Therefore, p is not a prime.
• Theorem: p  q.
• Outline of the proof of the theorem :
– Assume ~(p  q).
– This is equivalent to assuming p  ~q.
– Derive a contradiction, i.e., conclude r  ~r for some statement r.
– Conclude that p  q.
 Sometimes a proof by contradiction “becomes” a proof by
contraposition.
 Here is how it happens.
 Assume ~(p  q), i.e., p  ~q.
 Prove ~p.
 Cite the contradiction p  ~p.
 Conclude that p  q.
 Is this proof by contradiction or by contraposition?
 Proof by contraposition is preferred.
• Theorem: An integer p is prime if and only if, for
all integers a and b, if p | ab, then p | a or p | b.
• In symbols, p is prime if and only if
"a, b  Z, (p | ab  p | a  p | b)
• This is a positive characterization of primes.
• It may allow a direct proof rather than a proof by
contradiction or contraposition.
• Theorem: If u is a unit and p is prime, then up is prime.
• Proof:
– Let u be a unit and p a prime.
– There is an integer v such that uv = 1.
– Let a and b be integers and suppose that up | ab.
– There exists an integer c such that upc = ab.
– Therefore, p | ab.
 Thus, p | a or p | b, since p is prime.
 Case 1: p | a.
 Then there exists an integer d such that pd = a.
 Then (up)(dv) = (uv)(pd) = a.
 Therefore, up | a.
 Case 2: p | b.
 Similar to Case 1.
 Therefore, up | a or up | b.
 Therefore, up is prime.
Section 3.7
Classical Theorem #1
• Theorem: 2 is irrational.
• Proof (Euclid):
– Suppose 2 is rational.
– There exist integers a and b such that 2 = a/b.
– Assume that a and b are relatively prime.
– Square: 2b2 = a2.
– Therefore, 2 | a2 and so 2 | a.
2
2
 Substitute 2c for a: 2b = 4c .
2
2
 Simplify: b = 2c .
2
 Therefore, 2 | b and so 2 | b.
 This contradicts the assumption that a and b are relatively
prime.
 Therefore, 2 is irrational.
Classical Theorem #2
– Page 164,165
• Theorem: The set of prime numbers is infinite.
• Proof:
–
–
–
–
–
–
Suppose there are only finitely many primes.
Let {p1, …,pn} be a complete list of the primes.
Let k = (p1  …  pn) + 1.
k  2, yet pi does not divide k for any i.
This is a contradiction.
Therefore, there are infinitely many primes.
• Theorem: Between any two distinct irrationals there is a rational
and an irrational.
• Proof:
– Let α and β be irrational numbers with α < β.
– Then β – α > 0.
– Choose an integer n such that n(β – α) > 1.
– Then 1/n < β – α.
 Let m = nβ – 1.
 Then
m < nβ  m + 1.
 Then m/n < β and nβ – 1  m.
 Then α < β – 1/n = (nβ – 1)/n  m/n.
 Therefore, α < m/n < β.

Choose an integer k such that
k(β – m/n) > 2.

Divide by k:
β – m/n > 2/k.

Then β > m/n + 2/k.

Therefore,
α < m/n < m/n + 2/k < β.