The Integers

One of the most important sets in all of mathematics is the set Z of integers:

In spite of centuries of effort by the greatest mathematical minds, there are many simple problems concerning Z which cannot be settled at the present time. For example, consider the problem of Fermat which was mentioned in historical perspectives, concerning the nonexistence of nonzero solutions of the equation xⁿ + yⁿ = zⁿ, x,y,z integers, n > 3. The reader is undoubtedly familiar with the integers, and some of the properties of integers will seem like obvious consequences of everyday experiences with them. It is our intention to make use of this experience by assuming a certain number of basic properties of the integers. We will then make a number of deductions from our basic properties and will thereby prove a number of facts concerning integers which are, in some sense, less obvious than our basic properties.

It is possible to construct the integers in terms of sets and to verify all the basic properties from the properties of sets. However, this is a rather drawn-out process, and would take us far afield from our central area of interest, so we will resist the temptation to provide a complete development of the integers.

The Basic Properties of Z

In the following discussion, we will present five basic sets of properties of the integers. Mathematicians have distilled these properties of the integers during centuries of investigations. The properties which we will assume have two convenient features: They agree with our preconceived notions about the integers and they form a natural point of departure for the development of less elementary properties.

On the set of integers, there are defined two binary operations, one called addition (denoted +) and one called multiplication (denoted ·). Our first three sets of properties of the integers are just some familiar properties of + and · .

I. Properties of Addition

A1. Associativity: If a,b,c Z, then (a + b) + c = a + (b + c).

A2. Commutativity: If a,b Z, then a + b = b + a.

A3. Identity: If a Z, then a + 0 = 0 + a = a.

If a Z, then there exists a unique integer b such that a + b = b + a = 0. b is called the inverse of a with respect to addition and is denoted -a.

A4. Inverses: If a Z, then there exists a unique integer b such that a + b = b + a = 0. b is called the inverse of a with respect to addition and is denoted -a (read:minus a). Note that our notation for integers in such a way that the inverse of 2, say, is the integer -2.

II. Properties of Multiplication

M1. Associativity: If a,b,c Z, then (a · b) · c = a · (b · c).

M2. Commutativity: If a,b Z, then a · b = b · a.

M3. Identity: If a Z, then a · 1 = 1 · a = a.

III. Distributive Law

Addition and multiplication in Z are related by the distributive law which asserts that if a,b,c Z, then

At this point, let us cite some rules for calculating with integers. These rules are familiar from high school algebra and can easily be deduced from I, II, and III. Let x,y,z Z. Then we have

By way of illustration, let us prove (3). By A4, -y is the unique integer which has the property y + (-y) = 0, in particular, we set y = -x, then -(-x) is the unique integer having the property -x + [-(-x)] = 0. However, by A4, -x + x = 0. Therefore, by the uniqueness, we have x = -(-x). Hereafter, we will use rules (1)-(6) without explicit reference to them.

The elements of the set

are called positive integers. The set P of positive integers is a subset of Z. Our next set of properties concerns the positive integers.

IV. Properties of Positive Integers

Exactly one of the following is true:
a P, a = 0, -a P. If x,y P, then x · y P.

P0. Let a Z. Then exactly one of the following is true: a P, a = 0, -a P.

P1. If x, y P, then x = y P.

P2. If x, y P, then x · y P.

The set

N = P (0} = {0,1,2,3,...}

is called the set of natural numbers.

Our last basic property of Z is the principle of mathematical induction.

V. Principle of Mathematical Induction

Let S be a nonempty subset of the set of positive integers P. Assume that
(a) 1 S and
(b) whenever n S we have n + 1 S. Then S contains all positive integers.

In more formal developments of the integers, the principle of mathematical induction is the basic tool available to prove theorems and, in fact, all the preceding basic properties may be deduced by using the principle of mathematical induction and a set of axioms for N called Peano's axioms.

The principle of mathematical induction can be used to prove theorems as follows:Suppose that for each positive integer n, we have a given proposition P_n. Suppose further that we are able to show that P₁ is true and that whenever P_n is true, P_n+1 is true. Then P_n is true for every positive integer n. Indeed if S={n P | P_n is true}, then 1 S, and if n S, then n + 1 S, so that S=P by V. A useful variant of the principle of mathematical induction is given by the following:

