## 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* = 1*s* = *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* = 1*r* + 0*s* and *s* = 0*r* + 1*s*, so*r* 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* < *mand*1 < *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*_{1}, …, *m _{t}*,

*be integers*,

*and let p be a prime*.

*If p*|(

*m*

_{1}⋯

*m*),

_{t}*then p*|

*m*

_{i}for one of the factors m_{i}among m_{1}, …,

*m*.

_{t}We may write the product *m*_{1} ⋯ *m _{t}* as

*m*

_{1}(

*m*

_{2}⋯

*m*), so by Euclid’s lemma,

_{t}*p*|

*m*

_{1}or

*p*|

*m*

_{2}⋯

*m*. 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}*t*times.

**Corollary 2** *Let q*_{1}, …, *q _{t}* and

*p*be positive primes. If

*p*|(

*q*

_{1}⋯

*q*),

_{t}*then p is equal to one of the factors q*

_{1}, …,

*q*.

_{t}PROOF: By Corollary 1, *p divides* one of the factors *q*_{1}, …, *q _{t}*, say

*p*|

*q*But

_{i}*q*is a prime, so its only divisors are ±1 and ±

_{i}*q*;

_{i}*p*is positive and not equal to 1, so if

*p*|

*q*, necessarily

_{i}*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*_{1}, …, *p _{r} such that*

*n* = *p*_{1}*p*_{2} ⋯ *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 *K*is 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*_{1} ⋯ *p _{r}* =

*q*

_{1}⋯

*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*_{1} ⋯ *p _{r}* =

*q*

_{1}⋯

*q*, 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

_{t}*p _{i}* ⋯

*p*=

_{k}*q*⋯

_{j}*q*

_{m}Now, *p _{i}* is a factor of

*p*⋯

_{i}*p*, so

_{k}*p*|

_{i}*q*⋯

_{j}*q*. Thus, by Corollary 2 to Euclid’s lemma,

_{m}*p*is

_{1}*equal*to one of the factors

*q*, …,

_{j}*q*, which is impossible because we assumed we can do no more canceling. ■

_{m}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 ^{n}* 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 ^{n}*) = 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*_{1}*c* and *b* = *b*_{1}*c* where *c* = gcd(*a*, *b*), then lcm(*a*, *b*) = *a*_{1}*b*_{1}*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 ^{n}* =

*b*} is an ideal of .

^{n}a**7** Let *G* be a group, *H* a subgroup of *G*, and *a* ∈ *G*. Then

*S* = {*n* ∈ :*a ^{n}* ∈

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