A Book of Abstract Algebra, Second Edition (1982)

Chapter 22. FACTORING INTO PRIMES

It has been said that the two events most decisive in shaping the course of our development were the invention of the wheel and the discovery of numbers. From the time—ages ago—when humans first learned the use of numbers for counting, they have been a source of endless fascination. Alchemists and astrologers extolled the virtues of “mystic” numbers and found in them the key to potent magic. Others, more down to earth, found delight in observing the many regularities and unexpected properties of numbers. The integers have been a seemingly inexhaustible source of problems great and small on which mathematics has fed and continues to draw in our day.

The properties of prime numbers alone have occupied the energies of mathematicians from the time of Euclid. New questions relating to the primes continue to appear, and many continue to resist the best efforts to solve them. Most importantly, a large part of number theory starts out from a few basic facts about prime numbers. They will be outlined in this chapter.

Modern number theory is the oldest as well as one of the newest parts of mathematics. It rests upon some basic data regarding the structure of the domain of the integers. An understanding of this structure is a fundamental part of any mathematical education.

An important feature of any ring is the structure of its ideals. We therefore begin by asking: What are the ideals of ? We have already made use of principal ideals of , such as the ideal

⟨6⟩ = {…, −18, −12, −6, 0, 6, 12, 18, …}

which consist of all the multiples of one fixed integer. It is natural to inquire whether has any ideals which are not principal, and what they might look like. The answer is far from self-evident.

Theorem 1 Every ideal of is principal.

PROOF: Let J be any ideal of . If 0 is the only integer in J, then J = ⟨0⟩, the principal ideal generated by 0. If there are nonzero integers in J, then for each x in J, −x is also in J; thus there are positive integers in J. By the well-ordering property we may pick the least positive integer in J, and call it n.

We will prove that J = ⟨n⟩, which is to say that every element of J is some multiple of n. Well, let m be any element of J. By the division algorithm we may write m = nq + r where 0 ≤ r < n. Now m was chosen in J, and n ∈ J, hence nq is in J. Thus,

r = m − nq ∈ J

Remember that r is either 0 or else positive and less than n. The second case is impossible, because n is the least positive integer in J. Thus, r = 0, and therefore m = nq, which is a multiple of n.

We have proved that every element of J is a multiple of n, which is to say that J = ⟨n⟩. ■

It is useful to note that by the preceding proof, any ideal J is generated by the least positive integer in J.

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

If this is the case, we also say that r is a factor of s, or r divides s, and we symbolize this by writing

r|s

Note that 1 and −1 divide every integer. On the other hand, an integer r divides 1 iff r is invertible. In there are very few invertible elements. As a matter of fact,

Theorem 2 The only invertible elements of are 1 and −1.

PROOF: If s is invertible, this means there is an integer r such that

rs = 1

Clearly r ≠ 0 and s ≠ 0 (otherwise their product would be 0). Furthermore, r and s are either both positive or both negative (otherwise their product would be negative).

If r and s are both positive, then r = 1 or r >1. In case r > 1 we may multiply both sides of 1 < r by s to get s < rs = 1 ; this is impossible because s cannot be positive and < 1. Thus, it must be that r = 1; hence 1 = rs = 1s = s, so also s = 1.

If r and s are both negative, then −r and −s are positive. Thus,

1 = rs = (−r)(−s)

and by the preceding case, −r = −s = 1. Thus, r = s = −1. ■

A pair of integers r and s are called associates if they divide each other, that is, if r|s and s|r. If r and s are associates, this means there are integers k and l such that r = ks and s = lr. Thus, r = ks = klr, hence kl = 1. By Theorem 2, k and l are ±1, and therefore r = ±s. Thus, we have shown that

If r and s are associates in , then r = ±s.(1)

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 andthen u|t.

In other words, t is a greatest common divisor of r and s if t is a common divisor of r and s, and every other common divisor of r and s divides t. Note that the adjective “greatest” in this definition does not mean primarily that t is greater in magnitude than any other common divisor, but, rather, that it is a multiple of any other common divisor.

The words “greatest common divisor” are familiarly abbreviated by gcd. As an example, 2 is a gcd of 8 and 10; but −2 also is a gcd of 8 and 10. According to the definition, two different gcd’s must divide each other; hence by Property (1) above, they differ only in sign. Of the two possible gcd’s ±t for r and s, we select the positive one, call it the gcd of r and s, and denote it by

gcd(r, s)

Does every pair r, s of integers have a gcd? Our experience with the integers tells us that the answer is “yes.” We can easily prove this, and more:

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

t = kr + ls

for some integers k and l.

PROOF: Let J be the set of all the linear combinations of r and s, that is, the set of all ur + υs as u and υ range over . J is closed with respect to addition and negatives and absorbs products because

and

w(ur + υs) = (wu)r + (wυ)s

Thus, J is an ideal of . By Theorem 1, J is a principal ideal of , say J = ⟨t⟩. (J consists of all the multiples of t.)

Now t is in J, which means that t is a linear combination of r and s:

t = kr+ ls

Furthermore, r = 1r + 0s and s = 0r + 1s, sor and s are linear combinations of r and s; thus r and s are in J. But all the elements of J are multiples of t, so r and s are multiples of t. That is,

