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

### APPENDIX B. REVIEW OF THE INTEGERS

One of the most important facts about the integers is that any integer *m* can 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 may be stated precisely as follows:

**Theorem 1: Division algorithm** *If m and η are integers and η 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 when *m* is divided by *n*.

Here we shall take the division algorithm as a postulate of the system of the integers. (In __Chapter 21__ we started with a more fundamental premise and proved the division algorithm from it.)

If *r* and *s* are integers, we say that *s* is a *multiple* of *r* if there is an integer *k* such that

*s* = *rk*

In this case, we also say that *r* is *a factor* of *s*, or *r divides s*, and we symbolize this relationship by writing

*r*|*s*

For example, 3 is a factor of 12, so we write: 3|12. Some of the elementary properties of divisibility are stated in the next theorem.

**Theorem 2:** *The following are true for all integers a*, *b*, *and c*:

(i)*If a*|*b and b*|*c*, *then a*|*c*.

(ii)1|*a*.

(iii)*a*|0.

(iv)*If c*|*a and c*|*b*, *then c*| (*ax* + *by*) *for all integers x and y*.

(v)*If a*|*b and c*|*d*, *then ac*|*bd*.

The proofs of these relationships follow from the definition of divisibility. For instance, we give here the proof of (iv): If *c*|*a* and *c*|*b*, this means that *a* = *kc* and *b* = *lc* for some *k* and *l*. Then

*ax* + *by* = *kcx* + *lcy* = *c*(*kx* + *ly*)

Visibly, *c* is a factor of *c*(*kx* + *ly*), and hence a factor of *ax* + *by*. In symbols, *c*|(*ax* + *by*), and we are done.

An integer *t* is called a *common divisor* of integers *r* and *s* if *t*|*r* and *t*|*s*. A *greatest common divisor* of *r* and *s* is an integer *t* such that

(i)*t*|*r* and *t*|*s*, and

(ii)For any integer *u*, if *u*|*r* and *u*|*s*, then *u*|*t*.

In other words, *t* is a greatest common divisor of *r* and *s* if ί is a common divisor of *r* and *s* and every other common divisor of *r* and *s* divides *t*.

It is an important fact that any two nonzero integers *r* and *s* always have a positive greatest common divisor:

**Theorem 3:** *Any two nonzero integers r and s have a unique positive greatest common divisor t*. *Moreover*, *t is equal to a* “*linear combination*” *of r and s*. *That is*,

*t* = *kr* + *ls*

*for some integers k and l*.

The unique positive greatest common divisor of *r* and *s* is denoted by the symbol gcd (*r*, *s*).

A pair of integers *r* and *s* are said to be *relatively prime* if they have no common divisors except ±1. For example, 4 and 15 are relatively prime. If *r* and *s* are relatively prime, their gcd is equal to 1. So by __Theorem 3__, there are integers *k* and *l* such that

*kr* + *ls* = 1

Actually, the converse of this statement is true too, and is stated in the next theorem:

**Theorem 4**: *Two integers r and s are relatively prime if and only if there are integers k and l such that kr* + *ls* = 1.

The proof of this theorem is left as an exercise. From __Theorem 4__, we deduce the following:

**Theorem 5** *If r and s are relatively prime*, *and r*|*st*, *then r*|*t*.

PROOF From __Theorem 4__ we know there are integers *k* and *l* such that *kr* + *ls* = 1. Multiplying through by *t*, we get

*krt* + *lst* = *t* (1)

But we are given the fact that *r*|*st*; that is, *st* is a multiple of *r*, say *st* = *mr*. Substitution into __Equation (1)__ gives *krt* + *lmr* = *t*, that is, *r*(*kt* + *lm*) = *t*. This shows that *r* is a factor of *t*, as required. ■

If an integer *m* has factors not equal to 1 or -1, we say that *m* is *composite*. If a positive integer *m* ≠ 1 is *not* composite, we call it a *prime*. For example, 6 is composite (it has factors ±2 and ±3), while 7 is prime.

If *p* is a prime, then for any integer *n*, *p* and *n* are relatively prime. Thus, __Theorem 5__ has the following corollary:

**Corollary** *Let m and n be integers, and let p be a prime: If p*|*mn*, *then either p*|*m or p*|*n*.

It is a major fact about integers that every positive integer *m* > 1 can be written, uniquely, as a product of primes. (The proof is given in __Chapter 22__.)

By a *least common multiple* of two integers *r* and *s* we mean a positive integer *m* such that

(i)*r*|*m* and *s*|*m*, and

(ii)If *r*|*x* and *s*|*x*, then *m*|*x*.

In other words, *m* is a common multiple of *r* and *s* and *m* is a factor of every other common multiple of *r* and *s*. In __Chapter 22__ it is shown that every pair of integers *r* and *s* has a unique least common multiple.

The least common multiple of *r* and *s* is denoted by lcm(*r*, *s*). The least common multiple has the following properties:

**Theorem 6** *For any integers a*, *b*, *and c*,

(i)*If gcd*(*a*, *b*) = 1, *then lcm*(*a*, *b*) = *ab*.

(ii)*Conversely*, *if lcm*(*a*, *b*) = *ab*, *then gcd*(*a*, *b*) = 1.

(iii)*If gcd*(*a*, *b*) = *c*, then lcm(*a*, *b*) = *ab*|*c*.

(iv)*lcm*{*a*, *ab*) = *ab*.

The proofs are left as exercises.

**EXERCISES**

*Prove that the following are true for any integers a*, *b*, *and c*:

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

**2** If *a*|*b*, then *a*|(− *b*) and (− *a*)|*b*.

**3** 1|*a* and (−1)|*a*.

**4** *a*|0.

**5** If *a*|*b*, then *ac*|*bc*.

**6** If *a* > 0, then gcd(*a*, 0) = *a*.

**7** If gcd(*ab*, *c*) = 1, then gcd(*a*, *c*) = 1 and gcd(*b*, *c*) = 1.

**8** If there are integers *k* and *l* such that *ka* + *lb* = 1, then *a* and are relatively prime.

**9** If *a*|*d* and *c*|*d* and gcd(*a*, *c*) = 1, then *ac*|*d*.

**10** If *d*|*ab* and *d*|*cb* and gcd(*a*, *c*) = 1, then *d*|*b*.

**11** If gcd(*a*, *b*) = 1, then lcm(*a*, *b*) = *ab*.

**12** If lcm(*a*, *b*) = *c*, then gcd(*a*, *b*) = 1.

**13** If gcd(*a*, *b*) = *c*, then lcm(*a*, *b*) = *ab*/*c*.

**14** lcm(*a*, *ab*) = *ab*.

**15** *a* · lcm(*b*, *c*) = lcm(*ab*, *ac*).