Chapter 4.7 & 4.8 - Help-A-Bull

Report
Quotient-Remainder Theory,
Div and Mod
If  and  are integers and  > 0, then
   =  and    = 
⟺
 =  + 
where  and  are integers and 0 ≤  < .
Quotient: q =    =


Reminder: r =    =  − 
1
Exercise
Prove that for all integers a and b, if a mod 7
= 5 and b mod 7 = 6 then ab mod 7 = 2.
What values are , , and ?
2
Exercise
Prove that for all integers a and b, if a mod 7
= 5 and b mod 7 = 6 then ab mod 7 = 2.
Hint:  = 7
 = 7 + 5, b = 7 +6
 = 7 + 5 7 + 6
= 49 + 42 + 35 + 30
= 7 7 + 6 + 3 + 4 + 2
3
Floor & Ceiling
Definition:
• Floor: If  is a real number and  is an integer, then
 = ⟺  ≤ <+1
• Ceiling: if  is a real number and  is an integer, then
 = ⟺ −1< ≤

+1

floor of  = 

−1

ceiling of  = 
4
Relations between Proof by Contradiction
and Proof by Contraposition
• To prove a statement
∀ in , if   then ()
• Proof by contraposition proves the statement by giving a direct proof
of the equivalent statement
∀ in , if   is false then   is false
Suppose  is an arbitrary
element of  such that ~()
Sequence of steps
~()
• Proof by contradiction proves the statement by showing that the
negation of the statement leads logically to a contradiction.
Suppose ∃ in  such
that () and ~()
Same sequence of steps
Contradiction:
() and ~()
5
Summary of Chapter 4
• Number theories:
– Even, odd, prime, and composite
– Rational, divisibility, and quotient-remainder theorem
– Floor and ceiling
– The irrationality of 2 and gcd
• Proofs:
– Direct proof and counterexample
– Indirect proof by contradiction and contraposition
6
The Irrationality of 2
How to proof:
• Direct proof?
• Proof by contradiction?
• Proof by contraposition?
If  is a real number, then

 is rational ⇔ ∃ integers  and  such that  = and  ≠ 0.

A real number that is not rational is irrational.
7
The Irrationality of 2
Proof by contradiction:
Starting point:
Negation: 2 is rational.
To show:
A contradiction.

2 = , where  and  are integers with no common factors and  ≠ 0,

by definition of rational.
2 = 22 , by squaring and multiplying both sides with 2
2 is even, then  is even. Let  = 2 for some integer .
(2)2 = 4 2 = 22 , by substituting  = 2 into 2 = 22 .
2 is even, and so  is even.
Hence both  and  have a common factor of 2.
8
Irrationality of 1 + 3 2
Proof by contradiction:
Starting point:
Negation: 1 + 3 2 is rational.
To show:
A contradiction.
9
Irrationality of 1 + 3 2
Proof by contradiction:
By definition of rational,

1 + 3 2 =  for some integers  and  with  ≠ 0.
It follows that




=−
−
= 
3 2= −1
by subtracting 1 from both sides
by substitution
by the rule for subtracting fractions
with a common denominator
Hence,
2=
−
3
by dividing both sides by 3.
 −  and 3 are integers and 3 ≠ 0 by the zero product property.
Hence 2 is quotient of the two integers  −  and 3 with 3 ≠ 0, so 2 is rational
by the definition of rational. This contradicts the fact that 2 is irrational.
10
Property of a Prime Divisor
Proposition 4.7.3
For any integer  and any prime number , if | then  | ( + 1)
If a prime number divides an integer, then it does not divide the next successive
integer.
Starting point: there exists an integer  and a prime number  such that  |  and
 | ( + 1).
To show: a contradiction.
 =  and  + 1 =  for some integers  and  by definition of divisibility.
It follows that
1 = ( + 1) −  =  −  = ( −  ),
 −  = 1/, by dividing both sides with .
 > 1 because  is prime, hence, 1/ is not an integer, thus  −  is not an
