## A Book of Abstract Algebra, Second Edition (1982)

### Chapter 21. THE INTEGERS

There are two possible ways of describing the system of the integers.

On the one hand, we may attempt to describe it concretely.

On the other hand, we may find a list of axioms from which it is possible to deduce all the properties of the integers, so the *only* system which has all these properties is the system of the integers.

The second of these two ways is the way of mathematics. It is elegant, economical, and simple. We select as axioms only those particular properties of the integers which are absolutely necessary in order to prove further properties of the integers. And we select a sufficiently *complete* list of axioms so that, using them, one can prove all the properties of the integers needed in mathematics.

We have already seen that the integers are an integral domain. However, there are numerous examples of integral domains which bear little resemblance to the set of the integers. For example, there are finite integral domains such as _{5}, fields (remember that every field is an integral domain) such as and , and others. Thus, in order to pin down the integers — that is, in order to find a list of axioms which applies to the integers and *only* the integers—we must select some additional axioms and add them to the axioms of integral domains. This we will now proceed to do.

Most of the traditional number systems have two aspects. One aspect is their algebraic structure: they are integral domains or fields. The other aspect—which we have not yet touched upon—is that their elements can be *ordered*. That is, if *a* and *b* are distinct elements, we can say that *a* is less than *b* or *b* is less than *a*. This second aspect—the ordering of elements—will now be formalized.

*An ordered integral domain is an integral domain A with a relation, symbolized by <, having the following properties:*

1. *For any a and b in A, exactly one of the following is true:*

*a* = *b* *a* < *b* or *b* < *a*

*Furthermore, for any a, b, and c in A*,

2. *If* *a* < *b* and *b* < *c*, then *a* < *c*.

3. *If* *a* < *b*, then *a* + *c* < *b* + *c*.

4. *If* *a* < *b*, then *ac* < *bc on the condition that* 0 < *c*.

The relation < is called an *order relation* on *A*. The four conditions which an order relation must fulfill are familiar to everyone. Properties 1 and 2 require no comment. Property 3 asserts that we are allowed to add any given *c* to both sides of an inequality. Property 4 asserts that we may multiply both sides of an inequality by any *c*, on the condition that *c* is greater than zero.

As usual, *a* > *b* has the same meaning as *b* < *a*. Furthermore, *a* ≤ *b* means “*a* < *b* or *a* = *b*,” and *b* ≥ *a* means the same as *a* ≤ *b*.

In an ordered integral domain *A*, an element *a* is called *positive* if *a* >0. If *a* <0 we call *a negative*. Note that if *a* is positive then −*a* is negative. (Proof: Add −*a* to both sides of the inequality *a* > 0.) Similarly, if *a* is negative, then −*a* is positive.

In any ordered integral domain, *the square of every nonzero element is positive*. Indeed, if *c* is nonzero, then either *c* > 0 of *c* <0. If *c* >0, then, multiplying both sides of the inequality *c* >0 by *c*,

*cc* > *c*0 = 0

so *c*^{2}>0. On the other hand, if *c*<0, then

(−*c*) > 0

hence

(−*c*)(−*c*) > 0(−*c*) = 0

But (−*c*)(−*c*) = *c*^{2}, so once again, *c*^{2} > 0.

In particular, since *1* = *l*^{2}, *1 is always positive*.

From the fact that *1* >0, we immediately deduce that *1* + *1* > *1*, *1* + *1* + *1* > *1* + *1*, and so on. In general, for any positive integer n,

(n + 1)· *1* > n · *1*

where n · *1* designates the unity element of the ring *A* added to itself n times. Thus, in any ordered integral domain *A, the set of all the multiples of 1 is ordered as in* : namely

⋯ <(−2)·1 <(−1)·1 <0<1<2·1<3·1< ⋯

The set of all the positive elements of *A* is denoted by *A*^{+}. An ordered integral domain *A* is called an *integral system* if every nonempty subset of *A*^{+} has a least element. In other words, if *every nonempty set of positive elements of A has a least element*. This property is called the *well-ordering property* for *A*^{+}.

It is obvious that is an integral system, for every nonempty set of positive integers contains a least number. For example, the smallest element of the set of all the positive even integers is 2. Note that and are *not* integral systems. For although both are ordered integral domains, they contain sets of positive numbers, such as {*x*:0 <*x*

In any integral system, *there is no element between* 0 *and 1*. For suppose *A* is an integral system in which there are elements *χ* between 0 and *1*. Then the set {*x ∊ A*: 0<*x*< *1*} is a nonempty set of positive members of A, so by the well-ordering property it has a least element *c*. That is,

0 <*c* < 1

and *c* is the least element of *A* with this property. But then (multiplying by *c*),

**0** < *c*^{2} < *c*

Thus, *c*^{2} is between 0 and 1 and is less than *c*, which is impossible.

Thus, there is no element of *A* between 0 and *1*.

Finally, in any integral system, *every element is a multiple of 1*. If that were not the case, we could use the well-ordering principle to pick the least positive element of *A* which is *not* a multiple of *1 :* call it *b*. Now, b>0 and there are no elements of *A* between 0 and 1, so *b>l*. (Remember that *b* cannot be equal to *1* because *b* is not a multiple of *1*.) Since *b > 1*, it follows that *b − 1* >0. But *b − 1 < b* and *b* is the *least* positive element which is not a multiple of 1, so *b − 1 is* a multiple of *1*. Say

*b* − 1 = n · 1

But then *b* = *n · 1* + *1* = (n + *1*)*· 1*, which is impossible.

Thus, in any integral system, all the elements are multiples of 1 and these are ordered exactly as in . It is now a mere formality to prove that *every integral system is isomorphic to* This is left as __Exercise D__at the end of this chapter.

Since every integral system is isomorphic to , any two integral systems are isomorphic to each other. Thus is, up to isomorphism, the *only* integral system. We have therefore succeeded in giving a complete axiomatic characterization of

Henceforward we consider to be defined by the fact that it is an integral system.

The theorem which follows is the basis of proofs by mathematical induction. It is intuitively clear and easy to prove.

**Theorem 1** *Let K represent a set of positive integers. Consider the following two conditions’*.

(i) 1 *is in K*.

(ii) *For any positive integer* k, *if* k∈ *K, then also* k + 1 ∈ *K*.

*If K is any set of positive integers satisfying these two conditions, then K consists of all the positive integers*.

PROOF: Indeed, if *K* does not contain all the positive integers, then by the well-ordering principle, the set of all the positive integers which are *not* in *K* has a least element. Call it *b*; *b* is the least positive integer *not* in *K*. By Condition (i), *b* ≠ 1, hence *b* > 1.

Thus, *b* − 1 > 0, and *b* − 1 ∈ *K*. But then, by Condition (ii), *b ∈ K*, which is impossible. ■

Let the symbol *S*_{n} represent any statement about the positive integer n. For example, *S*_{n} might stand for “n is odd,” or “n is a prime,” or it might represent an equation such as (n − 1)(n + 1) = n^{2} − 1 or an inequality such as n ≤ n^{2}. If, let us say, *S*_{n} stands for n ≤ n^{2}, then *S*_{1} asserts that 1 ≤ 1^{2}, *S*_{2} asserts that 2 ≤ 2^{2}, *S*_{3} asserts that 3 ≤ 3^{2}, and so on.

**Theorem 2: Principle of mathematical induction** *Consider the following conditions :*

(i)*S*_{1} *is true*.

(ii)*For any positive integer k, if S _{k} is true, then also*

*S*

_{k+1}

*is true*.

*If Conditions* (i) *and* (ii) *are satisfied, then* *S*_{n} *is true for every positive integer* n.

PROOF: Indeed, if *K* is the set of all the positive integers k such that *S*_{k} is true, then *K* complies with the conditions of __Theorem 1__. Thus, K contains all the positive integers. This means that *S*_{n} is true for every n. ■

As a simple illustration of how the principle of mathematical induetion is applied, let *S*_{n} be the statement that

that is, the sum of the first n positive integers is equal to n(n + 1)/2. Then *S*_{1} is simply

which is clearly true. Suppose, next, that k is any positive integer and that *S*_{k} is true. In other words,

Then, by adding k + 1 to both sides of this equation, we obtain

that is,

However, this last equation is exactly *S*_{k+1}. We have therefore verified that whenever *S*_{k} is true, *S*_{k+1} also is true. Now, the principle of mathematical induction allows us to conclude that

for every positive integer n.

A variant of the principle of mathematical induction, called the *principle of strong induction*, asserts that *S*_{n} is true for every positive integer n on the conditions that

(i)*S*_{1} is true, and

(ii)For any positive integer k, if *S*_{i} is true for every i < k, then *S*_{k} is true.

The details are outlined in __Exercise H__ at the end of this chapter.

One of the most important facts about the integers is that any integer m may be divided by any positive integer n to yield a quotient q and a positive remainder r. (The remainder is less than the divisor n.) For example, 25 may be divided by 8 to give a quotient of 3 and a remainder of 1:

This process is known as the *division algorithm*. It is stated in a precise manner as follows:

**Theorem 3: Division algorithm** *If* m *and* n *are integers and* n *is positive, there exist unique integers* q *and* r *such that*

m = nq + r*and*0 ≤ r < n

*We call* q *the quotient, and* r *the remainder, in the division of* m *by* n.

PROOF: We begin by showing a simple fact:

*There exists an integer* x *such that* xn≤ m. (*)

Remember that n is positive; hence n ≥ 1. As for m, either m≥ 0 or m < 0. We consider these two cases separately:

Suppose m ≥ 0. Then

Suppose m < 0. We may multiply both sides of n ≥ 1 by the positive integer −m to get (−m)n≥ −m. Adding mn + m to both sides yields

Thus, regardless of whether m is positive or negative, there is some integer x such that xn ≤ m.

Let *W* be the subset of consisting of all the nonnegative integers which are expressible in the form m − xn, where x is any integer. By (*) *W* is not empty; hence by the well-ordering property, *W* contains a least integer r. Because r ∈ W, r is nonnegative and is expressible in the form m − nq for some integer q. That is,

r ≥0

and

r = m − nq

Thus, we already have m = nq + r and 0 ≤ r. It remains only to verify that r

r − n = (m − nq) − n = m − n(q +1)

and clearly r − n < r. This means that m − n(q + 1) is an element of *W* *less than* r, which is impossible because r is the least element of *W*. We conclude that n≤ r is impossible; hence r

The verification that q and r are unique is left as an exercise. ■

**EXERCISES**

**A. Properties of Order Relations in Integral Domains**

Let *A* be an ordered integral domain. Prove the following, for all *a*, *b*, and *c* in *A:*

**1** If *a* ≤ *b* and *b* ≤ *c*, then *a* ≤ *c*.

**2** If *a* ≤ *b*, then *a* +*c* ≤ *b* + *c*.

**3** If *a* ≤ *b* and*c* ≥ 0, then *ac* ≤ *bc*.

**4** If *a* < *b* and*c* < 0, then *bc* < *ac*.

**5** *a* < *b* iff − *b* <−*a*.

**6** If *a* +*c*<*b* + *c*, then *a* < *b*.

**7** If *ac* < *bc* and *c* > 0, then *a* < *b*.

**8** If *a* < *b* and*c*< *d*, then *a* +*c* < *b* + *d*.

**B. Further Properties of Ordered Integral Domains**

Let *A* be an ordered integral domain. Prove the following, for all *a*, *b*, and *c* in *A:*

**1** *a*^{2} + *b*^{2} ≥ 2*ab*

**2** *a*^{2} + *b*^{2} ≥ *ab and a*^{2} + *b*^{2} ≥ − *ab*

**3** *a*^{2} +*b*^{2} + *c*^{2} ≥ *ab* + *bc* + *ac*

**4** *a*^{2} + *b*^{2} >,if *a*^{2} + *b*^{2} ≠ 0

__5__*a* + *b* < *ab* + 1,if *a*,*b* > 1

**6** *ab* + *ac* + *bc* +1 *< a* + *b* + *c* + *abc, if a, b, c > 1*

**C. Uses of Induction**

Prove parts 1−7, using the principle of mathematical induction. (Assume *n* is a positive integer.)

**1** 1 + 3 + 5 + ⋯ + (2n − 1) = n^{2} (The sum of the first *n* odd integers is n^{2}.)

**2** 1^{3} + 2^{3} + ⋯ + n^{3} = (1 + 2 + ⋯ + n)^{2}

**3** 1^{2} + 2^{2} + ⋯ + (n − 1)^{2} < < 1^{2} + 2^{2} + ⋯ + n^{2}

**4** 1^{3} + 2^{3} + ⋯ + (n − 1)^{3} < < 1^{3} + 2^{3} + ⋯ + n^{3}

**5** 1^{2} + 2^{2} + ⋯ + n^{2} = n(n + 1)(2n + 1)

**6** 1^{3} + 2^{3} + ⋯ + n^{3} = n^{2}(n + 1)^{2}

**7**

# ** 8** The

*Fibonacci sequence*is the sequence of integers

*F*

_{1},

*F*

_{2},

*F*

_{3},…defined as follows:

*F*

^{1}= 1;

*F*

_{2}= 1;

*F*

_{n+2}=

*F*

_{n+1}+

*F*

_{n}for all positive integers n. (That is, every number, after the second one, is the sum of the two preceding ones.) Use induction to prove that for all

*n*> 0,

*F*_{n + 1} *F*_{n + 2} −*F*_{n}*F*_{n + 3} = (−l)^{n}

**D. Every Integral System Is Isomorphic to **

Let *A* be an integral system. Let *h*:→*A* be defined by: *h*(n) = n · 1. The purpose of this exercise is to prove that *h* is an isomorphism, from which it follows that *A* ≅

**1** Prove: For every positive integer n, n · 1 > 0. What is the characteristic *of A*

**2**Prove that *h* is injective and surjective.

**3** Prove that *h* is an isomorphism.

**E. Absolute Values**

In any ordered integral domain, define |a| by

Using this definition, prove the following:

**1** |−*a*| = |*a*|

**2** *a* ≤ |*a*|

**3** *a* ≤ −|*a*|

**4** If *b* >0, |*a*|≤ *b* iff −*b* ≤ *a* ≤ *b*

# ** 5** |

*a*+

*b*| ≤|

*a*| +|

*b*|

**6** |*a*−*b*|≤|*a*| +|*b*|

**7** |*ab*| = |*a*|·|*b*|

# ** 8** |

*a*|−|

*b*|≤ |

*a*−

*b*|

**9** ||*a*|−|*b*||≤ |*a* − *b*|

**F. Problems on the Division Algorithm**

Prove parts 1−3, where k, m, n, q, and r designate integers.

**1** Let n > 0 and k > 0. If q is the quotient and r is the remainder when m is divided by n, then q is the quotient and kr is the remainder when km is divided by kn.

# ** 2** Let n > 0 and k > 0. If q is the quotient when m is divided by n, and

*q*is the quotient when q is divided by k, then q

_{1}_{1}is the quotient when m is divided by nk.

**3** If n ≠ 0, there exist q and r such that m = nq + r and 0 ≤ r < |n|. (Use __Theorem 3__, and consider the case when n < 0.)

**4** In __Theorem 3__, suppose m = nq_{1} + r_{1} = nq_{2} + r_{2} where 0 ≤ r_{1}, r_{2} < n. Prove that r_{1} − r_{2} = 0. [HINT: Consider the difference (nq_{1} + r_{1} − (nq_{2} + r_{2}).]

**5** Use part 4 to prove that q_{1} − q_{2} = 0. Conclude that the quotient and remainder, in the division algorithm, are unique.

**6** If r is the remainder when m is divided by n, prove that m = r in _{n}.

**G. Laws of Multiples**

The purpose of this exercise is to give rigorous proofs (using induction) of the basic identities involved in the use of exponents or multiples. If *A* is a ring and *a* ∈ *A*, we define n · *a* (where n is any positive integer) by the pair of conditions:

(i) 1 · *a* = *a*, and (ii) (n + 1)· *a* = n · *a* + *a*

Use mathematical induction (with the above definition) to prove that the following are true for all positive integers n and all elements *a*, *b* ∈ *A:*

**1** n ·(*a* + *b*) = n · *a* + n · *b*

**2** (n + m)· *a* = n · *a* + m · *a*

**3** (n · *a*)*b* = *a*(n · *b*) = n · (*ab*)

**4** m · (n · *a*) = (mn) · *a*

# ** 5** n ·

*a*= (n ·

*1*)

*a*where

*1*is the unity element of

*A*

**6**(n · *a*)(m · *b*) = (nm) · *ab*(Use parts 3 and 4.)

**H. Principle of Strong Induction**

Prove the following in :

**1** Let *K* denote a set of positive integers. Consider the following conditions:

(i) I∈*K*.

(ii) For any positive integer k, if every positive integer less than k is in *K*, then *k ∈ K*.

If *K* satisfies these two conditions, prove that *K* contains all the positive integers.

**2** Let *S*_{n} represent any statement about the positive integer n. Consider the following conditions:

(i) *S*_{1} is true.

(ii) For any positive integer k, if *S*_{i} is true for every i < k, *S*_{k} is true.

If Conditions (i) and (ii) are satisfied, prove that *S*_{n} is true for every positive integer n.