# The ring of integers

## 1. The fundamental theorem of arithmetic and unique factorization domains

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

Definition 1.1. A ring is a set $R$ equipped with two binary operations $+:R \times R \to R$ and $\cdot:R \times R \to R$ such that the following properties hold:

(RA1) addition is commutative, viz., $a+b=b+a$ for all $a,b \in R$;
(RA2) addition is associative, viz., $a+(b+c) = (a+b)+c$ for all $a,b \in R$;
(RA3) multiplication is associative, viz., $a(bc) = (ab)c$ for all $a,b,c \in R$;
(RA4)addition and multiplication are distributive, viz., $a(b+c) = ab+ac$ and $(a+b)c = ac + bc$ for all $a,b,c \in R$;
(RA5) an additive identity $0_R$ exists, so that $a + 0_R = 0_R + a = a$ for all $a \in R$;
(RA6) a multiplicative identity $1_R$ exists, so that $a 1_R = 1_R a = a$ for all $a \in R$;
(RA7)addition is invertible, viz., each $a \in R$ admits $-a \in R$ such that $a + (-a) = (-a) + a = 0_R$.

A ring $R$ is said to be commutative if

(RA8) multiplication is commutative, viz., $ab = ba$ for all $a,b \in R$.

An integral domain is a commutative ring $R$ such that

(RA9) $R$ has no zero divisors, viz., if $a,b \in R$ and $ab = 0$, then either $a = 0_R$ or $b = 0_R$.

In fact, the adjective integral suggests that integral domains are, in a sense, an abstraction of $\mathbb{Z}$. As in the case of fields, we often drop the subscripts and write 0 and 1 for $0_R$ and $1_R$, respectively. Moreover, given $n \in \mathbb{N}$ and $x \in R$, we write $n \cdot x$ to denote the $n$-fold sum $x + \cdots + x$. Obviously, $(n \cdot x) + (m \cdot x) = (n+m) \cdot x$ for all $n,m \in \mathbb{Z}$ and $x \in R$.

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

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

(1) $0$ is the unique additive identity, and that $1$ 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 $a \in R \smallsetminus \{0\}$. If $ax = 1$ and $ya = 1$, then $x = y$. Moreover, if $b$ and $c$ are two-sided multiplicative inverses of $a$, then $b = c$. Hint: use (RA3).

(4) $0 \cdot a = a \cdot 0 = 0$ for all $a \in R$. Hint: use (RA4).

(5) $0 = 1$ if and only if $R = \{0\}$. Hint: use (4).

(6) $-(ab) = (-a)b = a(-b)$ for all $a,b \in R$. Hint: use (2), (4), and (RA4).

(7) Define $n \cdot x = (-n) \cdot (-x)$ for each negative integer $n$ and every $x \in R$. Show that $n \cdot x + m \cdot x = (n + m) \cdot x$ for all $n,m \in \mathbb{Z}$ and $x \in R$.

(8) $(n \cdot x)(m \cdot y) = (nm) \cdot xy$ for all $n,m \in \mathbb{Z}$ and $x \in R$. Hint: use (6), (7), and (RA4).

Aside from having no zero divisors, $\mathbb{Z}$ 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 $n \in \mathbb{Z}$ is divisible by $m \in \mathbb{Z}$ if there exists $k \in \mathbb{Z}$ such that $n = km$. In this case, we write $m \mid n$.

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

Definition 1.5. A prime number in $\mathbb{Z}$ is a number $p \in \mathbb{Z} \smallsetminus \{-1,0,1\}$ that is divisible only by $1$, $-1$, $p$, and $-p$.

In other words, $p$ is a prime if and only if it is not a product of two numbers in $\mathbb{Z} \smallsetminus \{-1,1,p,-1\}$. We also single out the integers that can be built out of prime numbers.

Definition 1.6. A composite number in $\mathbb{Z}$ is a product of two or more prime numbers. A prime factorization of a prime or composite number $n$ is of the form

where $u$ is either $1$ or $-1$, $p_1,\ldots,p_k$ 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 $-1,0,1$ 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 $u p_1 \cdots p_k$ and $t q_1 \cdots q_l$ are prime factorizations of the same integer, then $u = t$ and there exists a bijection $\varphi:\{1,\ldots,k\} \to \{1,\ldots,l\}$ such that $p_i = q_{\varphi(i)}$ for all $1 \leq i \leq k$.

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 $R$ be an integral domain. If $a,b \in R$ such that $a \neq 0$, we say that $a$ divides $b$ in case there exists $k \in R$ such that $b = ka$.

