Integer Division, Modulus, and Parity
For each of the following values of
n
and
d
, find integers
q
and
r
such that
n
=
dq
+
r
and 0 ≤
r
<
d
.
a
.
n
=
5
4
,
d
=
4
b
.
n
=
–
5
4
,
d
=
4
c
.
n
=
5
4
,
d
=
7
0
Solution:
a.
54 = (4)(13) + 2, and so
q
= 13 and
r
= 2
b.
–54 = (4)(–14) + 2, and so
q
= –14 and
r
= 2
c.
54 = (70)(0) + 54, and so
q
= 0 and
r
= 54
Direct Proof and Counterexample IV: Division into
Cases and the Quotient-Remainder Theorem
div and mod
A number of computer languages have built-in functions
that enable you to compute values of
q
and
r
for the
quotient-remainder theorem.
•
d
i
v
a
n
d
m
o
d
i
n
P
a
s
c
a
l
•
/ and % in C, C++, and Java
•
/
(
o
r
\
)
a
n
d
m
o
d
i
n
.
N
E
T
The functions give the values that satisfy the
quotient-remainder theorem when a
nonnegative
integer
n
is divided by a positive integer
d
and the result is assigned
to an integer variable.
div and mod
However, they do not give the values that satisfy the
quotient-remainder theorem when a negative integer
n
is
divided by a positive integer
d
.
div and mod
For instance, to compute
n div d
for a nonnegative integer
n
and a positive integer
d
, you just divide
n
by
d
and ignore
the part of the answer to the right of the decimal point.
To find
n
mod
d
, you can use the fact that if
n
=
dq
+
r
then
r
=
n
–
dq
. Thus,
n
=
d
(
n
div
d
) +
n
mod
d
and so
n
mod
d
=
n
–
d
(
n
div
d
)
Compute 32 div 9 and 32 mod 9 by hand.
Solution:
Performing the division by hand gives:
Discarding the fractional part gives 32 div 9 = 3, and so
32 mod 9 = 32 – 9 (32 div 9) = 32 – 27 = 5
Example 2 –
Computing div and mod
Representations of Integers
Theorem
: Any integer is either even or odd (but not both).
Proof: Let
n
be any integer. By the quotient-remainder
theorem (with
d
= 2), there exist unique integers
q
and
r
such that
n
= 2
q
+
r
and 0 ≤
r
< 2
But the only integers that satisfy 0 ≤
r
< 2 are
r
= 0 and
r
= 1.
Thus, there exists an integer
q
with
n
= 2
q
+ 0 or
n
= 2
q
+ 1
In the first case,
n
is even. In the second,
n
is odd. The
uniqueness of
q
and
r
means
n
cannot be both.
Representations of Integers
The
parity
of an integer refers to whether the integer is
even or odd.
For instance, 5 has odd parity and 28 has even parity.
W
e
c
a
l
l
t
h
e
f
a
c
t
t
h
a
t
a
n
y
i
n
t
e
g
e
r
i
s
e
i
t
h
e
r
e
v
e
n
o
r
o
d
d
t
h
e
p
a
r
i
t
y
p
r
o
p
e
r
t
y
.
Example 5 –
Consecutive Integers Have Opposite Parity
Two integers are called
consecutive
if, and only if, one is
one more than the other. So if one integer is
m
, then the
next consecutive integer is
m
+ 1.
Theorem
: For any two consecutive integers, one is even
and the other is odd.
Proof: Let
m
be any integer. We need to prove that if
m
is
even, then
m
+1 is odd, and if
m
is odd, then
m
+1 is even.
Example 5 –
Solution
C
a
s
e
1
:
m
i
s
e
v
e
n
.
T
h
e
n
,
m
= 2
k
for some integer
k
, by the definition of “even”
m
+ 1 = 2
k
+ 1 is odd, by the definition of “odd”
C
a
s
e
2
:
m
i
s
o
d
d
.
T
h
e
n
,
m
= 2
k
+ 1 for some integer
k
, by the definition of “odd”
m
+ 1 = 2
k
+ 2 = 2(
k
+ 1) is even, by the definition of “even”
(since
k
+1 is an integer)
cont’d
Proof by Division into Cases
First assume
A
1
is true and deduce
C
; next assume
A
2
is
true and deduce
C
; and so forth until you have assumed
A
n
is true and deduced
C
.
At that point, you can conclude that regardless of which
statement
A
i
happens to be true, the truth of
C
follows
.
Example 6 –
Representations of Integers Modulo 4
Lemma
: Any integer can be written in one of the four forms
n
= 4
q
or
n
= 4
q
+ 1 or
n
= 4
q
+ 2 or
n
= 4
q
+ 3
for some integer
q
.
Proof: Given any integer
n
, apply the quotient-remainder
theorem to
n
with
d
= 4.
This implies that there exist an integer quotient
q
and a
remainder
r
such that
n
= 4
q
+
r
and 0 ≤
r
< 4
But the only nonnegative remainders
r
that are less than 4
are 0, 1, 2, and 3.
Example 7
P
r
o
o
f
:
S
u
p
p
o
s
e
n
i
s
a
n
o
d
d
i
n
t
e
g
e
r
.
B
y
t
h
e
p
r
e
c
e
d
i
n
g
l
e
m
m
a
,
n
c
a
n
b
e
w
r
i
t
t
e
n
i
n
o
n
e
o
f
t
h
e
f
o
r
m
s
n
= 4
q
or
n
= 4
q
+ 1 or
n
= 4
q
+ 2 or
n
= 4
q
+ 3
for some integer
q
.
In fact, since
n
is odd and 4
q
and 4
q
+ 2 are even,
n
must
have one of the forms
n
= 4
q
+ 1 or
n
= 4
q
+ 3
Example 7 –
Solution
C
a
s
e
1
(
n
=
4
q
+
1
f
o
r
s
o
m
e
i
n
t
e
g
e
r
q
)
:
cont’d
Let Then
m
is an integer since 2 and
q
are
integers and sums and products of integers are integers.
Thus, substituting,
where
m
is an integer.
Example 7 –
Solution
C
a
s
e
2
(
n
=
4
q
+
3
f
o
r
s
o
m
e
i
n
t
e
g
e
r
q
)
:
cont’d
Let Then
m
is an integer since 1, 2, 3,
and
q
are integers and sums and products of integers are
integers.
Thus, substituting, where
m
is an integer.
Representations of Integers
Note that the result of Theorem 4.4.3 can also be written,
“For any odd integer
n
,
n
2
mod
8 = 1.”
In general, according to the quotient-remainder theorem, if
an integer
n
is divided by an integer
d
, the possible
remainders are 0, 1, 2, . . ., (
d
– 1).
This implies that
n
can be written in one of the forms
for some integer
q.
The triangle inequality is one of the most important results
involving absolute value. It has applications in many areas
of mathematics.
Absolute Value and the Triangle Inequality
A
l
e
m
m
a
i
s
a
s
t
a
t
e
m
e
n
t
t
h
a
t
d
o
e
s
n
o
t
h
a
v
e
m
u
c
h
i
n
t
r
i
n
s
i
c
i
n
t
e
r
e
s
t
b
u
t
i
s
h
e
l
p
f
u
l
i
n
d
e
r
i
v
i
n
g
o
t
h
e
r
r
e
s
u
l
t
s
.
Absolute Value and the Triangle Inequality
Lemmas 4.4.4 and 4.4.5 now provide a basis for proving
the triangle inequality.
Absolute Value and the Triangle Inequality
Explore the concepts of integer division, modulus, and the parity of integers through the quotient-remainder theorem. Learn how to compute div and mod manually and understand the representation of integers as even or odd. Discover how these principles apply in computer languages and the unique properties of integers.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Direct Proof and Counterexample IV: Division into Cases and the Quotient-Remainder Theorem For each of the following values of n and d, find integers q and r such that n = dq + r and 0 r < d. a. n = 54, d = 4 b. n = 54, d = 4 c. n = 54, d = 70 Solution: a. 54 = (4)(13) + 2, and so q = 13 and r = 2 b. 54 = (4)( 14) + 2, and so q = 14 and r = 2 c. 54 = (70)(0) + 54, and so q = 0 and r = 54 1
div and mod A number of computer languages have built-in functions that enable you to compute values of q and r for the quotient-remainder theorem. div and mod in Pascal / and % in C, C++, and Java / (or \) and mod in .NET The functions give the values that satisfy the quotient-remainder theorem when a nonnegative integer n is divided by a positive integer d and the result is assigned to an integer variable. 2
div and mod However, they do not give the values that satisfy the quotient-remainder theorem when a negative integer n is divided by a positive integer d. 3
div and mod For instance, to compute n div d for a nonnegative integer n and a positive integer d, you just divide n by d and ignore the part of the answer to the right of the decimal point. To find n mod d, you can use the fact that if n = dq + r then r = n dq. Thus, n = d (n div d) + n mod d and so n mod d = n d (n div d) 4
Example 2 Computing div and mod Compute 32 div 9 and 32 mod 9 by hand. Solution: Performing the division by hand gives: Discarding the fractional part gives 32 div 9 = 3, and so 32 mod 9 = 32 9 (32 div 9) = 32 27 = 5 5
Representations of Integers Theorem: Any integer is either even or odd (but not both). Proof: Let n be any integer. By the quotient-remainder theorem (with d = 2), there exist unique integers q and r such that n = 2q + rand 0 r < 2 But the only integers that satisfy 0 r < 2 are r = 0 and r = 1. Thus, there exists an integer q with n = 2q + 0 or n = 2q + 1 In the first case, n is even. In the second, n is odd. The uniqueness of q and r means n cannot be both. 6
Representations of Integers The parity of an integer refers to whether the integer is even or odd. For instance, 5 has odd parity and 28 has even parity. We call the fact that any integer is either even or odd the parity property. 7
Example 5 Consecutive Integers Have Opposite Parity Two integers are called consecutive if, and only if, one is one more than the other. So if one integer is m, then the next consecutive integer is m + 1. Theorem: For any two consecutive integers, one is even and the other is odd. Proof: Let m be any integer. We need to prove that if m is even, then m+1 is odd, and if m is odd, then m+1 is even. 8
Example 5 Solution cont d Case 1:m is even. Then, m = 2k for some integer k, by the definition of even m + 1 = 2k + 1 is odd, by the definition of odd Case 2: m is odd. Then, m = 2k + 1 for some integer k, by the definition of odd m + 1 = 2k + 2 = 2(k + 1) is even, by the definition of even (since k+1 is an integer) 9
Proof by Division into Cases First assume A1 is true and deduce C; next assume A2 is true and deduce C; and so forth until you have assumed An is true and deduced C. At that point, you can conclude that regardless of which statement Ai happens to be true, the truth of C follows. 10
Example 6 Representations of Integers Modulo 4 Lemma: Any integer can be written in one of the four forms n = 4q or n = 4q + 1 or n = 4q + 2 or n = 4q + 3 for some integer q. Proof: Given any integer n, apply the quotient-remainder theorem to n with d = 4. This implies that there exist an integer quotient q and a remainder r such that n = 4q + rand 0 r < 4 But the only nonnegative remainders r that are less than 4 are 0, 1, 2, and 3. 11
Example 7 Proof: Suppose n is an odd integer. By the preceding lemma, n can be written in one of the forms n = 4q or n = 4q + 1 or n = 4q + 2 or n = 4q + 3 for some integer q. In fact, since n is odd and 4q and 4q + 2 are even, n must have one of the forms n = 4q + 1 or n = 4q + 3 12
Example 7 Solution cont d Case 1(n = 4q + 1 for some integer q): Let Then m is an integer since 2 and q are integers and sums and products of integers are integers. Thus, substituting, where m is an integer. 13
Example 7 Solution cont d Case 2 (n = 4q + 3 for some integer q): Let Then m is an integer since 1, 2, 3, and q are integers and sums and products of integers are integers. Thus, substituting, where m is an integer. 14
Representations of Integers Note that the result of Theorem 4.4.3 can also be written, For any odd integer n, n2mod8 = 1. In general, according to the quotient-remainder theorem, if an integer n is divided by an integer d, the possible remainders are 0, 1, 2, . . ., (d 1). This implies that n can be written in one of the forms for some integer q. 15
Absolute Value and the Triangle Inequality The triangle inequality is one of the most important results involving absolute value. It has applications in many areas of mathematics. 16
Absolute Value and the Triangle Inequality A lemma is a statement that does not have much intrinsic interest but is helpful in deriving other results. 17
Absolute Value and the Triangle Inequality Lemmas 4.4.4 and 4.4.5 now provide a basis for proving the triangle inequality. 18
