The Ring of Integers

1. The fundamental theorem of arithmetic and unique factorization domains

In this post, we study the system of integers and introduce various ring-theoretic generalizations thereof. We have seen from the previous blog post that is, first and foremost, an integral domain:

Definition 1.1. A ring is a set equipped with two binary operations and such that the following properties hold:

(RA1) addition is commutative, viz., for all ;
(RA2) addition is associative, viz., for all ;
(RA3) multiplication is associative, viz., for all ;
(RA4)addition and multiplication are distributive, viz., and for all ;
(RA5) an additive identity exists, so that for all ;
(RA6) a multiplicative identity exists, so that for all ;
(RA7)addition is invertible, viz., each admits such that .

A ring is said to be commutative if

(RA8) multiplication is commutative, viz., for all .

An integral domain is a commutative ring such that

(RA9) has no zero divisors, viz., if and , then either or .

In fact, the adjective integral suggests that integral domains are, in a sense, an abstraction of . As in the case of fields, we often drop the subscripts and write 0 and 1 for and , respectively. Moreover, given and , we write to denote the -fold sum . Obviously, for all and .

Many basic remarks we have made for fields hold for rings as well:

Exercise 1.2. Let be a ring and verify the following:

(1) is the unique additive identity, and that is the unique multiplicative identity. Hint: use (RA2) and(RA3).

(2) Additive inverses are unique. Hint: use (RA2) and(RA3).

(3) Multiplicative inverses are unique, in the following sense. Fix . If and , then . Moreover, if and are two-sided multiplicative inverses of , then . Hint: use (RA3).

(4) for all . Hint: use (RA4).

(5) if and only if . Hint: use (4).

(6) for all . Hint: use (2), (4), and (RA4).

(7) Define for each negative integer and every . Show that for all and .

(8) for all and . Hint: use (6), (7), and (RA4).

Aside from having no zero divisors, satisfies various other number-theoretic properties as well. Of particular importance is that there are special “irreducible” numbers from which we can build all other integers. Let us recall the basic definitions.

Definition 1.3. We say that is divisible by if there exists such that . In this case, we write .

Note that every integer is divisible by , , , and . Prime numbers are precisely those that do not have any other divisors.

Definition 1.5. A prime number in is a number that is divisible only by , , , and .

In other words, is a prime if and only if it is not a product of two numbers in . We also single out the integers that can be built out of prime numbers.

Definition 1.6. A composite number in is a product of two or more prime numbers. A prime factorization of a prime or composite number is of the form

where is either or , are positive prime numbers.

That all integers can be built out of prime numbers can be stated as follows:

Theorem 1.7 (Euclid, the fundamental theorem of arithmetic). Every integer other than is either prime or composite. Moreover, the prime factorization of each integer is unique up to a reordering of the prime factors. In other words, if and are prime factorizations of the same integer, then and there exists a bijection such that for all .

We are interested in coming up with characterizations of rings with an analogous unique factorizationproperty. Of course, any reasonable definition would include (1) an abstraction of the notion of irreducible or prime elements and (2) what it means to factor the other elements into products of such elements in a unique fashion.

To this end, we first generalize the basic notions introduced above. Definition 1.3 admits a straightforward generalization.

Definition 1.8. Let be an integral domain. If such that , we say that divides in case there exists such that .

Note that if is a unit in , then for all , whence divides every element of . Therefore, in defining irreducible elements, units must be excluded. Moreover, is divisible by everything, and so we exclude as well.

Definition 1.9. Let be an integral domain. is said to be irreducible if it is not a product of two units. In particular, irreducible elements are never units themselves.

We now note that, in Theorem 1.7, we have forced the prime factorization to use only the positive prime numbers in order to ensure uniqueness up to a reordering. Had we dropped the positive-prime requirement, we would only be able to guarantee that for each . This condition is equivalent to the stipulation that and divide each other, as both are prime numbers. We abstract this condition:

Definition 1.10. Two elements and of an integral domain is said to be associates of each other in case and .

We are now ready to state what it means for an integral domain to satisfy the unique factorization property.

Definition 1.11. An integral domain is a unique factorization domain (UFD) if the following properties hold:

(1) if is a non-zero element of , then we can find a unit and irreducible elements in such that
(2) if are units and are irreducible elements in such that , then there exists a bijection such that is an associate of for each .