Note that if $u$ is a unit in $R$, then $b = (bu^{-1})u$ for all $b \in R$, whence $u$ divides every element of $R$. Therefore, in defining irreducible elements, units must be excluded. Moreover, $0$ is divisible by everything, and so we exclude $0$ as well.

Definition 1.9. Let $R$ be an integral domain. $a \in R \smallsetminus \{0\}$ 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 $p_i = \pm q_{\varphi(i)}$ for each $i$. This condition is equivalent to the stipulation that $p_i$ and $q_{\varphi(i)}$ divide each other, as both are prime numbers. We abstract this condition:

Definition 1.10. Two elements $a$ and $b$ of an integral domain $R$ is said to be associates of each other in case $a \mid b$ and $b \mid a$.

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 $R$ is a unique factorization domain (UFD) if the following properties hold:

(1) if $x$ is a non-zero element of $R$, then we can find a unit $u$ and irreducible elements $p_1,\ldots,p_n$ $(n \geq 0)$ in $R$ such that $x = u p_1 \cdots p_n$
(2) if $u,t$ are units and $p_1,\ldots,p_n,q_1,\ldots,q_m$ are irreducible elements in $R$ such that $up_1 \cdots p_n = tq_1 \cdots q_m$, then there exists a bijection $\varphi:\{1,\ldots,n\} \to \{1,\ldots,m\}$ such that $p_i$ is an associate of $q_{\varphi(i)}$ for each $1 \leq i \leq n$.

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 $a$ and $b$ of an integral domain $R$ are associates of each other if and only if $a = ub$ for some unit $u$ in $R$. This, in particular, implies that condition (2) in Definition 1.11 is equivalent to the following:

(2′) if $u,t$ are units and $p_1,\ldots,p_n,q_1,\ldots,q_m$ are irreducible elements in $R$ such that $up_1 \cdots p_n = tq_1 \cdots q_m$, then there exists a bijection $\varphi:\{1,\ldots,n\} \to \{1,\ldots,m\}$ such that $p_i = q_{\varphi(i)}$ for each $1 \leq i \leq n$.

Proof. Write $a = xb$ and $b = ya$, so that $b = (yx)b$. Since $R$ is an integral domain, we can cancel out $b$ and conclude that $1 = xy$. As for the equivalence of (2) and (2′), we need only to note that the commutativity of $R$ can be used to consolidate all the extra units we get from the associate condition and send them to the leftmost term. $\square$

## 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 $\mathbb{Z}$ satisfies this property. In fact, we have not even proved that $\mathbb{Z}$ 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 $n,m \in \mathbb{Z}$ is an integer $d$ such that\ (1) $d \mid n$ and $d \mid m$; (2) $d’ \mid n$ and $d’ \mid m$ imply that $d’ \mid d$.

We write $(a,b)$ to denote an arbitrary greatest common divisor of $n$ and $m$.

The adjective greatest refers to the fact that $(n,m)$ sits on top of all the other divisors of $n$ and $m$ with respect to the “divides” relation. That greatest common divisors always exist in $\mathbb{Z}$ is familiar to us:

Theorem 2.2 (Existence of greatest common divisors). Given $n,m \in \mathbb{Z}$, there exists a unique positive greatest common divisor of $n$ and $m$, which we denote by $\gcd(n,m)$.

Proof. $1$ always divides both $n$ and $m$, and so the set $D$ of common divisors of $n$ and $m$ is nonempty. Since every element of $D$ is bounded above by $\operatorname{min}(n,m)$, the greatest common divisor exists. Uniqueness follows from the uniqueness of maximum elements of subsets of $\mathbb{Z}$. $\square$

Let us now examine the notions of multiples and divisors from a ring-theoretic viewpoint. Recall that an ideal of a commutative ring $R$ is a subset $I$ of $R$ such that $a \in R$ and $x \in I$ imply $ax \in I$, and that $x,y \in I$ implies $x+y \in I$. A principal ideal is an ideal of the form $(x) = \{ax: a \in R\}$ for a fixed $x \in I$; in other words, $(x)$ is the collection of all “multiples” of $x$.

Now, if $d$ divides $x$, then every multiple of $x$ is a multiple of $d$, and so $(d) \supseteq (x)$. Indeed, if $d$ is a common divisor of $x$ and $y$, then $(d)$ contains the ideal generated by $x$ and $y$

as $\lambda x$ and $\mu y$ are multiples of $d$. What happens when $(d)$ equals $(x)+(y)$?

Proposition 2.3. Let $R$ be an integral domain and let $d,x,y \in R$. If $(d) = (x) + (y)$, then $d$ is a greatest common divisor of $x$ and $y$.

