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).