The following observation shows that condition (2) can be tightened to resemble the statement of the fundamental theorem of arithmetic more closely.

Proposition 1.12. Two elements and of an integral domain are associates of each other if and only if for some unit in . This, in particular, implies that condition (2) in Definition 1.11 is equivalent to the following:

(2′) if are units and are irreducible elements in such that , then there exists a bijection such that for each .

Proof. Write and , so that . Since is an integral domain, we can cancel out and conclude that . As for the equivalence of (2) and (2′), we need only to note that the commutativity of can be used to consolidate all the extra units we get from the associate condition and send them to the leftmost term.

2. Greatest common divisors and principal ideal domains

While the definition of a UFD (Definition 1.11) is a nice abstraction of the fundamental theorem of arithmetic, it is not very clear whether any ring other than satisfies this property. In fact, we have not even proved that is a UFD! What we shall see in the course is that it is often easier to establish stronger ring-theoretic properties that imply the UFD property but are nevertheless easier to check.

To motivate such properties, we isolate the properties of the integers that play a crucial role in proving the fundamental theorem of arithmetic. Let us begin by recalling the following classical definition:

Definition 2.1. A greatest common divisor of is an integer such that\ (1) and ; (2) and imply that .

We write to denote an arbitrary greatest common divisor of and .

The adjective greatest refers to the fact that sits on top of all the other divisors of and with respect to the “divides” relation. That greatest common divisors always exist in is familiar to us:

Theorem 2.2 (Existence of greatest common divisors). Given , there exists a unique positive greatest common divisor of and , which we denote by .

Proof. always divides both and , and so the set of common divisors of and is nonempty. Since every element of is bounded above by , the greatest common divisor exists. Uniqueness follows from the uniqueness of maximum elements of subsets of .

Let us now examine the notions of multiples and divisors from a ring-theoretic viewpoint. Recall that an ideal of a commutative ring is a subset of such that and imply , and that implies . A principal ideal is an ideal of the form for a fixed ; in other words, is the collection of all “multiples” of .

Now, if divides , then every multiple of is a multiple of , and so . Indeed, if is a common divisor of and , then contains the ideal generated by and

as and are multiples of . What happens when equals ?

Proposition 2.3. Let be an integral domain and let . If , then is a greatest common divisor of and .

Proof. . Suppose that . This, in particular, implies that , whence and . Moreover, , and so we can find such that . Therefore, if is such that and , then , whence . It follows that is a greatest common divisor of and .

In other words, the principal ideal generated by equals the ideal generated by and . If greatest common divisors always exist, then we can continue this process to reduce any finitely generated ideal to principal ideals. Taking a cue from this, we make the following definition:

Definition 2.4. An integral domain is a principal ideal domain (PID) if every ideal of is a principal ideal. In other words, given an ideal of , we can find such that .

We now show that greatest common divisors always exist in PIDs.

Proposition 2.5 (Generalized Bézout’s identity). Let be a PID. Given , there exists a greatest common divisor of and . Moreover,there exist and such that .

Proof. is an ideal in , and so we can find such that . By Proposition 2.3, is a greatest common divisor of and . Moreover, , and so we can find such that .

3. The division algorithm and Euclidean domains

We now recall that computation of the greatest common divisor of two integers relies on the “division with a remainder” process in :

Theorem 3.1 (Division algorithm). Given with , there exist such that with . For notational convenience, we shall write and to denote and , respectively.

Proof. Let

Since is a subset of , there exists the smallest element . Observe that , for otherwise , contradicting minimality. It now suffices to set and .

Corollary 3.2 (Euclidean algorithm). The following algorithm always outputs the greatest common divisor of with :

   Input n and m  
   IF divR(n,m) = 0  
       THEN output m  
   ELSE  
       Set r = divR(n,m)  
       Set r_0 = divR(n,m)  
       Set r_{-1} = m  
       Set k = 0  
       WHILE r > 0  
           Set k := k+1  
           Set r_k = divR(r_{k-2},r_{k-1})  
           Set r := r_k  
       Output r_{k-1}

Proof. We first show that, given with ,

We let , , , and for notational convenience. Since and , we see that . Now,, and so . It follows that .

Conversely, and , and so . Since , we see that . Therefore, , whence we conclude that .

