Number theory1

Number theory




INTRODUCTION
This chapter investigates some basic properties of the natural numbers (or positive integers), that is, the set
N = {1, 2, 3, . . .}
and their “cousins,” the integers, that is, the set
Z = {. . . ,?2,?1, 0, 1, 2, . . .}
(The letter Z comes from the word “Zahlen” which means numbers in German.)
The following simple rules concerning the addition and multiplication of these numbers are assumed (where
a, b, c are arbitrary integers):
(a) Associative law for multiplication and addition:
(a + b) + c = a + (b + c) and (ab)c = a(bc)
(b) Commutative law for multiplication and addition:
a + b = b + a and ab = ba
(c) Distributive law:
a(b + c) = ab + ac
(d) Additive identity 0 and multiplicative identity 1:
a + 0 = 0 + a = a and a · 1 = 1 · a = a
(e) Additive inverse ?a for any integer a:
a + (?a) = (?a) + a = 0
264
Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.
CHAP. 11] PROPERTIES OF THE INTEGERS 265
Appendix B shows that other mathematical structures have the above properties. One fundamental property
which distinguishes the integers Z from other structures is the Principle of Mathematical Induction (Section 1.8)
which we rediscuss here. We also state and prove (Problem 11.30) the following theorem.
Fundamental Theorem of Arithmetic: Every positive integer n > 1 can be written uniquely as a product
of prime numbers.
This theorem already appeared in Euclid’s Elements. Here we also develop the concepts and methods which
are used to prove this important theorem.
11.2 ORDER AND INEQUALITIES, ABSOLUTE VALUE
This section discusses the elementary properties of order and absolute value.
Order
Observe that we define order in Z in terms of the positive integers N. All the usual properties of this order
relation are a consequence of the following two properties of N:
[P1] Ifa and b belong to N, then a + b and ab belong to N.
[P2] For any integer a, either a ? N, a = 0, or ?a ? N.
The following notation is also used:
a > b means b < a; read: a is greater than b.
a ? b means a < b or a = b; read: a is less than or equal to b.
a ? b means b ? a; read: a is greater than or equal to b.
The relations <,>, ? and ? are called inequalities in order to distinguish them from the relation = of
equality. The reader is certainly familiar with the representation of the integers as points on a straight line, called
the number line R, as shown in Fig. 11-1.
Fig. 11-1
We note that a < b if and only if a lies to the left of b on the number line R in Fig. 11-1. For example,
2 < 5; ?6 < ?3; 4 ? 4; 5 > ?8; 6 ? 0; ?7 ? 0
We also note that a is positive iff a > 0, and a is negative iff a < 0. (Recall “iff” means “if and only if.”)
Basic properties of the inequality relations follow.
Proposition 11.1: The relation ? in Z has the following properties:
(i) a ? a, for any integer a.
(ii) If a ? b and b ? a, then a = b.
(iii) If a ? b and b ? c, then a ? c.
Proposition 11.2 (Law of Trichotomy): For any integers a and b, exactly one of the following holds:
a < b, a = b, or a > b
Proposition 11.3: Suppose a ? b, and let c be any integer. Then:
(i) a + c ? b + c.
(ii) ac ? bc when c > 0; but ac ? bc when c < 0.
(Problem 11.5 proves Proposition 11.3.)
266 PROPERTIES OF THE INTEGERS [CHAP. 11
Absolute Value
The absolute value of an integer a. written |a|, is formally defined by
|a| =
-
a if a ? 0
?a if a < 0
Accordingly, |a| > 0 except when a = 0. Geometrically speaking, |a| may be viewed as the distance between
the points a and 0 on the number line R. Also, |a ? b| = |b ? a| may be viewed as the distance between the
points a and b. For example:
(a) |?3| = 3; |7| = 7; |?13| = 13; (b) |2 ? 7| = |?5| = 5; |7 ? 2| = |5| = 5
Some properties of the absolute value function follow. (Problems 11.6 and 11.7 prove (iii) and (iv).)
Proposition 11.4: Let a and b be any integers. Then:
(i) |a| ? 0, and |a| = 0 iff a = 0 (iv) |a ± b| ? |a| + |b|
(ii) ?|a| ? a ? |a| (v) ||a| ? |b|| ? |a ± b|
(iii) |ab| = |a||b|
11.3 MATHEMATICAL INDUCTION
The principle of mathematical induction stated below essentially asserts that the positive integers N begin
with the number 1 and the rest are obtained by successively adding 1. That is, we begin with 1, then 2 = 1 + 1,
then 3 = 2 + 1, then 4 = 3 + 1, and so on. The principle makes precise the vague phrase “and so on.”
Principle of Mathematical Induction: Let S be a set of positive integers with the following two properties:
(i) 1 belongs to S.
(ii) If k belongs to S, then k + 1 belongs to S.
Then S is the set of all positive integers.
We shall not prove this principle. On the contrary, when the set N of positive integers (natural numbers) is
developed axiomatically, this principle is given as one of the axioms.
There is an equivalent form of the above principle which is usually used when proving theorems:
Principle of Mathematical Induction: Let P be a proposition defined on the integers n ? 1 such that:
(i) P(1) is true.
(ii) P(k + 1) is true whenever P(k) is true.
Then P is true for every integer n ? 1.
EXAMPLE 11.1
(a) Let P be the proposition that the sum of the first n odd numbers is n2; that is:
P(n): 1 + 3 + 5+· · ·+(2n ? 1) = n2
(The nth odd number is 2n ? 1 and the next odd number is 2n + 1.)
Clearly, P(n) is true for n = 1; that is:
P(1): 1 = 12
CHAP.