For each positive integer n there is a proposition P_n. Suppose also that (a) P₁ is true and that (b) whenever P_m is true for all m < n, m is a positive integer, we have P_n+1 is true. Then P_n is true for every positive integer n.

V'. Variant of Mathematical Induction Principle

Suppose that for each positive integer n there is a proposition P_n. Suppose also that
(a) P₁ is true and that
(b) whenever P_m is true for all m < n, m is a positive integer, we have P_n+1 is true.
Then P_n is true for every positive integer n.

Let us illustrate the use of the principle of mathematical induction by means of a number of examples.

Example 1: Let us prove that in n is a positive integer, then

Let P_n denote this proposition. It is clear that P₁ is true since 1 = [1 · (1 + 1)]/2.If P_n is true, then

But then by adding n + 1 to both sides of the equation, we derive that

and thus P_n+1 is true. Thus, by the principle of mathematical induction, P_n is true for all n P.

Example 2: Let S be a set containing n elements. Then S contains 2ⁿ subsets.

Denote this proposition by P_n. It is clear that P₁ since if S={a} then the subsets of S are {a} and . Assume that P_n is true, and let S={a₁,...,a_n,a_n+1}. By the principle of mathematical induction, it suffices to show that S has 2ⁿ⁺¹ subsets, assuming P_n. Let S₀ = {a₁,...,a_n}. By our assumption S₀ has 2ⁿ subsets T₁,...,T_2ⁿ.Let T be a subset of S. There are two cases: If T is contained in S₀, then T is one of T₁,...,T_2ⁿ. If T is not contained in s₀, then a_n+1 T and T-{a_n+1} is contained in S₀. Thus in the second case, T-{a_n+1} is one of T₁,...,T_2ⁿ and T is one of

T₁{a_n+1},...,T_2ⁿ {a_n+1}.

We have exhibited 2 · 2ⁿ = 2ⁿ⁺¹ subsets of S. Thus P_n+1 holds and we are done.

Example 3: Definition by induction. It is possible to use mathematical induction to define various mathematical concepts. The basic idea of this process of "definition by induction" is as follows: Suppose that it is required to define a function f:PA, where A is some given set. This may be done by
(a) specifying f(1) and
(b) specifying f(n + 1) in terms of f(1),f(2),...f(n).
If S={n P | f(n) is defined}, then by V', S=P and f is defined for all positive integers n. For example, let us define the nth power aⁿ of an integer as follows:

By principle of mathematical induction, aⁿ is defined for n a positive integer or 0.

Example 4: Let x,y Z and let m and n be positive integers or 0. Then the following laws of exponents hold:

Feel free to complete the proof of these yourself.

Order

Let a and b be integers. We say that a is greater than b, denoted a>b, if a-b is a positive number. Thus, in particular, if a P, then a > 0, and conversely, if a > 0, then a P. In other words, the positive integers are precisely those which are greater than 0. If a is greater than b, then we say b is less than a, and we write b < a. We will use the notation a < b to mean that either a < b or a = b. Let us verify some of the elementary properties of the relations "greater than" and "less than."

Exactly on of the following holds:
x < y, x = y, x > y.

O1. Exactly on of the following holds: x < y, x = y, x > y.

For, by P0, exactly one of the following holds:

y-x P, y - x = 0, -(y - x) P.

In the first case x < y, while in the second x = y. Noting that -(y - x) = x - y, we see that in the third case, x > y Thus, at least one of the conditions x < y, x = y, x > y holds.

O2. If x < y, y < z, then x < z.

O3. If x < y and z < w, then x + z < y + w.

A simple application of O2 and O3 shows that there are no integers between 0 and 1. More precisely, we have

If b is a positive integer. Then b is greater than or equal to 1 Proposition 1: Suppose that b is a positive integer. Then b is greater than or equal to 1.

Proof: Let us proceed by induction. The assertion is clearly true for b = 1. Let us assume that the assertion is true for b that is b > 1. By O3 (above), we see that b + 1 > 1 + 1. However, 1 is positive, so that 1 > 0. [For if 1 were not positive, -1 would be positive by P0, therefore by P2, 1 = (-1) · (-1) is positive, which is a contradiction.] Therefore, by O3, 1 + 1 > 1 + 0 = 1. Thus, we see that

Therefore by O2

which implies our assertion for b + 1. Therefore, the proposition is proved.

Let x and y be integers. If x > y, then x > y + 1.