Therefore, at step of the algorithm, we have the identity

In particular, . Since the ’s decrease at each step, the algorithm terminates in finitely many steps. When it terminates, we get , and so

as was claimed.

This suggests that greatest common divisors should always exist in rings with an analogue of the division algorithm.

Definition 3.3. An integral domain is said to be a Euclidean domain in case there exists a function such that
(1) ;
(2) if , then ;
(3) if , then there exist such that and that either or .

Theorem 3.1 shows that is a Euclidean domain with the size function . In fact, it is often significantly easier to check that a ring is a Euclidean domain than to check that it is a PID or a unique factorization domain. In the next section, we outline a proof that all Euclidean domains are unique factorization domains.

For now, let us show that Euclidean domains are PIDs, so that they always admit greatest common divisors.

Theorem 3.4. Every Euclidean domain is a PID.

Proof. Let be a Euclidean domain and fix and ideal of . Let be the element of such that the size is minimal; this is possible because is -valued. We pick an arbitrary and invoke the division algorithm to write . If , then . But then , contradicting the minimality of in . We conclude that . Since was arbitrary, we conclude that every element of is a multiple of .

4. Proof of the fundamental theorem of arithmetic; Euclidean domains are PIDs and UFDs

Generalized Bézout’s identity (Proposition 2.5) in the context of integers implies that is an integer linear combination of and . This implies the following important fact.

Theorem 4.1. If , is a prime number in , and , then either or . Conversely, if is such that and always imply either or , then is a prime number.

Proof. Assume that , is a prime number in such that . , and . We also suppose that . Since the only divisors of are , we see that . Generalized Bézout’s identity (Proposition 2.5) implies that we can find such that . Multiplying through by , we obtain the identity

Now, and , and so .

Conversely, we assume that is such that and always imply either or . If is not a prime, then we can write for some integers . In this case, however, but and , which contradicts the hypothesis.

With Theorem 4.1 at hand, we can prove the fundamental theorem of arithmetic.

Proof of Theorem 1.7. We first show that every element of is can be written as a product of and positive prime numbers. To show this, it suffices to show that all positive integers can be written as products of prime numbers. We proceed by mathematical induction. is a positive prime number. Assume that the claim holds for all . If is a prime number, then there is nothing to do. If is not a prime, then , where . By induction, both and are products of positive prime numbers. This completes the proof of the claim.

It thus suffices to establish uniqueness. Specifically, we let and be two prime factorizations of . Let us assume without loss of generality that . Theorem 4.1 implies that must divide at least one , which we relabel to be . Since and are both positive prime numbers, we see that . Cancel out and from each side, and repeat the process. If , then we end up with the identity

This is absurd: , and so does not admit a multiplicative inverse in . It follows that .

The above proof suggests that characterizing irreducible elements in terms of the property introduced in Theorem 4.1 is crucial in proving that an integral domain is a UFD. We give this condition a name.

Definition 4.2. An element in an integral domain is said to be a prime element in case , is not a unit, and, for all , implies or .

The relationship between irreducible and prime elements is as follows:

Proposition 4.3. Let be an integral domain. Every prime element of is irreducible in . If, in addition, is PID, then every irreducible element in is prime.

Proof. Let be a prime element of an integral domain . We suppose for a contradiction that for some non-units . This, in particular, implies that . If we assume that , then for some . Substituting , we see that . is an integral domain, and so we can cancel out to conclude that . It follows that is a unit in , which contradicts the assumption that is a non-unit. We conclude that is irreducible.

We now assume that is a PID and fix an irreducible element of . Assume that and that . We let . is irreducible, and so either for some unit in or itself is a unit. Since , we conclude that is a unit. By generalized Bézout’s identity (Proposition 2.5), we can find such that . In other words, . Multiplying through by , we obtain the identity

Now, and , and so . It follows that is a prime element of .

Exercise 4.4. Prove that every Euclidean domain is a UFD, mimicking the proof of Theorem 1.7. Prove first that every element in a Euclidean domain is either a unit in or can be written as a finite product of irreducible elements of . This can be done by induction on the size of an element. The associate argument from the second paragraph of the proof of Theorem 1.7 can now be adopted without much change, keeping in mind that irreducible elements are prime elements, and vice versa.