# 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.Aringis 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

commutativeif

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

integral domainis a commutative ring such that

(RA9)has nozero 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 isdivisibleby 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. Aprime numberin 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.Acomposite numberin is a product of two or more prime numbers. Aprime factorizationof a prime or composite number is of the formwhere 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 factorization*property. 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 thatdividesin 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 beirreducibleif 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 beassociatesof 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 aunique 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)inDefinition 1.11is 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.Agreatest common divisorof 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 aprincipal 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 aEuclidean domainin 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 aprime elementin 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 ofTheorem 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 ofTheorem 1.7can now be adopted without much change, keeping in mind that irreducible elements are prime elements, and vice versa.