t|r and t|s

Now, if u is any common divisor of r and s, this means that r = xu and s = yu for some integers x and y. Thus,

t= kr + ls = kxu + lyu = u(kx + ly)

It follows that u|t. This confirms that t is the gcd of r and s. ■

A word of warning: the fact that an integer m is a linear combination of r and s does not necessarily imply that m is the gcd of r and s. For example, 3 = (1)15 + (−2)6, and 3 is the gcd of 15 and 6. On the other hand, 27 = (1)15 + (2)6, yet 27 is not a gcd of 15 and 6.

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: if some linear combination of r and s is equal to 1 (that is, if there are integers k and l such that kr + ls = 1), then r and s are relatively prime. The simple proof of this fact is left as an exercise.

If m is any integer, it is obvious that ±1 and ±m are factors of m. We call these the trivial factors of m. If m has any other factors, we call them proper factors of m. For example, ±1 and ±6 are the trivial factors of 6, whereas ±2 and ±3 are proper factors of 6.

If an integer m has proper factors, m is called composite. If an integer p ≠ 0, 1 has no proper factors (that is, if all its factors are trivial), then we call p a prime. For example, 6 is composite, whereas 7 is a prime.

Composite number lemma If a positive integer m is composite, then m = rs where

1 < r < mand1 < s < m

PROOF: If m is composite, this means that m = rs for integers r and s which are not equal either to 1 or to m. We may take r and s to be positive; hence 1 < r and 1 < s. Multiplying both sides of 1 < r by s gives s < rs = m. Analogously, we get r < m. ■

What happens when a composite number is divided by a prime? The next lemma provides an answer to that question.

Euclid’s lemma Let m and n be integers, and let p be a prime.

If p|(mn), then either p|m or p|n.

PROOF: If p|m we are done. So let us assume that p does not divide m. What integers are common divisors of p and m?

Well, the only divisors of p are ±1 and ±p. Since we assume that p does not divide m, p and −p are ruled out as common divisors of p and m, hence their only common divisors are 1 and −1.

It follows that gcd(p, m) = 1, so by Theorem 3,

kp + lm = 1

for some integer coefficients k and l. Thus,

kpn + lmn = n

But p|(mn), so there is an integer h such that mn = ph. Therefore,

kpn + lph = n

that is, p(kn + lh) = n. Thus, p|n. ▪

Corollary 1 Let m₁, …, m_t, be integers, and let p be a prime. If p|(m₁ ⋯ m_t), then p|m_i for one of the factors m_i among m₁, …, m_t.

We may write the product m₁ ⋯ m_t as m₁(m₂ ⋯ m_t), so by Euclid’s lemma, p|m₁ or p|m₂ ⋯ m_t. In the first case we are done, and in the second case we may apply Euclid’s lemma once again, and repeat this up to t times.

Corollary 2 Let q₁, …, q_t and p be positive primes. If p|(q₁ ⋯ q_t), then p is equal to one of the factors q₁, …, q_t.

PROOF: By Corollary 1, p divides one of the factors q₁, …, q_t, say p|q_i But q_i is a prime, so its only divisors are ±1 and ±q_i; p is positive and not equal to 1, so if p|q_i, necessarily p = q_i. ■

Theorem 4: Factorization into primes Every integer n > 1 can be expressed as a product of positive primes. That is, there are one or more primes p₁, …, p_r such that

n = p₁p₂ ⋯ p_r

PROOF: Let K represent the set of all the positive integers greater than 1 which cannot be written as a product of one or more primes. We will assume there are such integers, and derive a contradiction.

By the well-ordering principle, K contains a least integer m; m cannot be a prime, because if it were a prime it would not be in K. Thus, m is composite; so by the composite number lemma,

m = rs

for positive integers r and s less than m and greater than 1; r and s are not in K because m is the least integer in K. This means that r and s can be expressed as products of primes, hence so can m = rs. This contradiction proves that Kis empty; hence every n > 1 can be expressed as a product of primes. ■

Theorem 5: Unique factorization Suppose n can be factored into positive primes in two ways, namely,

n = p₁ ⋯ p_r = q₁ ⋯ q_t

Then r = t, and the p_i are the same numbers as the q_j except, possibly, for the order in which they appear.

PROOF: In the equation p₁ ⋯ p_r = q₁ ⋯ q_t, let us cancel common factors from each side, one by one, until we can do no more canceling. If all the factors are canceled on both sides, this proves the theorem. Otherwise, we are left with some factors on each side, say

p_i ⋯ p_k = q_j ⋯ q_m

Now, p_i is a factor of p_i ⋯ p_k, so p_i|q_j ⋯ q_m. Thus, by Corollary 2 to Euclid’s lemma, p₁ is equal to one of the factors q_j, …, q_m, which is impossible because we assumed we can do no more canceling. ■

It follows from Theorems 4 and 5 that every integer m can be factored into primes, and that the prime factors of m are unique (except for the order in which we happen to list them).

EXERCISES

A. Properties of the Relation “a Divides a”

Prove the following, for any integers a, b, and c:

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