Proof. $(\Rightarrow)$. Suppose that $(d) = (x)+(y)$. This, in particular, implies that $x,y \in (d)$, whence $d \mid x$ and $d \mid y$. Moreover, $d \in (x)+(y)$, and so we can find $\lambda,\mu \in R$ such that $d = \lambda x + \mu y$. Therefore, if $d’ \in R$ is such that $d’ \mid x$ and $d’ \mid y$, then $d’ \mid (\lambda x + \mu y)$, whence $d’ \mid d$. It follows that $d$ is a greatest common divisor of $x$ and $y$. $\square$

In other words, the principal ideal generated by $(x,y)$ equals the ideal generated by $x$ and $y$. 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 $R$ is a principal ideal domain (PID) if every ideal of $R$ is a principal ideal. In other words, given an ideal $I$ of $R$, we can find $x \in I$ such that $I = (x)$.

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

Proposition 2.5 (Generalized Bézout’s identity). Let $R$ be a PID. Given $x,y \in R$, there exists a greatest common divisor $d$ of $x$ and $y$. Moreover,there exist $\lambda$ and $\mu$ such that $d = \lambda x + \mu y$.

Proof. $(x)+(y)$ is an ideal in $R$, and so we can find $d \in R$ such that $(d) = (x)+(y)$. By Proposition 2.3, $d$ is a greatest common divisor of $x$ and $y$. Moreover, $d \in (x) + (y)$, and so we can find $\lambda ,\mu \in R$ such that $d = \lambda x + \mu y$. $\square$

## 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 $\mathbb{Z}$:

Theorem 3.1 (Division algorithm). Given $n,m \in \mathbb{Z}$ with $m > 0$, there exist $q,r \in \mathbb{Z}$ such that $n = qm + r$ with $% $. For notational convenience, we shall write $\operatorname{divQ}(n,m)$ and $\operatorname{divR}(n,m)$ to denote $q$ and $r$, respectively.

Proof. Let

Since $N$ is a subset of $\mathbb{N}$, there exists the smallest element $n – k_0m$. Observe that $% $, for otherwise $n – (k_0 – 1)m \in N$, contradicting minimality. It now suffices to set $q = k_0$ and $r = n – k_0 m$. $\square$

Corollary 3.2 (Euclidean algorithm). The following algorithm always outputs the greatest common divisor of $n,m \in \mathbb{Z}$ with $m > 0$:

   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 $a,b \in \mathbb{Z}$ with $b > 0$,

We let $d = \gcd(a,b)$, $q = \operatorname{divQ}(a,b)$, $r = \operatorname{divR}(a,b)$, and $d_r = \gcd \left( b,r \right)$ for notational convenience. Since $d \mid a$ and $d \mid b$, we see that $d \mid a – q b$. Now,$r = a – qb$, and so $d \mid r$. It follows that $d \leq d_r$.

Conversely, $d_r \mid b$ and $d_r \mid r$, and so $d_r \mid qb + r$. Since $a = qb+r$, we see that $d_r \mid a$. Therefore, $d_r \leq d$, whence we conclude that $d = d_r$.

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

In particular, $\gcd(n,m) = \gcd(r_{k-1},r_k)$. Since the $r_k$’s decrease at each step, the algorithm terminates in finitely many steps. When it terminates, we get $r_k = 0$, and so

as was claimed. $\square$

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

Definition 3.3. An integral domain $R$ is said to be a Euclidean domain in case there exists a function $d:R \to \mathbb{Z}_{\geq 0}$ such that
(1) $d(0) = 0$;
(2) if $a,b \in R \smallsetminus \{0\}$, then $d(a) \leq d(ab)$;
(3) if $a,b \in R \smallsetminus \{0\}$, then there exist $q,r \in R$ such that $a = qb + r$ and that either $r = 0$ or $% $.

Theorem 3.1 shows that $\mathbb{Z}$ is a Euclidean domain with the size function $d(n) = |n|$. 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 $R$ be a Euclidean domain and fix and ideal $I$ of $R$. Let $a_0$ be the element of $I$ such that the size $d(a_0)$ is minimal; this is possible because $d$ is $\mathbb{Z}_{\geq 0}$-valued. We pick an arbitrary $a \in I$ and invoke the division algorithm to write $a = qa_0 + r$. If $r \neq 0$, then $% $. But then $r = a – qa_0 \in I$, contradicting the minimality of $a_0$ in $I$. We conclude that $r = 0$. Since $a$ was arbitrary, we conclude that every element of $I$ is a multiple of $a_0$. $\square$

## 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 $\gcd(n,m)$ is an integer linear combination of $n$ and $m$. This implies the following important fact.