Corollary 2: Let x and y be integers. If x > y, then x > y + 1.

Proof: If x > y, then x-y is positive, so that by Proposition 1, x-y>1. Thus by O3, x>y + 1.

We will require one additional basic property of inequalities:

If x < y and z > 0 then xz < yz.
If x < y and z < 0 then xz > yz.

O4a. If x < y and z > 0 then xz < yz.

O4b. If x < y and z < 0 then xz > yz.

For if x < y then z > 0, then z and y - x belong to P, so that by P2, (y - x) · z = yz - xz belongs to P. Therefore, xy < yz, whence O4a. If x < y and z < 0, then -z > 0 by P0, so that by O4a, we see that x(-z) < y(-z). In other words,xz - yz = y(-z)-x(-z) P, which implies that xz > yz.

Another easy consequence of Proposition 1 is given by

Let a and b positive integers. Then there exists a positive integer n such that a < nb.

Corollary 3: Let a and b positive integers. Then there exists a positive integer n such that a < nb.

Proof: Set n = a + 1. For then n · b = ab + b. However, by Proposition 1 and O4, ab > a · 1 = a, b > 1 > 0. Therefore by O3,

A very important property of Z is the fact that if a and b are nonzero integers, then a · b is nonzero. The simplest way to see this is to divide the reasoning up into four cases: a > 0, b > 0; a > 0, b < 0; a < 0, b > 0; a < 0, b < 0. In each case, we may apply O4 to conclude that either a·b > 0 or a · b < 0. In any case, a · b 0. Let us record this important fact for later reference.

Theorem 4: Let a and b be nonzero integers. Then a · b 0.

If S is a subset of Z, then an integer s is said to be the least(or smallest )element of S if s S and s < t for all t belonging to S. Similarly s is said to be the greatest (or largest) element of S if s S and s > t for all t belonging to S. Not every subset of Z has a greatest or least element. For example, if S = Z, then S has neither a largest nor smallest element. However, it is reasonably clear from property O1 that we have the following result.

Proposition 5: Let S be a finite, nonempty subset of Z. Then S has a largest and smallest element.

A somewhat more difficult result to prove is the well-ordering principle:

Theorem 6: Let S be a nonempty (finite or infinite) subset of N. Then S contains a smallest element.

Proof: The following argument makes a rather interesting use of the principle of mathematical induction. Let A = {y N | y < x for all x S}. Since SN, 0 < s for all s S, so that 0 A and A. Moreover AN. For if x S, then x + 1 > x and thus x + 1 A. Since 0 A and AN, the principle of mathematical induction implies that there exists y A such that y + 1A. (If, whenever y A, we have y + 1 A, then, since 0 A, we would have A = N by induction.) Let us prove that y is the smallest element of S. Since y A, y < x for all x S. Therefor it suffices to show that y S. Since y + 1 A, there exists x₀ S such that y + 1 > x₀. But then by Corollary 2, we see that y + 1 > x₀ + 1, so that y > x₀ by O3. However, since y < x for all x S, we see that y < x₀. Combining this latter inequality with the inequality y > x₀, we see that y = x₀ S.

The Division Algorithm

Let a be a nonnegative integer and let b be a positive integer. In elementary arithmetic, we learned how to "divide" a by b, thereby deriving a quotient q plus a remainder of the form r/b, where

This process of division can be expressed by the equation

It is possible to formulate the process of division, as described by (10) and (11), solely in terms of integers.

Theorem 7(Division Algorithm): Let a be a nonnegative integer and let b be a positive integer. Then there exist natural numbers q and t such that 0 < r < b and

Proof: Of all the multiples

of b, there are only finitely many less than or equal to a. Indeed, Corollary 3 asserts that there exists a positive number n such that a < nb. then the only multiples of b which are less than or equal to a are among 0 · b,1 · b,...,(n - 1) · b. Among the multiples of b which are less than or equal to a, let q·b be the largest. Then, by choice of q · b, we have q · b < a < (q + 1) · b. Let r = a - qb. Then r > 0 since q · b < a; and

since (q + 1) · b > a. Therefore we have shown that a = qb + r, where 0 < r < b.

The division algorithm, although it appears to be a rather superficial feature of the integers, is actually one of the most important results about Z. In other sections, we will see that the division algorithm can be applied in rather ingenious ways to yield arithmetic facts about the integers.