2 a|b iff a|(−b) iff (−a)|b.

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

4 a|0.

5 If c|a and c|b, then c| (ax + by) for all x, y ∈ .

6 If a > 0 and b > 0 and a|b, then a ≤ b.

7 a|b iff ac|bc, when c ≠ 0.

8 If a|b and c|d, then ac|bd.

9 Let p be a prime. If p|aⁿ for some n > 0, then p|a.

B. Properties of the gcd

Prove the following, for any integers a, b, and c. For each of these problems, you will need only the definition of the gcd.

# 1 If a > 0 and a|b, then gcd(a, b) = a.

2 gcd(a, 0) = a, if a > 0.

3 gcd(a, b) = gcd(a, b + xa) for any x ∈ .

4 Let p be a prime. Then gcd(a, p) = 1 or p. (Explain.)

5 Suppose every common divisor of a and b is a common divisor of c and d, and vice versa. Then gcd(a, b) = gcd(c, d).

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

7 Let gcd(a, b) = c. Write a = ca′ and b = cb′. Then gcd(a′, b′) = 1.

C. Properties of Relatively Prime Integers

Prove the following, for all integers a, b, c, d, r, and s. (Theorem 3 will be helpful.)

1 If there are integers r and s such that ra + sb = 1, then a and b are relatively prime.

2 If gcd(a, c) = 1 and c|ab, then c|b. (Reason as in the proof of Euclid’s lemma.)

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

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

5 If d = gcd(a, b) where a = dr and b = ds, then gcd(r, s) = 1.

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

D. Further Properties of gcd’s and Relatively Prime Integers

Prove the following, for all integers a, b, c, d, r, and s:

1 Suppose a|b and c|b and gcd(a, c) = d. Then ac|bd.

2 If ac|b and ad|b and gcd(c, d) = 1, then acd|b.

# 3 Let d = gcd(a, b). For any integer x, d|x iff x is a linear combination of a and b.

4 Suppose that for all integers x, x|a and x|b iff x|c. Then c = gcd(a, b).

5 For all n > 0, if gcd(a, b) = 1, then gcd(a, bⁿ) = 1. (Prove by induction.)

6 Suppose gcd(a, b) = 1 and c|ab. Then there exist integers r and s such that c = rs, r|a, s|b, and gcd(r, s) = 1.

E. A Property of the gcd

Let a and b be integers.

Prove parts 1 and 2:

# 1 Suppose a is odd and b is even, or vice versa. Then gcd(a, b) = gcd(a + b, a − b).

2 Suppose a and b are both odd. Then 2gcd(a, b) = gcd(a + b, a − b).

3 If a and b are both even, explain why either of the two previous conclusions are possible.

F. Least Common Multiples

A least common multiple of two integers a and b is a positive integer c such that (i) a|c and b|c; (ii) if a|x and b|x, then c|x.

1 Prove: The set of all the common multiples of a and b is an ideal of

2 Prove: Every pair of integers a and b has a least common multiple. (HINT: Use part 1.)

The positive least common multiple of a and b is denoted by lcm(a, b). Prove the following for all positive integers a, b, and c:

# 3 a · lcm(b, c) = lcm(ab, ac).

4 If a = a₁c and b = b₁c where c = gcd(a, b), then lcm(a, b) = a₁b₁c.

5 lcm(a, ab) = ab.

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

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

8 Let gcd(a, b) = c. Then lcm(a, b) = ab/c.

9 Let gcd(a, b) = c and lcm(a, b) = d. Then cd = ab.

G. Ideals in

Prove the following:

1 ⟨n⟩ is a prime ideal iff n is a prime number.

2 Every prime ideal of is a maximal ideal. [HINT: If ⟨p⟩ ⊆ ⟨a⟩, but ⟨p⟩ ≠ ⟨a⟩, explain why gcd(p, a) = 1 and conclude that 1 ∈ ⟨a⟩.] Assume the ideal is not {0}.

3 For every prime number p, _p is a field. (HINT: Remember _p = /⟨p⟩. Use Exercise 4, Chapter 19.)

4 If c = lcm(a, b), then ⟨a⟩ ∩ ⟨b⟩ = ⟨c⟩.

5 Every homomorphic image of is isomorphic to _n for some n.

6 Let G be a group and let a, b ∈ G. Then S = {n ∈ : abⁿ = bⁿa} is an ideal of .

7 Let G be a group, H a subgroup of G, and a ∈ G. Then

S = {n ∈ :aⁿ ∈ H}

is an ideal of .

8 If gcd(a, b) = d, then ⟨a⟩ + ⟨b⟩ = ⟨d⟩. (NOTE: If J and K are ideals of a ring A, then J + K = {x + y: x ∈ J and y ∈ K}.)

H. The gcd and the 1cm as Operations on

For any two integers a and b, let a * b = gcd(a, b) and a ∘ b? = lcm(a, b). Prove the following properties of these operations:

1 * and ∘ are associative.

2 There is an identity element for º, but not for * (on the set of positive integers).

3 Which integers have inverses with respect to º?

4 Prove: a * (b ∘ c) = (a * b) ∘ (a * c).