Theorem 4.1. If $n,m \in \mathbb{Z}$, $p$ is a prime number in $\mathbb{Z}$, and $p \mid nm$, then either $p \mid n$ or $p \mid m$. Conversely, if $p \in \mathbb{Z} \smallsetminus \{-1,0,1\}$ is such that $n,m \in \mathbb{Z}$ and $p \mid nm$ always imply either $p \mid m$ or $p \mid n$, then $p$ is a prime number.

Proof. Assume that $n,m \in \mathbb{Z}$, $p$ is a prime number in $\mathbb{Z}$ such that $(q,a) = \lambda q + \lambda b$. $\mathbb{Z}$, and $p \mid nm$. We also suppose that $p \nmid n$. Since the only divisors of $p$ are $1,-1,p,-p$, we see that $\gcd(p,n) = 1$. Generalized Bézout’s identity (Proposition 2.5) implies that we can find $\lambda,\mu \in \mathbb{Z}$ such that $\lambda p + \mu n = 1$. Multiplying through by $m$, we obtain the identity

Now, $p \mid \lambda pm$ and $p \mid \mu (nm)$, and so $p \mid m$.

Conversely, we assume that $p \in \mathbb{Z} \smallsetminus \{-1,0,1\}$ is such that $n,m \in \mathbb{Z}$ and $p \mid nm$ always imply either $p \mid m$ or $p \mid n$. If $p$ is not a prime, then we can write $p = ab$ for some integers $a,b \in \mathbb{Z} \smallsetminus \{-1,0,1\}$. In this case, however, $p\mid ab$ but $p \nmid a$ and $p \nmid b$, which contradicts the hypothesis. $\square$

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 $\mathbb{Z} \smallsetminus \{-1,0,1\}$ is can be written as a product of $\pm 1$ and positive prime numbers. To show this, it suffices to show that all positive integers $N \geq 2$ can be written as products of prime numbers. We proceed by mathematical induction. $N = 2$ is a positive prime number. Assume that the claim holds for all $% $. If $N$ is a prime number, then there is nothing to do. If $N$ is not a prime, then $N = mn$, where $% $. By induction, both $m$ and $n$ are products of positive prime numbers. This completes the proof of the claim.

It thus suffices to establish uniqueness. Specifically, we let $p_1 \cdots p_n$ and $q_1 \cdots q_m$ be two prime factorizations of $N \geq 2$. Let us assume without loss of generality that $n \leq m$. Theorem 4.1 implies that $p_1$ must divide at least one $q_i$, which we relabel to be $q_1$. Since $p_1$ and $q_1$ are both positive prime numbers, we see that $p_1 = q_1$. Cancel out $p_1$ and $q_1$ from each side, and repeat the process. If $m > n$, then we end up with the identity

This is absurd: $q_{m-n+1} \geq 2$, and so $q_{m-n+1}$ does not admit a multiplicative inverse in $\mathbb{Z}$. It follows that $m = n$. $\square$

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 $p$ in an integral domain $R$ is said to be a prime element in case $p \neq 0$, $p$ is not a unit, and, for all $a,b \in R$, $p \mid ab$ implies $p \mid a$ or $p \mid b$.

The relationship between irreducible and prime elements is as follows:

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

Proof. Let $p$ be a prime element of an integral domain $R$. We suppose for a contradiction that $p = ab$ for some non-units $a,b \in R$. This, in particular, implies that $p \mid ab$. If we assume that $p \nmid b$, then $px = a$ for some $x \in R$. Substituting $p = ab$, we see that $abx = a$. $R$ is an integral domain, and so we can cancel out $a$ to conclude that $bx = 1$. It follows that $b$ is a unit in $R$, which contradicts the assumption that $b$ is a non-unit. We conclude that $p$ is irreducible.

We now assume that $R$ is a PID and fix an irreducible element $q$ of $R$. Assume that $q \mid ab$ and that $q \nmid a$. We let $d = (q,a)$. $q$ is irreducible, and so either $d = uq$ for some unit $u$ in $R$ or $d$ itself is a unit. Since $q \nmid a$, we conclude that $d$ is a unit. By generalized Bézout’s identity (Proposition 2.5), we can find $\lambda,\mu \in R$ such that $\lambda q + \mu a = d$. In other words, $d^{-1} \lambda q + d^{-1} \mu a = 1$. Multiplying through by $b$, we obtain the identity

Now, $q \mid d^{-1} \lambda q b$ and $q \mid d^{-1} \mu a b$, and so $q \mid b$. It follows that $q$ is a prime element of $R$. $\square$

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 $R$ is either a unit in $R$ or can be written as a finite product of irreducible elements of $R$. 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.

Tags:

Categories:

Updated: