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 ₅, 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 > c0 = 0

so c²>0. On the other hand, if c<0, then

(−c) > 0

hence

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

But (−c)(−c) = c², so once again, c² > 0.

In particular, since 1 = l², 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² < c

Thus, c² 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 Dat 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² − 1 or an inequality such as n ≤ n². If, let us say, S_n stands for n ≤ n², then S₁ asserts that 1 ≤ 1², S₂ asserts that 2 ≤ 2², S₃ asserts that 3 ≤ 3², and so on.

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

(i)S₁ 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₁ 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₁ 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 + rand0 ≤ 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 andc ≥ 0, then ac ≤ bc.

4 If a < b andc < 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 andc< 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² + b² ≥ 2ab

2 a² + b² ≥ ab and a² + b² ≥ − ab

3 a² +b² + c² ≥ ab + bc + ac

4 a² + b² >,if a² + b² ≠ 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² (The sum of the first n odd integers is n².)

2 1³ + 2³ + ⋯ + n³ = (1 + 2 + ⋯ + n)²

3 1² + 2² + ⋯ + (n − 1)² < < 1² + 2² + ⋯ + n²

4 1³ + 2³ + ⋯ + (n − 1)³ < < 1³ + 2³ + ⋯ + n³

5 1² + 2² + ⋯ + n² = n(n + 1)(2n + 1)

6 1³ + 2³ + ⋯ + n³ = n²(n + 1)²

7

# 8 The Fibonacci sequence is the sequence of integers F₁, F₂, F₃,…defined as follows: F¹ = 1; F₂ = 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_nF_{n + 3} = (−l)ⁿ

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

2Prove 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₁ 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₁ + r₁ = nq₂ + r₂ where 0 ≤ r₁, r₂ < n. Prove that r₁ − r₂ = 0. [HINT: Consider the difference (nq₁ + r₁ − (nq₂ + r₂).]

5 Use part 4 to prove that q₁ − q₂ = 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₁ 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.