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