integer, which is a contradict  −  is an integer since  and  are integers.
if  and  are integers and  ≠ 0:
|
⟺
∃ an integer  such that  =  ∙ 
Infinitude of the Primes
Theorem 4.7.4 Infinitude of the Primes
The set of prime numbers is infinite.
Proof by contradiction:
Starting point: the set of prime number is finite.
To show: a contradiction.
Assume a prime number  is the largest of all the prime numbers 2, 3, 5, 7, 11, . . . , .
Let  be the product of all the prime numbers plus 1:
 = (2 · 3 · 5 · 7 · 11 · · · ) + 1
Then  > 1, and so, by Theorem 4.3.4 (any integer larger than 1 is divisible by a
prime number) ,  is divisible by some prime number q. Because q is prime, q must
equal one of the prime numbers 2, 3, 5, 7, 11, . . . , .
Thus, by definition of divisibility,  divides 2 · 3 · 5 · 7 · 11 · · · , and so, by
Proposition 4.7.3,  does not divide (2 · 3 · 5 · 7 · 11 · · · ) + 1, which equals .
Hence N is divisible by q and N is not divisible by q, and we have reached a
contradiction. [Therefore, the supposition is false and the theorem is true.]
12
Greatest Common Divisor (GCD)
• The greatest common divisor of two integers a and b is the largest
integer that divides both  and .
Definition
Let  and  be integers that are not both zero. The greatest common divisor of
 and , denoted gcd(a, b), is that integer  with the following properties:
1.  is common divisor of both a and b, in other words,
 | , and  | .
2. For all integers , if  is a common divisor of both  and , then  is less than
or equal to . In other words,
for all integers , if  | , and  |, then c ≤ .
Exercise:
• gcd 72,63 = 9, since 72 = 9 ∙ 8 and 63 = 9 ∙ 7
• gcd 1020 , 630 = 220 , since 1020 = 220 ∙ 520 and 630 = 230 ∙ 330
13
Greatest Common Divisor (GCD)
Lemma 4.8.1
If  is a positive integer, then gcd(, 0) = .
Proof:
Suppose  is a positive integer. [We must show that the greatest common divisor
of both  and 0 is .]
1.  is a common divisor of both  and 0 because r divides itself and also 
divides 0 (since every positive integer divides 0).
2. No integer larger than  can be a common divisor of  and 0 (since no integer
larger than  can divide ).
Hence  is the greatest common divisor of  and 0.
14
Greatest Common Divisor (GCD)
Lemma 4.8.2
If  and  are any integers not both zero, and if  and  are any integers
such that  =  + , then
gcd(, ) = gcd(, )
Proof:
[The proof is divided into two sections: (1) proof that gcd(, ) ≤ gcd(,  ), and
(2) proof that gcd(,  ) ≤ gcd(, ). Since each gcd is less than or equal to the
other, the two must be equal.]
1. gcd(, ) ≤ gcd(, ):
a. [We will first show that any common divisor of  and  is also a common
divisor of  and .]
Let  and  be integers, not both zero, and let  be a common divisor of 
and . Then  |  and  | , and so, by definition of divisibility,  = 
and  = , for some integers  and . Now substitute into the equation
 =  + 
to obtain
 = () + .
15
Greatest Common Divisor (GCD)
Lemma 4.8.2
If  and  are any integers not both zero, and if  and  are any integers
such that  =  + , then
gcd(, ) = gcd(, )
Proof (cont’):
1. gcd(, ) ≤ gcd(, ):
a. [We will first show that any common divisor of  and  is also a common
divisor of  and .]
 = () + .
Then solve for  :
 =  − () = ( − ).
But  −  is an integer, and so, by definition of divisibility,  |  . Because
we already know that  | , we can conclude that  is a common divisor of 
and  [as was to be shown].
16
Greatest Common Divisor (GCD)
Lemma 4.8.2
If  and  are any integers not both zero, and if  and  are any integers such
that  =  + , then
gcd(, ) = gcd(, )
Proof (cont’):
1. gcd(, ) ≤ gcd(, ):
b. [Next we show that gcd(, ) ≤ gcd(, ).]
By part (a), every common divisor of  and  is a common divisor of  and
 . It follows that the greatest common divisor of  and  is defined because
 and  are not both zero, and it is a common divisor of  and  . But then
gcd(, ) (being one of the common divisors of  and ) is less than or equal
to the greatest common divisor of  and  :
gcd(, ) ≤ gcd(,  ).
2.
gcd(, ) ≤ gcd(, ):
The second part of the proof is very similar to the first part. It is left as an
exercise.
17
The Euclidean Algorithm
• Problem:
– Given two integer A and B with  >  ≥ 0, find gcd(, )
• Idea:
– The Euclidean Algorithm uses the division algorithm repeatedly.
– If B=0, by Lemma 4.8.1 we know gcd(, ) = .
– If B>0, division algorithm can be used to calculate a quotient  and
a remainder :
 =  +  where 0 ≤  < 
– By Lemma 4.8.2, we have gcd(, ) = gcd(, ), where  and 
are smaller numbers than  and .
• gcd(, ) = gcd(, ) = ⋯ = gcd(, 0) = 
 =   
18
The Euclidean Algorithm - Exercise
Use the Euclidean algorithm to find gcd(330, 156).
19
The Euclidean Algorithm - Exercise
Use the Euclidean algorithm to find gcd(330, 156).
Solution:
gcd(330,156) = gcd(156, 18) 330 mod 156 = 18
= gcd(18, 12)
156 mod 18 = 12
= gcd(12, 6)
18 mod 12 = 6
= gcd(6, 0)
12 mod 6 = 0
=6
20
An alternative to Euclidean Algorithm
If  ≥  > 0, then gcd(, ) = gcd(,  − )
21
An alternative to Euclidean Algorithm
If  ≥  > 0, then gcd(, ) = gcd(,  − )
Hint:
Part 1: proof gcd(, ) ≤ gcd(,  − )
every common divisor of a and b is a common
divisor of b and a-b
Part 2: proof gcd(, ) ≥ gcd(,  − )
every common divisor of b and a-b is a common
divisor of a and b.
22
Homework #5 Problems
Converting decimal to rational numbers.
4.2.2: 4.6037
4.2.7: 52.4672167216721…
23
Homework #5 Problems
1. Converting decimal to rational numbers.
4.2.2: 4.6037
Solution: 4.6037 =
4.6037
10000
∗ 10000 =
46037
10000
4.2.7: 52.4672167216721…
Solution: let X = 52.4672167216721 . . .
100000x = 5246721.67216721….
10x = 524.67216721…
100000x – 10x = 5246197 X = 5246197 / 99990
24
Exercise
Prove that for any nonnegative integer , if the sum of the
digits of  is divisible by 9, then  is divisible by 9.
Hint:
by the definition of decimal representation
 =  10 + −1 10−1 + ⋯ + 1 101 + 0
where  is nonnegative integer and all the  are integers
from 0 to 9 inclusive.
 =  10 + −1 10−1 + ⋯ + 1 101 + 0
=  (9999 ⋯ 999 + 1) + −1 (9999 ⋯ 999 + 1) + ⋯ + 1 (9 + 1) + 0
 9′ 
−1 9′ 
= 9  11 ⋯ 11 + −1 11 ⋯ 11 + ⋯ + 1 +  + −1 + ⋯ + 1 + 0
 1′ 
−1 1′ 
= an integer divisible by 9 + the sum of the digits of 
25
Homework #5 Problems
Theorem: The sum of any two even integers equals 4k for
some integer k.
“Proof: Suppose m and n are any two even integers. By
definition of even, m = 2k for some integer k and n = 2k
for some integer k. By substitution,
m + n = 2k + 2k = 4k.
This is what was to be shown.”
What’s the mistakes in this proof?
26

similar documents