Ring Theory

Prerequisites: Basic Concepts of Abstract Algebra and Group Theory

Introduction

Ring theory studies rings of many kinds.

The ring-theoretic topics covered in this article are inseparable from the theory of divisibility in number theory. First, analogous to normal subgroups in group theory, we introduce the kernel of a ring homomorphism, called an ideal of a ring; this is in fact a generalization of the notion of numbers from number theory to general rings. Then, by extending the notions of primes, the Euclidean algorithm, and prime factorization from the ring of integers to general rings, we obtain different types of integral domains.

Many conclusions from number theory still hold in other common rings. In one sense, part of the work of ring theory is to ask whether these number-theoretic conclusions continue to hold in general rings; if not, what restrictions must be imposed on a ring to make them hold.

Notation

When there is no risk of ambiguity, this article may omit the multiplication symbol for a ring and write the ring $(R,+,\cdot)$ simply as the ring $R$. In the ring $R$, the additive identity is also called the zero element and denoted by $0$; the multiplicative identity is also called the unit element and denoted by $1$.

The Definition of a Ring Here Does Not Require a Unit

Note that the definition of a ring in this article does not require a unit. Some texts require rings to have a unit, in which case the statements of some conclusions here need slight adjustment. For example, ideals here can be defined in terms of subrings, whereas other texts may need to define them in terms of additive subgroups.

Ideals

As in the case of groups, we can define subrings and ring homomorphisms.

Subring

For a ring $(R,+,\cdot)$ and its subset $S$, if $(S,+,\cdot)$ is also a ring, then $S$ is called a subring of $R$ (subring).

Example: The Ring of Integers $\mathbf Z$

For every integer $n$, $n\mathbf Z=\{nk:k\in\mathbf Z\}$ is a subring of $\mathbf Z$.

Ring Homomorphism

For rings $(R,+,\cdot)$ and $(S,\oplus,\odot)$, if $\pi$ preserves the ring's addition and multiplication, that is, if for all $r_1,r_2\in R$ we have $\pi(r_1+r_2)=\pi(r_1)\oplus\pi(r_2)$ and $\pi(r_1\cdot r_2)=\pi(r_1)\odot\pi(r_2)$, then the map $\pi:R\rightarrow S$ from $R$ to $S$ is called a homomorphism (homomorphism).

The Case Where the Definition of a Ring Requires a Unit

If the definition of a ring requires a unit, the definition of a ring homomorphism often also requires that the unit map to the unit. For a homomorphism between nonzero unital rings, this additional requirement only ensures that the homomorphism does not map the entire unital ring to the zero element.

Example: The Ring of Integers $\mathbf Z$ (Continued)

For any nonzero integer $n$, the reduction modulo n map $\pi:\mathbf Z\rightarrow\mathbf Z/n\mathbf Z$, where $\pi(a)=\bar a$, is a ring homomorphism.

The discussion of kernels and images of group homomorphisms carries over here almost verbatim. The relative size of the image of a homomorphism determines whether it is surjective, while whether its kernel is trivial determines whether it is injective. The kernel of a ring homomorphism is defined as follows:

Kernel of a Homomorphism

The kernel (kernel) of a homomorphism from a ring $R$ to a ring $S$, $\pi:R\rightarrow S$, is $\{r\in R:\pi(r)=0\}$, denoted by $\ker\pi$, where $0$ is the additive identity of $S$.

Clearly, the kernel and image of a ring homomorphism are both subrings. Conversely, not every subring can be the kernel of a ring homomorphism. A subring that can be the kernel of a ring homomorphism is called an ideal of the ring.

Ideal

For a ring $R$ and its subring $I$, $I$ is called an ideal of $R$

• left ideal (left ideal) if, for every $r\in R$, $rI\subseteq I$, where $rI=\{ra:a\in I\}$;
• right ideal (left ideal) if, for every $r\in R$, $Ir\subseteq I$, where $Ir=\{ar:a\in I\}$;
• ideal (ideal) if $I$ is a left ideal of $R$ and also a right ideal of $R$.

The ideal $I$ is required to be closed under left and right multiplication by elements of $R$. This condition is natural: elements of an ideal map to the zero element under a ring homomorphism, and multiplying zero on either the left or the right by any number should give zero, which is exactly the required closure. Moreover, because the additive structure of a ring is an Abelian group, every subgroup is a normal subgroup; and the multiplicative structure of a ring is very primitive, so it imposes no additional restrictions on substructures. This shows that closure under left and right multiplication is also sufficient.

Example: The Ring of Integers $\mathbf Z$ (Continued)

As an example, the subring $n\mathbf Z$ mentioned above is actually an ideal of $\mathbf Z$. It is the set of all multiples of $n$. Multiplying a multiple of $n$ by any integer again gives a multiple of $n$. In fact, all ideals of $\mathbf Z$ have this form; such a ring is called a principal ideal domain. For general rings, some ideals are not sets of multiples of a single element; the existence of such general rings was the original motivation for studying ideals (rather than simply multiples)¹.

Quotient Ring

As with groups, ideals of a ring allow us to define a quotient ring (quotient ring) on the set of all cosets (in the sense of the additive group). Consider the set

$$R/I=\{a+I:a\in R\},$$

where the coset $a+I=\{a+b:b\in I\}$. It can be proved that $I$ is an ideal if and only if the operations

$$\begin{aligned} (a+I)+(b+I)&=(a+b)+I,\\ (a+I)(b+I)&=(ab)+I \end{aligned}$$

are well-defined; that is, their results do not depend on the choice of representatives in the cosets. Under these operations, $R/I$ forms a ring. As in the case of groups, we can establish the first isomorphism theorem (first isomorphism theorem) for rings, and there is a natural homomorphism from a ring to its quotient ring. These proofs show that ideals of rings and normal subgroups of groups play the same role in homomorphisms of the corresponding structures.

First Isomorphism Theorem

Let $\pi:R\rightarrow S$ be a homomorphism from a ring $R$ to a ring $S$. Then $\ker\pi$ is an ideal of $R$, and $R/\ker\pi\cong\pi(R)$ is a subring of $S$.

Natural Homomorphism

For a ring $R$ and its ideal $I$, the map given by $\pi(r)=r+I$, namely $\pi:R\rightarrow R/I$, is a surjective homomorphism from $R$ to $R/I$, called the natural homomorphism (natural homomorphism) from the ring $R$ to the quotient ring $R/I$.

Example: The Ring of Integers $\mathbf Z$ (Continued)

For example, the congruence classes of integers modulo $n$ form the quotient ring $\mathbf Z/n\mathbf Z$, obtained from $\mathbf Z$ by its ideal $n\mathbf Z$. This also explains the meaning of the notation $\mathbf Z/n\mathbf Z$. The reduction modulo $n$ map $\pi:\mathbf Z\rightarrow\mathbf Z/n\mathbf Z$ mentioned above is the natural map here, and its kernel is exactly the ideal $n\mathbf Z$.

Other isomorphism theorems also hold for rings.

Second Isomorphism Theorem

Suppose a ring $R$ has a subring $A$ and an ideal $B$. Then $A+B=\{a+b:a\in A,b\in B\}$ is also a subring of $R$, $A\cap B$ is an ideal of $A$, $B$ is an ideal of $A+B$, and $(A+B)/B\cong A/(A\cap B)$.

Third Isomorphism Theorem

Suppose a ring $R$ has ideals $I,J$ with $I\subseteq J$. Then $J/I$ is also an ideal of $R/I$, and $(R/I)/(J/I)\cong R/J$.

Correspondence Theorem

Suppose a ring $R$ has an ideal $I$. Then there is a bijection between all subrings containing $I$ of the ring $R$, $\mathcal S=\{S:I\subseteq S\subseteq R\}$, and all subgroups of the quotient group $R/I$, $\mathcal T=\{T:T\le R/I\}$, given by $\varphi:\mathcal S\rightarrow\mathcal T$, which maps $S\in\mathcal S$ to $S/I\in\mathcal T$. This bijection preserves the inclusion relation between subrings, and ideals of $R$ always map to ideals of $R/I$.

These theorems will serve as a foundation for the discussion of the structures of rings and ideals later in the article.

Operations on Ideals

Various operations can be defined on ideals of a ring. This is analogous to defining notions such as greatest common divisors and least common multiples on the divisibility structure of the integers.

Operations on Ideals

Suppose a ring $R$ has ideals $I,J$. We can define the following operations:

• Sum of ideals (sum): $I+J=\{a+b:a\in I,b\in J\}$;
• Product of ideals (product): $IJ=\{\sum_{i=1}^na_ib_i:a_i\in I,b_i\in J\}$, the set consisting of all finite sums of products of the form $ab$;
• Intersection of ideals (intersection): $I\cap J$.

It is easy to verify that the results of these operations are still ideals of the ring.

Example: The Ring of Integers $\mathbf Z$ (Continued)

Consider the ring of integers $\mathbf Z$. For the ideals $n\mathbf Z$ and $m\mathbf Z$, we obtain

$$\begin{aligned} n\mathbf Z+m\mathbf Z&=\gcd(m,n)\mathbf Z,\\ (n\mathbf Z)(m\mathbf Z)&=(mn)\mathbf Z,\\ (n\mathbf Z)\cap(m\mathbf Z)&=\mathrm{lcm}(m,n)\mathbf Z. \end{aligned}$$

In general, for a ring $R$ and its ideals $I$ and $J$, we always have

$$IJ\subseteq I\cap J\subseteq I,J\subseteq I+J.$$

Using these definitions, the Chinese remainder theorem for the integers can be generalized to general rings. Before that, however, notions such as primes and coprimality must also be generalized to general rings.

Maximal Ideals

The properties of a ring can be understood through the structure of its ideals.

A nonzero ring $R$ always has two trivial ideals, namely $\{0\}$ and $R$. If $R$ is also commutative, a ring with only these two ideals can only be a field².

Theorem

Let $R$ be a commutative nonzero unital ring. Then $R$ is a field if and only if $R$ has only the trivial ideals $\{0\}$ and $R$.

Proof

If $R$ is a field, then for any nonzero ideal $I$, choose any nonzero element $a\in I$. For every element $r\in R$ of the field, we have $r=(ra^{-1})a\in (ra^{-1})I\subseteq I$, so $I=R$. Conversely, for any $a\in R$ with $a\neq 0$, one can verify that $aR=\{ar:r\in R\}$ is an ideal. It must equal $R$, so there exists $b\in R$ with $ab=1$. Thus $a$ has an inverse, and $R$ is a field.

The commutativity condition is necessary here. Otherwise, both the left ideals and the right ideals would need to be restricted to the trivial ones to guarantee that the ring is a division ring.

This conclusion can be generalized to the case where the ring itself is not a field. We then consider quotient rings instead and ask when the quotient ring of a commutative nonzero unital ring is a field. The quotient ring $R/I$ is a field precisely when the quotient ring $R/I$ has only the trivial ideals. By the correspondence theorem, this means that the original ring $R$ has no ideal strictly between the ideal $I$ being quotiented out and the original ring $R$. Such an ideal $I$ is called a maximal ideal.

Maximal Ideal

For a ring $R$ and its ideal $M$, if $M\neq R$ and the only ideals containing $M$ in $R$ are $M$ and $R$, then $M$ is called a maximal ideal (maximal ideal).

Theorem

Let a commutative nonzero unital ring $R$ have an ideal $M$. Then the quotient ring $R/M$ is a field if and only if $M$ is a maximal ideal.

Example: The Ring of Integers $\mathbf Z$ (Continued)

For example, in the ring of integers $\mathbf Z$, the ideal $n\mathbf Z$ is a maximal ideal if and only if $n$ is prime. For a prime $p$, the quotient ring $\mathbf Z/p\mathbf Z$ is a field, also denoted by $\mathbf F_p$.

Not every ring has maximal ideals, but every nonzero unital ring has a maximal ideal.

Theorem (Krull)

For a nonzero unital ring $R$, any ideal $I\neq R$ of $R$ has a maximal ideal $M$ such that $I\subseteq M$.

Proof

The idea is to use Zorn's lemma. Consider all ideals containing $I$ in $R$ that are proper (that is, ideals not equal to $R$); let the set of these ideals be $\mathcal S$. Since $I\in\mathcal S$, it is nonempty, and it is partially ordered by inclusion. For any chain $J_0\subseteq J_1\subseteq\cdots\subseteq J_n\subseteq\cdots$ in it, let $J$ be their union. It is easy to verify that this is also an ideal. Moreover, $J\neq R$; otherwise $1\in J$, so there would be an $n$ with $1\in J_n$, contradicting that $J_n$ is proper. Hence, by Zorn's lemma, there exists a maximal ideal $M\supseteq I$.

Maximal ideals are analogous to irreducible elements in divisibility theory. This is because inclusion of ideals corresponds to divisibility of integers: having no ideal as a proper superset is analogous to having no factor that divides it further. However, the concept of a maximal ideal is broader than that of an irreducible element, because not every ideal is principal.

Prime Ideals

The condition for a field is more stringent than that for an integral domain. An ideal that ensures the quotient ring is an integral domain is called a prime ideal, analogous to the notion of a prime number in divisibility theory.

Prime Ideal

For a commutative ring $R$ and its ideal $P$, if $P\neq R$ and for any elements $a,b\in R$, $ab\in P$ always implies $a\in P$ or $b\in P$, then $P$ is called a prime ideal (prime ideal).

This definition may look somewhat unmotivated, but in comparison with the definition of a prime number, it is also natural.

Theorem

Let a commutative nonzero unital ring $R$ have an ideal $P$. Then the quotient ring $R/P$ is an integral domain if and only if $P$ is a prime ideal.

Proof

For a commutative nonzero unital ring $R$, the quotient ring $R/P$ is an integral domain if and only if $R/P$ has no zero divisors. Write the coset $a+P$ as $\bar a$. The absence of zero divisors in $R/P$ is equivalent to $\bar a\bar b=\bar 0$ always implying $\bar a=\bar 0$ or $\bar b=\bar 0$. By the correspondence theorem, this is equivalent to $ab\in P$ always implying $a\in P$ or $b\in P$.

In the ring of integers $\mathbf Z$, $n\mathbf Z$ is a maximal ideal and a prime ideal if and only if $n$ is prime. In a general commutative ring, a maximal ideal always implies a prime ideal, but the converse need not hold; this can be seen from the properties of their corresponding quotient rings.

Theorem

For a commutative nonzero unital ring $R$, every maximal ideal is necessarily a prime ideal.

We will see later that the converse holds only in rings with good properties, sufficiently similar to the ring of integers.

Principal Ideals

As with the notion of subgroups, in discussions of rings it is often necessary to consider ideals generated by a subset.

Ideal Generated by a Subset

For a nonzero unital ring $R$ and its nonempty subset $A\subseteq R$, if $I$ is the smallest (under inclusion) ideal containing $A$ among the ideals of $R$, then $I$ is called the ideal generated by the subset $A$ (ideal generated by a subset), denoted by $(A)$. In this case, $A$ is called a generating set (generating set) of $(A)$.

Principal Ideal

The ideal generated by a single element $a\in R$ is called a principal ideal (principal ideal), denoted by $(a)$. In this case, $a$ is called a generator of $(a)$ (generator).

For a set $A$, we can construct the ideal it generates. First, define

$$\begin{aligned} RA&=\{r_1a_1+\cdots+r_na_n:r_i\in R,a_i\in A,n\in\mathbf Z\},\\ AR&=\{a_1r_1+\cdots+a_nr_n:r_i\in R,a_i\in A,n\in\mathbf Z\}. \end{aligned}$$

These are in fact the left ideal and right ideal generated by $A$, respectively. The ideal generated by the subset $A$ is then $RAR$. For a commutative ring, all these structures are the same.

All ideals $n\mathbf Z$ in the ring of integers are principal ideals, and below they are often denoted by $(n)$.

Integral Domains

An integral domain is a nonzero commutative unital ring with no zero divisors. This concept is precisely a generalization of the ring of integers. However, the properties of the resulting ring may not be good enough to allow every conclusion from the divisibility theory of integers to be copied verbatim. To generalize conclusions from number theory, we can impose further restrictions on integral domains. The three most common types are Euclidean domains, principal ideal domains, and unique factorization domains; each preceding concept is strictly contained in the following one.

Divisibility

We first generalize the relevant concepts from the divisibility theory of integers to general commutative rings.

Divisibility

Let a commutative ring $R$ have elements $a,b\in R$. If there exists $x\in R$ such that $a=bx$, then $b$ is said to divide (divide) $a$, denoted by $b\mid a$. In this case, $b$ is called a divisor (divisor) of $a$.

Associates

Let a commutative ring $R$ have elements $a,b\in R$. If they differ only by a unit, that is, if there exists a unit $u\in R$ such that $a=bu$, then $a$ and $b$ are called associates (associate).

Divisibility is a partial order on a ring, while being associates is an equivalence relation on a ring. From the perspective of ideals, $a\mid b$ is equivalent to $(b)\subseteq (a)$, and $a$ and $b$ being associates is equivalent to $(a)=(b)$. Therefore, when discussing elements of a ring, we usually do not distinguish between associates. As in the case of integers, the greatest common divisor of $a$ and $b$ in a commutative ring is defined as the infimum of $\{a,b\}$.

Greatest Common Divisor

For a commutative ring $R$ and elements $a,b\in R$, if there exists a nonzero element $d\in R$ such that $d\mid a$ and $d\mid b$, and, for any element satisfying $d'\mid a$ and $d'\mid b$, the element $d'$ also satisfies $d'\mid d$, then $d$ is called a greatest common divisor (greatest common divisor) of $a$ and $b$, denoted by $\gcd(a,b)$.

In an integral domain, the greatest common divisor is unique up to associates. The discussion below is restricted to integral domains.

Integral domains also admit a notion analogous to primes. In integer theory, primes have two equivalent definitions, but in a general integral domain these two definitions correspond to different concepts:

Prime Element

Let an integral domain $R$ have a nonzero element $p\in R$. If $(p)$ is a prime ideal, that is, if $p$ is not a unit and $p\mid ab$ always implies $p\mid a$ or $p\mid b$, then $p$ is called a prime element (prime).

Irreducible Element

Let an integral domain $R$ have a nonzero element $r\in R$. If $r$ is not a unit and, for any $a,b\in R$ with $r=ab$, either $a$ or $b$ is a unit, then $r$ is called an irreducible element (irreducible), or $r$ is simply called irreducible. Conversely, if $r=ab$ and $a,b\in R$ are both not units, then $r$ is called reducible.

One can show that an irreducible element $r$ corresponds to the principal ideal $(r)$, which is maximal among all principal ideals of the ring. However, in a general integral domain not every ideal is principal, so the concepts of irreducible elements and maximal ideals are not equivalent.

Analogous to the proof that a prime ideal in a principal ideal domain is maximal, we can generally prove the following result:

Theorem

Let $R$ be an integral domain. If $a\in R$ is a prime element, then $a$ is also an irreducible element.

Proof

Let $r\in R$ be a prime element, and let $a,b\in R$ satisfy $r=ab$. Since $r$ is prime, assume without loss of generality that $r\mid a$. Then $a=cr=cba$. Since the cancellation law holds in an integral domain, $1=bc$, so $b$ has the inverse $c$. This shows that $r$ is irreducible.

The converse does not hold.

Counterexample

In the quadratic integer ring $\mathbf Z[\sqrt{-5}]$, $3$ is irreducible, but $9=3\cdot 3=(2+\sqrt{-5})(2-\sqrt{-5})$, so it is not prime.

Here we prove this counterexample. Readers unfamiliar with quadratic integer rings should first read the section on quadratic integer rings. Let $N(\cdot)$ be the norm on the quadratic integer ring. For every factorization $3=ab$, we have $N(a)N(b)=N(3)=9$. If $a,b$ are not units, then $N(a)$ and $N(b)$ are both greater than $1$, so necessarily $N(a)=N(b)=3$. But there is no such element in $\mathbf Z[\sqrt{-5}]$; equivalently, $x^2+5y^2=3$ has no integer solution. This shows that $3$ is irreducible. To show that $3$ is not prime, it remains to prove that $3$ does not divide $2\pm\sqrt{-5}$, which is clear.

Euclidean Domains

Further reading: (Extended) Euclidean Algorithm, Bézout's identity

A Euclidean domain is an integral domain in which the Euclidean algorithm can be performed.

Euclidean Domain

For an integral domain $R$, if there exists a map $N:R\setminus\{0\}\rightarrow\mathbf N$ such that for every $a,b\in R$ with $b\neq 0$, there exist $q,r\in R$ satisfying $a=qb+r$ and either $r=0$ or $N(r)<N(b)$, then $R$ is called a Euclidean domain (Euclidean domain, ED). The map $N$ is called the norm of elements in the Euclidean domain (norm).

Other Equivalent Definitions

The definition used in this article defines the norm only for nonzero elements. Different texts may handle the definition of a Euclidean domain differently. For example, some texts may additionally define $N(0)=0$; however, the value of $N(0)$ is not used in the division algorithm with remainder that follows, so this is immaterial. As another example, the definition on Wikipedia also requires the norm $N$ to satisfy the property that for every nonzero $a,b\in R$, $N(a)\le N(ab)$. However, it is easy to verify that if a Euclidean domain $R$ has a norm $N(\cdot)$ satisfying the properties required by the definition here, we can define a norm $N'(a)=\min_{b\in R\setminus\{0\}} N(ab)$ satisfying the additional property $N'(a)\le N'(ab)$. Thus, these different definitions are equivalent.

This definition is in fact a generalization of division with remainder over the integers. The existence of a norm makes it possible to measure the relative sizes of the remainder and divisor. Thus, during the Euclidean algorithm, the norms of the successive remainders keep decreasing; because the norm takes values in the natural numbers, the process must eventually end with $r=0$. This yields the Euclidean algorithm in a Euclidean domain.

The ability to perform the Euclidean algorithm means that greatest common divisors can be computed efficiently in a Euclidean domain. Completely analogously to the divisibility theory of integers, we can prove that the result of the Euclidean algorithm is a greatest common divisor and that Bézout's identity holds, with the coefficients determined by the extended Euclidean algorithm.

Theorem

For a Euclidean domain $R$ and elements $a,b\in R$, applying the Euclidean algorithm to $a$ and $b$ yields $d$, which is a greatest common divisor of $a$ and $b$, and there exist $x,y\in R$ such that $d=ax+by$; conversely, every element of the form $ax+by$ is a multiple of $d$.

In the language of ring theory, all elements of the form $ax+by$ are precisely the elements of the ideal $(a,b)$, and this theorem says that $(a,b)$ is necessarily the principal ideal $(d)$.

In fact, every ideal in a Euclidean domain is principal.

Theorem

Every ideal in a Euclidean domain is principal.

Proof

Let $R$ be a Euclidean domain and let $I$ be one of its ideals. If $I=\{0\}$, it is clearly principal. Suppose $I$ is nonzero. By definition, the ring $R$ has a norm $N(\cdot)$, so choose a nonzero element in $I$, denoted by $d$, of minimum norm. Then for any $a\in I$, we have $a=qd+r$ with $r=0$ or $N(r)< N(d)$. Since $r=a-qd\in I$, the choice of $d$ implies $r=0$, so $a=qd\in (d)$. Hence $I$ is necessarily principal.

Principal Ideal Domains

An integral domain in which every ideal is principal is called a principal ideal domain. This is a class of integral domains with very good properties and one that occurs frequently. In such domains, the concept of an ideal is equivalent to the concept of a multiple among the integers.

Principal Ideal Domain

For an integral domain $R$, if every ideal is principal, then it is called a principal ideal domain (principal idel domain, PID).

Therefore, the last theorem of the previous section can be restated as follows:

Theorem

Every Euclidean domain is a principal ideal domain.

In a principal ideal domain, maximal ideals are equivalent to ideals generated by irreducible elements. Just as primes and irreducible elements are equivalent among the integers, these two concepts are also equivalent in a principal ideal domain. Hence maximal ideals and prime ideals are completely equivalent as well.

Theorem

Let a principal ideal domain $R$ have a nonzero ideal $I$. Then $I$ is a prime ideal if and only if $I$ is a maximal ideal.

Proof

It suffices to prove that every prime ideal is maximal. Suppose a principal ideal domain $R$ has a nonzero prime ideal $(p)$ and an ideal $(a)$ with $(p)\subseteq(a)\subseteq R$. This means $a\mid p$, so there exists $b\in R$ with $p=ab$. But since $(p)$ is a prime ideal, $ab\in(p)$ implies $a\in(p)$ or $b\in(p)$. If $a\in(p)$, then $(a)\subseteq (p)$, so $(a)=(p)$. If $b\in(p)$, then $b=cp$, so $p=acp$; since $p\neq 0$, we have $1=ac$, meaning that $a$ has inverse $c$, and hence $(a)=R$. Thus $(p)$ is a maximal ideal.

Corollary

Let a principal ideal domain $R$ have a nonzero element $r$. Then $r$ is a prime element if and only if $r$ is an irreducible element.

The analysis of Bézout's identity in the previous section carries over to principal ideal domains.

Theorem

Let $R$ be a principal ideal domain and let $a,b\in R$ be nonzero elements. Let $d\in R$ be a generator of the ideal $(a,b)$. Then $a$ and $b$ have greatest common divisor $d$, unique up to associates; moreover, there exist $x,y\in R$ such that $ax+by=d$.

In other words, Bézout's identity still holds in a principal ideal domain. Although both types of domains have greatest common divisors, the main difference is that in a Euclidean domain the greatest common divisor can be computed efficiently by the Euclidean algorithm, whereas a principal ideal domain generally has no such efficient algorithm.

Unique Factorization Domains

A more general concept than a principal ideal domain is a unique factorization domain. The unique factorization theorem for integers is the fundamental theorem of arithmetic. A similar unique factorization theorem continues to hold in some integral domains that are not principal ideal domains. Such domains are called unique factorization domains.

Unique Factorization Domain

For an integral domain $R$, if every nonzero nonunit element $r$ can be written in the form $r=p_1\cdots p_n$, where $p_1,\cdots,p_n$ are irreducible elements that may repeat, and this factorization is unique up to associates and reordering, then $R$ is called a unique factorization domain (unique factorization domain, UFD).

The fundamental theorem of arithmetic says that the ring of integers $\mathbf Z$ is a unique factorization domain.

The counterexample above, in which an irreducible element is not prime, involved the integral domain $\mathbf Z[\sqrt{-5}]$, where unique factorization no longer holds. However, in every unique factorization domain, irreducible elements and prime elements are equivalent.

Theorem

For a unique factorization domain $R$ and its nonzero element $a\in R$, $a$ is a prime element if and only if $a$ is an irreducible element.

Proof

It suffices to prove that every irreducible element is prime. For an irreducible element $r$, if $r\mid ab$, then there exists $c\in R$ such that $ab=rc$. Since $R$ is a unique factorization domain, we can factor $a,b,c\in R$ into products of irreducible elements. Comparing the two sides and using uniqueness of factorization, $r$ must be associate to an irreducible factor of either $a$ or $b$, so $r$ divides one of $a$ and $b$. Thus $r$ is also prime.

Every principal ideal domain is a unique factorization domain.

Theorem

Every principal ideal domain is a unique factorization domain.

Proof

Let $R$ be a principal ideal domain and let $r\in R$ be neither zero nor a unit. To show that $r$ can be uniquely factored into a product of irreducible elements, we proceed in two steps: first prove existence, then prove uniqueness.

The existence of a factorization is fairly natural. If $r$ is already irreducible, no further factorization is needed. Otherwise, there must be $r_1r_2$ such that $r=r_1r_2$ and $r_1,r_2$ are not units. If both $r_1$ and $r_2$ are irreducible, no further factorization is needed; otherwise, factor whichever of $r_1$ and $r_2$ is not irreducible further, and $r$ can be written as a product of more elements. Thus, as long as not all factors in the product are irreducible, the factorization process can continue. It must terminate after finitely many steps. Otherwise, the axiom of choice would guarantee an infinite chain of elements from $R$, $\{r_{(i)}\}_{i=0}^\infty$, satisfying $r_{(0)}=r$ and $r_{(i+1)}\mid r_{(i)}$ for all $i\in\mathbf N$, with all these divisibility relations strict, meaning that no two elements in the chain are associates. In the language of ideals, this corresponds to a strictly increasing infinite chain of ideals: $I_{0}\subset I_{1}\subset \cdots\subset I_{i}\subset\cdots\subset R$, where $I_i=(r_{(i)})$. It is easy to verify that their union $I=\bigcup_{i=0}^\infty I_i$ is also an ideal, and hence must be principal. Let $a$ be a generator of the principal ideal $I$, so there exists $n\in\mathbf N$ with $a\in I_n$. Therefore, $I=(a)\subseteq I_n$. This shows that such a strictly increasing infinite chain of ideals cannot exist, so the factorization process above must terminate in finitely many steps.

Then prove uniqueness of the factorization. We can induct on the number of factors in a factorization. The key step is to verify that if $r=p_1p_2\cdots p_n=q_1q_2\cdots q_m$ and $n\le m$, then $p_1$ must be associate to some $q_j$. This uses the earlier result that irreducible elements in a principal ideal domain are prime. Since $p_1$ is an irreducible element in $R$, it is also prime, so by induction on the product on the right, there must be an element $q_j$ such that $p_1\mid q_j$. Thus there is a $c\in R$ with $q_j=p_1c$. Since $q_j$ and $p_1$ are both irreducible, the definition forces $c$ to be a unit, so $p_1$ and $q_j$ are associates. We can then use cancellation to cancel $p_1$ and $q_j$ from the two sides, and multiply the associate relating them into any one of the remaining elements. By the induction hypothesis, $p_2\cdots p_n$ and $q_1\cdots q_{j-1}q_{j+1}\cdots q_m$ have the same number of irreducible elements and are the same up to associates. The theorem follows.

Finally, greatest common divisors still exist in a unique factorization domain.

Theorem

Let a unique factorization domain $R$ have nonzero elements $a,b\in R$, with factorizations $a=up_1^{r_1}\cdots p_n^{r_n}$ and $b=vp_1^{s_1}\cdots p_n^{s_n}$, where $u,v$ are units, $p_1,\cdots,p_n$ are distinct irreducible elements, and $r_i,s_i$ are natural numbers. Then one greatest common divisor is $d=p_1^{\min\{r_1,s_1\}}\cdots p_n^{\min\{r_n,s_n\}}$.

This actually shows that the property of having greatest common divisors is weaker than the unique factorization theorem³.

Example: Quadratic Integer Rings

Further reading: Quadratic Fields

Understanding abstract algebra cannot be separated from examples. It was the need to study the properties of a class of algebraic integers in the course of research on Fermat's Last Theorem that gradually led to the ring theory we have today⁴. Here we discuss the simplest algebraic integers, namely quadratic integers. Proofs of many conclusions in this section require advanced knowledge of algebraic number theory, so they are omitted.

A quadratic integer (quadratic integer) is a complex root of an integer-coefficient quadratic equation $\alpha^2+b\alpha+c=0$ whose coefficient of the quadratic term is one. Every quadratic integer has the form

$$\alpha=a+b\omega,~(a,b\in\mathbf Z)$$

where

$$\omega=\begin{cases} \dfrac{1+\sqrt{D}}{2},& D\equiv 1\pmod 4,\\ \sqrt D,& D\equiv 2,3\pmod 4, \end{cases}$$

where $D$ is squarefree.

Analysis

By the quadratic formula, the roots of this equation can be written as

$$\alpha=\frac{-b\pm\sqrt{b^2-4c}}{2}.$$

When $b=2k+1$ is odd, this root can be written as

$$\alpha=-k-\frac{1\pm\sqrt{4(k^2+k-c)+1}}{2}.$$

Otherwise, when $b=2k$ is even, this root can be written as

$$\alpha=-k\pm\sqrt{k^2-c}.$$

Thus, we can conclude inductively that every quadratic integer has the form above.

It is easy to verify that for such an $\omega$, the set $\mathbf Z[\omega]=\{a+b\omega:a,b\in\mathbf Z\}$ forms a ring. This is called a quadratic integer ring (quadratic integer ring), and its field of fractions is the quadratic field $\mathbf Q(\sqrt D)$. When $D>0$, all quadratic integers are real, so it is also called a real quadratic integer ring; when $D<0$, all quadratic integers other than the integers are complex, so it is also called an imaginary quadratic integer ring.

All quadratic integer rings $\mathbf Z[\omega]$ are integral domains. When $D=-1$, $\mathbf Z[\sqrt{-1}]$ (also written $\mathbf Z[\mathrm{i}]$) is called the ring of Gaussian integers; when $D=-3$, $\mathbf Z\left[\dfrac{1+\sqrt{-3}}{2}\right]$ is called the ring of Eisenstein integers.

For a quadratic integer $a+b\omega$, define its conjugate (conjugate) to be $a+b\bar\omega$, where

$$\bar\omega=\begin{cases} \dfrac{1-\sqrt{D}}{2},& D\equiv 1\pmod 4,\\ -\sqrt D,& D\equiv 2,3\pmod 4, \end{cases}$$

Note that when $D>0$, quadratic integers are real, so this notion of conjugation is not exactly the same as conjugation of complex numbers; however, both are special cases of conjugation of algebraic elements in field theory. The conjugate quadratic integers are roots of the same integer-coefficient quadratic equation.

The norm can be defined on a quadratic integer ring:

$$\begin{aligned} N(a+b\omega)&=(a+b\omega)(a+b\bar\omega)\\ &=\begin{cases} a^2+ab+\dfrac{1-D}{4}b^2,& D\equiv 1\pmod 4,\\ a^2-Db^2,& D\equiv 2,3\pmod 4. \end{cases} \end{aligned}$$

The norm of a quadratic integer is always an integer. In particular, when $D<0$, the norm is always a natural number. The norm preserves multiplication: $N(ab)=N(a)N(b)$.

The units in a quadratic integer ring are precisely the elements whose norms are $\pm1$. When $D>0$, this is equivalent to considering the solutions of the Pell equations $x^2-Dy^2=\pm1$ or $x^2-Dy^2=\pm4$. When $D<0$, it is easy to verify that, except for the two special cases in which the units in the ring of Gaussian integers $\mathbf Z[\rm{i}]$ are $\{\pm1,\pm\rm{i}\}$ and the units in the ring of Eisenstein integers $\mathbf Z[\omega]$ are $\{\pm1,\pm\omega,\pm\omega^2\}$, all other units are just $\{\pm1\}$.

The norm $N(\alpha)$ defined on a quadratic integer ring can be used to prove that it is a Euclidean domain. When $D>0$, its absolute value $|N(\alpha)|$ must be used as the norm in the definition of a Euclidean domain. Using this norm, one can prove that when $D<0$,

$$D=-1,-2,-3,-7,-11$$

or when $D>0$,

$$D=2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73$$

the corresponding quadratic integer rings are Euclidean domains under the norm $|N(\cdot)|$. However, the norm in the definition of a Euclidean domain need not be the norm defined above. For example, when $D=14,69$, the corresponding quadratic integer rings are also Euclidean domains, but a different norm is needed. For $D<0$, it can be proved that the cases listed above are all the Euclidean domains among quadratic integer rings.

More complicated methods can also determine whether a quadratic integer ring is a principal ideal domain. It can be proved that when $D<0$, only

$$D=-1,-2,-3,-7,-11,-19,-43,-67,-163$$

give quadratic integer rings that are principal ideal domains. Comparing the results above, we see that the case $D=-19$, for example, provides an example of a principal ideal domain that is not a Euclidean domain. When $D>0$, no complete result is currently known.

However, in quadratic integer rings, unique factorization domains and principal ideal domains are equivalent. The results above show, for example, that $\mathbf Z[\sqrt{-5}]$ is not a principal ideal domain, and therefore is not a unique factorization domain. We have already demonstrated through an example that unique factorization fails there:

$$9=3\times3=(2+\sqrt{-5})\times(2-\sqrt{-5}).$$

Using the same example, one can show that the ideal $(3,2+\sqrt 5)$ is also not principal. We will see later that a simple example of a unique factorization domain that is not a principal ideal domain is the polynomial ring $\mathbf Z[x]$.

Although many quadratic integer rings are not unique factorization domains, they are all Dedekind domains. This means that every nontrivial ideal in a quadratic integer ring can be uniquely factored into a product of prime ideals. But if the quadratic integer ring itself is not a principal ideal domain, these prime ideal factors do not necessarily correspond to prime elements, so unique factorization (that is, factoring numbers into products of primes) no longer holds. This was also the original motivation for studying ideals rather than numbers.

Polynomial Rings

Further reading: Introduction to Polynomial Techniques

In algorithmic contests, various polynomial operations are frequently encountered. Multiplication, inversion, and remainder operations on polynomials can be regarded as generalizations of operations on numbers to polynomial rings. The language of abstract algebra makes it possible to understand the properties of these operations on polynomial rings more quickly.

Polynomial

For a nonzero commutative unital ring $R$, a polynomial (polynomial) over $R$ is a formal sum

$$\sum_{k=0}^{n}a_kx^k = a_0+a_1x+\cdots+a_{n-1}x^{n-1}+a_nx^n,$$

where $n\in\mathbf N$ and, for every $k$, $a_k\in R$. These $a_k$ are called the coefficients (coefficient) of the polynomial, and the corresponding $a_kx^k$ is called a term (term) of the polynomial; the term $a_kx^k$ has $k$ as its degree (degree).

A polynomial whose coefficients are all zero (that is, the zero element) is called the zero polynomial (zero polynomial), denoted by $0$. For any other polynomial, assume without loss of generality that $a_n\neq 0$, so $a_nx^n$ is the term of greatest degree among the nonzero-coefficient terms. The natural number $n$ is then called the degree (degree) of the polynomial, and the term $a_nx^n$ is called the leading term (leading term); $a_n$ is also called the leading coefficient (leading coefficient). A polynomial whose leading coefficient is equal to one (the unit) is called a monic (monic) polynomial. The degree of the zero polynomial is unspecified, or is defined to be $-\infty$.

The $x$ appearing in polynomial notation is called the indeterminate (indeterminate) of the polynomial. It has no intrinsic meaning or range of values. Its only role is to mark the position of a coefficient through its exponent. Thus, a polynomial can also be written as a sequence over $R$:

$$(a_0,a_1,...,a_{n-1},a_n,0,0,\cdots).$$

However, such a sequence can have only finitely many nonzero terms. If two polynomials correspond to the same sequence of coefficients, the two polynomials are called equal. This is equivalent to filling in the missing zero coefficients so that their formal sums are exactly the same. Below, we do not distinguish between the formal-sum notations of equal polynomials; when necessary, the reader can fill in the omitted zero coefficients.

Sometimes it is necessary to substitute an element of the ring for the indeterminate in a polynomial. For example, if $f(x)$ is a polynomial over $R$ and $a\in R$, then the result of substituting $a$ into $f(x)$ is $f(a)$. This means replacing $x$ with $a$ in the formal sum of the polynomial, obtaining an arithmetic expression in $R$, whose value is $f(a)$ after evaluation in $R$.

“Polynomial” and “Polynomial Function”

These two concepts should not be confused. A polynomial is only a finite sequence of coefficients; it does not automatically become a function. Although substituting an element of the ring for the indeterminate does map a polynomial to a polynomial function, this map need not be injective. For example, $f(x)=x^p-x$ as a polynomial over the field $\mathbf F_p$ is clearly not the zero polynomial; but $f(x)$, as a polynomial function $\mathbf F_p\rightarrow \mathbf F_p$, is identically zero (that is, Fermat's little theorem). Although the two concepts are different, many notions for polynomial functions can be generalized to polynomials, such as defining formal derivatives, indefinite integrals, and composition of polynomials by analogy with polynomial functions. These formal operations do not depend on any topological structure, but many operation laws still hold.

For the polynomials

$$\begin{aligned} f(x)&=a_0+a_1x+\cdots+a_{n-1}x^{n-1}+a_nx^n,\\ g(x)&=b_0+b_1x+\cdots+b_{n-1}x^{n-1}+b_nx^n, \end{aligned}$$

define polynomial addition by

$$f(x)+g(x) = (a_0+b_0)+(a_1+b_1)x+\cdots+(a_{n-1}+b_{n-1})x^{n-1}+(a_n+b_n)x^n,$$

and define polynomial multiplication by

$$f(x)g(x) = a_0b_0+(a_1b_0+a_0b_1)x+(a_2b_0+a_1b_1+a_0b_2)x^2+\cdots,$$

where the coefficient of the $x^k$ term is $\sum_{i=0}^ka_{k-i}b_i$. Under these definitions of addition and multiplication, it can be proved that all polynomials over $R$ form a ring, denoted by $R[x]$.

The degree of a polynomial $f(x)$ is denoted by $\deg f(x)$. Polynomials of degree zero are constant polynomials, and they, together with the zero polynomial, correspond to the embedding of $R$ into $R[x]$. Clearly, $R$ has zero divisors if and only if $R[x]$ has zero divisors.

Theorem

The polynomial ring $R[x]$ is an integral domain if and only if $R$ is an integral domain.

In an integral domain $R$, the results of addition and multiplication in the polynomial ring $R[x]$ satisfy

$$\begin{aligned} \deg(f(x)+g(x)) &\le \max\{\deg f(x),\deg g(x)\},\\ \deg(f(x)g(x)) &= \deg f(x) + \deg g(x). \end{aligned}$$

Here we set $\deg 0 = -\infty$. Therefore, the units in a polynomial ring must be the units among its constant polynomials. No polynomial of degree one or higher is a unit.

The discussion below is restricted to polynomials over integral domains.

Convention

Below, we use the expressions “polynomial over the ring $R$” and “polynomial in the polynomial ring $R[x]$” interchangeably. For example, a polynomial being irreducible over the ring $R$ means that it is irreducible in the ring $R[x]$. Moreover, if $R$ is a subring of $S$, then a polynomial over $R$ automatically becomes a polynomial over $S$; this will not be explained separately.

Polynomial Rings over Fields

Among polynomial rings over integral domains, the simplest properties are found in those over a field $F$, namely $F[x]$. Since coefficients can be divided, division with remainder can be defined. For a nonzero polynomial $f(x)$, let its norm be $N(f(x))=\deg f(x)$. Then, in $F[x]$, for a polynomial $f(x)$ and a nonzero polynomial $g(x)$, we can clearly perform division with remainder:

$$f(x)=g(x)q(x)+r(x),$$

where $q(x),r(x)\in F[x]$ and $r(x)=0$ or $\deg r(x)<\deg g(x)$. This shows that every polynomial ring over a field is a Euclidean domain.

Theorem

For a field $F$, the polynomial ring $F[x]$ is a Euclidean domain, a principal ideal domain, and a unique factorization domain.

In algorithmic contests, because of numerical precision, the polynomial ring $\mathbf F_p[x]=(\mathbf Z/p\mathbf Z)[x]$ is often used, where the modulus $p$ is required to be prime. Such a ring permits operations such as the Euclidean algorithm. However, for an arbitrary modulus $n$, the corresponding polynomial ring $(\mathbf Z/n\mathbf Z)[x]$ is not even an integral domain.

The existence of division with remainder means that every root of a polynomial corresponds to one of its linear factors.

Root

A root (root) of a polynomial $f(x)$ is an element for which $f(\xi)=0$, with $\xi\in F$.

Theorem

For a field $F$ and a polynomial $f(x)$ over it, if $\xi\in F$, then $\xi$ is a root of $f(x)$ if and only if $f(x)$ has the linear factor $(x-\xi)$.

Proof

Division with remainder gives $q(x),r(x)$ such that $f(x)=q(x)(x-\xi)+r(x)$ and $\deg r(x)<\deg(x-\xi)=1$. Hence, $r(x)$ is a constant polynomial or the zero polynomial. Let $r(x)=c$; then $f(x)=q(x)(x-\xi)+c$. Substituting $x=\xi$ gives $0=a(\xi)=c$, so $f(x)=q(x)(x-\xi)$.

The concept of a root can be extended to multiple roots.

Multiple Root

If a polynomial $f(x)$ has a factor $(x-\xi)^k$, and $(x-\xi)^{k+1}$ does not divide $f(x)$, then $\xi$ is called a root of $f(x)$ with multiplicity $k$ (root of multiplicity $k$). If $k>1$, the root $\xi$ is called a multiple root (multiple root) of $f(x)$; if $k=1$, the root $\xi$ is called a simple root (simple root) of $f(x)$.

Theorem

If, over a field $F$, a polynomial $f(x)$ has roots $\xi_1,\cdots,\xi_k$, possibly with repetitions, then it must have the factor $(x-\xi_1)\cdots(x-\xi_k)$. Consequently, over the field $F$, a polynomial $f(x)$ of degree $n$ has at most $n$ roots, counted with multiplicity.

Proof

This follows immediately from the fact that $F[x]$ is a unique factorization domain.

Although the unique factorization theorem holds for polynomials over a field, there is no general method for determining whether a given polynomial is reducible. The case of relatively small degree is easier. For example, every linear polynomial is irreducible. Over certain fields, every irreducible polynomial is linear. Such fields are called algebraically closed fields. In such a field, every polynomial that is not identically a nonzero constant has a root, so every polynomial of degree greater than one can be factored further. The complex field $\mathbf C$ is one such example. Over the real field $\mathbf R$, there are irreducible quadratic polynomials; over the rational field $\mathbf Q$, the structure of irreducible polynomials is more complicated. The page on field theory contains more discussion of polynomials over the rational and finite fields.

All of the conclusions above concern polynomials over fields. More generally, polynomials over integral domains can often be reduced to this case.

Now consider a unique factorization domain $R$ and its polynomial ring $R[x]$. Direct computation in $R[x]$ is restricted because coefficients often cannot be divided. We can instead extend $R$ to its field of fractions $F$ and then, in $R[x]$, consider a polynomial $f(x)$ and factor it in $F[x]$. Since $F[x]$ is a unique factorization domain, the factorization in $F[x]$ of $f(x)$ yields a factorization in $R[x]$. Fortunately, this idea always works.

Gauss's Lemma

Let $R$ be a unique factorization domain and $F$ its field of fractions. If $f(x)\in R[x]$, then in $F[x]$ we have $f(x)=A(x)B(x)$, and there exist $s,t\in F$ such that $a(x)=sA(x)\in R[x]$, $b(x)=tB(x)\in R[x]$, and $f(x)=a(x)b(x)$. Therefore, if $f(x)$ is irreducible in $R[x]$, then it is irreducible in $F[x]$.

Proof

Suppose $f(x)\in R[x]$ is reducible in $F[x]$, with $f(x)=A(x)B(x)$. Let $r_a$ and $r_b$ be the least common multiples of the denominators of all coefficients in $A(x)$ and $B(x)$, respectively. Then $\tilde a(x)=r_aA(x)$ and $\tilde b(x)=r_bB(x)$ are both polynomials over $R$. Let $r=r_ar_b$; then $rf(x)=\tilde a(x)\tilde b(x)$. If $r$ is a unit in $R$, we can use the factorization $f(x)=(r^{-1}\tilde a(x))\tilde b(x)$, which clearly satisfies the lemma.

Otherwise, if $r$ has an irreducible factor $p$, we need to show that this factor can be canceled from both sides while keeping all coefficients in the integral domain $R$. Note that $p$ must also be prime, so $(p)$ is a prime ideal. Reducing both sides of the equation modulo $p$ gives the polynomial equation in $(R/(p))[x]$, namely $0=\bar a(x)\bar b(x)$, where $\bar a$ and $\bar b$ are the reduced polynomials. Since $R/(p)$ is an integral domain, $(R/(p))[x]$ is also an integral domain, so we may assume $\bar a(x)=0$. This means that all coefficients of $\tilde a(x)$ are divisible by $p$. Hence, the factor $p$ can be canceled directly from both sides of the equation.

By the definition of a unique factorization domain, $r$ has at most finitely many such irreducible factors. After canceling them finitely many times, we reach the case where $r$ is a unit in $R$. The lemma follows.

Corollary

Let $R$ be a unique factorization domain and $F$ its field of fractions. If $f(x)\in R[x]$ and all nonzero coefficients of $f(x)$ are coprime (that is, their greatest common divisor is a unit in $R$), then $f(x)$ is irreducible in $R[x]$ if and only if $f(x)$ is irreducible in $F[x]$.

In other words, irreducible elements of the integer-coefficient polynomial ring $\mathbf Z[x]$ are irreducible elements of $\mathbf Q[x]$. An effective method for determining whether an integer-coefficient polynomial is irreducible is the Eisenstein criterion. By Gauss's lemma, it also provides a method for determining whether a rational-coefficient polynomial is irreducible.

Eisenstein Criterion

Let an $n$-th-degree integer-coefficient polynomial be $f(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}+a_nx^n$. If there exists a prime $p$ such that $p\mid a_i$ for every $i=0,1,\cdots,n-1$, but $p$ does not divide $a_n$ and $p^2$ does not divide $a_0$, then $f(x)$ is irreducible over the rational field $\mathbf Q$. If $\gcd(a_0,a_1,\cdots,a_n)=1$, then $f(x)$ is also irreducible over the ring of integers $\mathbf Z$.

Proof

Gauss's lemma shows that if a polynomial $f(x)$ is reducible over the field of rational numbers $\mathbf Q$, then it is also reducible over the integer ring $\mathbf Z$. Suppose that $f(x)=b(x)c(x)$ is its factorization in $\mathbf Z[x]$. Reducing both sides of the equation modulo the prime $p$ gives the factorization $\overline{f}(x)=\overline{b}(x)\overline{c}(x)$ in $\mathbf F_p[x]$. However, the conditions of the theorem state that $\overline{f}(x)=x^n$, so there must be an integer $m$ such that $\overline b(x)=x^m$ and $\overline c(x)=x^{n-m}$, where $0<m<n$. Thus, the constant terms $b_0$ and $c_0$ of the factors $b(x)$ and $c(x)$ are both multiples of $p$. Consequently, the constant term $a_0=b_0c_0$ of $f(x)$ must be a multiple of $p^2$. This contradicts the given conditions.

Example

1. The polynomial $x^3-2$ is irreducible in $\mathbf Q[x]$. This follows immediately by applying the Eisenstein criterion with $p=2$.
2. The polynomial $x^4+1$ is irreducible in $\mathbf Q[x]$. Otherwise, $(x+1)^4+1=x^4+4x^3+6x^2+4x+2$ would also be reducible. However, applying the Eisenstein criterion with $p=2$ shows that the latter is irreducible.

For a unique factorization domain $R$, the polynomial ring over its corresponding field of fractions $F$ is a unique factorization domain, and Gauss's lemma says that factorizations of polynomials over the field of fractions $F$ correspond to factorizations of polynomials over the original domain $R$. Therefore, $R[x]$ is also a unique factorization domain. Thus we have the following theorem:

Theorem

The polynomial ring $R[x]$ is a unique factorization domain if and only if $R$ is a unique factorization domain.

Here $\mathbf Z[x]$ provides an example showing that a unique factorization domain need not be a principal ideal domain. For example, $(2,x)$ is not a principal ideal in $\mathbf Z[x]$.

There are many ways to extend a polynomial ring to a larger set. For example, for a polynomial ring $R[x]$ over an integral domain, we can extend it to its field of fractions, denoted by $R(x)$. This field of fractions is often called the field of rational fractions, whose elements have the basic form $\dfrac{f(x)}{g(x)}$, where $f(x)$ and $g(x)$ are polynomials.

Multivariable polynomial rings

Polynomial rings can be generalized to the case of several indeterminates. For a commutative ring with unity $R$, define the polynomial ring over $R$, namely the univariate polynomial ring $R[x]$. We can then define the polynomial ring over $R[x]$, $R[x][y]$, which can be viewed as the bivariate polynomial ring $R[x,y]$ over $R$. In this way, the $k$-variable polynomial ring $R[x_1,\cdots,x_k]$ over $R$ can be defined inductively. When $R$ is an integral domain, every multivariable polynomial ring over it is an integral domain; similarly, the unique factorization domain property is inherited by every multivariable polynomial ring.

Formal power series rings

We may also consider the case where a formal sum can contain arbitrarily many nonzero coefficients. A formal power series (formal power series) over a commutative ring with unity $R$ is defined by

$$\sum_{k=0}^\infty a_kx^k=a_0+a_1x+a_2x^2+\cdots.$$

Addition and multiplication of power series can be defined in the same way as for the polynomial ring $R[x]$. The formal power series then also form a ring, denoted by $R[[x]]$. The convergence of formal power series need not be considered here, because in fact each formal power series is merely a sequence of coefficients, without any additional topological structure.

The structure of the formal power series ring is interesting. In a polynomial ring over an integral domain, the only invertible elements are constants. In a formal power series ring, however, we can have

$$(1-x)^{-1}=\sum_{k=0}^\infty x^k=1+x+x^2+\cdots.$$

This phenomenon is general. As long as the constant term $a_0$ of a formal power series is a unit in $R$, the formal power series $\sum_{k=0}^\infty a_kx^k$ is also invertible. Indeed, if we suppose that

$$\left(\sum_{k=0}^\infty a_kx^k\right)\left(\sum_{k=0}^\infty b_kx^k\right)=1,$$

then, by writing down the system of equations that the coefficients must satisfy, we can recursively obtain expressions for $b_k$, involving only the inverse of $a_0$.

Various operations can be defined on the formal power series ring, such as inversion, division, compositional inversion, formal differentiation, and elementary functions; see An Introduction to Polynomial Techniques for details.

Formal Laurent series rings

The formal power series ring can be extended further to allow terms with negative degrees. A formal Laurent series (formal laurent series) over a commutative ring with unity $R$ is defined by

$$\sum_{k=N}^\infty a_kx^k,$$

where $N\in\mathbf Z$. Thus a formal Laurent series can have finitely many terms of negative degree. Extending the preceding addition and multiplication to formal Laurent series gives the formal Laurent series ring, denoted by $R((x))$. If $F$ is a field, then $F((x))$ is also a field.

The formal Laurent series ring has applications in Lagrange inversion.

Chinese remainder theorem

Related reading: Chinese remainder theorem

In number theory, the Chinese remainder theorem is often used to solve systems of Diophantine congruences. A Chinese remainder theorem can likewise be established for general commutative rings with unity. Each congruence equation amounts to specifying the image of an unknown in some quotient ring; thus, the Chinese remainder theorem for a commutative ring with unity determines an element of the ring from its images in these quotient rings.

This discussion can be translated into formal language. For a nonzero commutative ring with unity $R$ and its ideals $I_1,\cdots,I_n$, consider the ring homomorphism $\varphi:R\rightarrow R/I_1\times \cdots R/I_n$, which maps $r$ to $(r+I_1,\cdots,r+I_n)$. Here, $r+I_i$ is a coset, while $\times$ denotes the direct product of rings:

Direct product

For rings $R_1$ and $R_2$, define multiplication on the direct product $R_1\times R_2$ of their additive groups by multiplying the corresponding components. Then $R_1\times R_2$ becomes a ring, called the direct product (direct prodcut) of the rings $R_1$ and $R_2$, still denoted by $R_1\times R_2$.

The kernel of the homomorphism $\varphi$ is $\ker\varphi=I_1\cap\cdots\cap I_n$. The question answered by the Chinese remainder theorem is under what conditions this map is surjective.

In the number-theoretic case, the theorem requires the moduli to be coprime. This condition generalizes to the ring-theoretic setting.

Comaximal ideals

Let $R$ be a ring with ideals $I$ and $J$. If $I+J=R$, then $I$ and $J$ are called comaximal (comaximal).

For a ring with unity, if we consider the principal ideals $(a)$ and $(b)$, this condition is equivalent to the existence of $x,y\in R$ such that $ax+by=1$, analogous to Bézout's identity for coprime integers. Using this definition, we can establish the Chinese remainder theorem (Chinese remainder theorem) for commutative rings with unity exactly as in the case of the integer ring.

Chinese remainder theorem

Let a nonzero commutative ring with unity $R$ have ideals $I_1,\cdots,I_n$. If they are pairwise comaximal, then the ring homomorphism $\varphi$ defined above is surjective, and its kernel is the product of these ideals, $\ker\varphi=I_1\cap\cdots\cap I_n=I_1\cdots I_n$, and hence

$$R/(I_1\cdots I_n)=R/(I_1\cap\cdots\cap I_n)\cong R/I_1\times\cdots\times R/I_n.$$

Proof

The theorem contains substantial information, but only two conclusions need to be proved: $\varphi$ is surjective and $I_1\cap\cdots\cap I_n=I_1\cdots I_n$. The key is to make good use of the comaximality condition.

First consider the case $n=2$. Since the ideals $I_1$ and $I_2$ are comaximal, namely $I_1+I_2=R$, the unity $1$ of $R$ can be written as $a_1+a_2$, where $a_i\in I_i$. Since $a_1\in I_1$ and $a_1=1-a_2\in 1+I_2$, we have $\varphi(a_1)=(I_1,1+I_2)$; similarly, $\varphi(a_2)=(1+I_1,I_2)$. Thus $(\varphi(a_2),\varphi(a_1))$ plays a role analogous to a basis in a vector space. Therefore, for any target image $(r_1+I_1,r_2+I_2)$, we can find its preimage under $\varphi$, namely $r_1a_2+r_2a_1$. This shows that $\varphi$ is surjective.

We still need to prove $I_1\cap I_2=I_1I_2$. For a general ring, $I_1I_2\subseteq I_1\cap I_2$ always holds; the key is the converse. For any $r\in I_1\cap I_2$, we have $r=r(a_1+a_2)=ra_1+ra_2\in I_1I_2$. Hence $I_1\cap I_2\subseteq I_1I_2$ also holds. This proves the claim.

For $n>2$, mathematical induction is needed. The key inductive step is to prove that for pairwise comaximal ideals $I_1,\cdots,I_n$, the ideals $I_1$ and $I_2\cdots I_n$ are always comaximal. Since $I_1$ is comaximal with each of $I_2,\cdots,I_n$, for every $i=2,\cdots,n$ there exist $a_i\in I_1$ and $b_i\in I_i$ such that $1=a_i+b_i$. Therefore, $1=(a_2+b_2)\cdots(a_n+b_n)$. Hence $1\in (b_2\cdots b_n)+I_1\subseteq I_1+(I_2\cdots I_n)$. This shows that $I_1$ and $I_2\cdots I_n$ are comaximal.

Application: Lagrange interpolation formula

Related reading: Lagrange interpolation, Fast polynomial interpolation

The interpolation problem asks, given a collection of point values $\{(x_i,y_i)\}_{i=1}^n$, for a polynomial $f(x)$ over a field $F$ satisfying $f(x_i)=y_i$ for every $i=1,\cdots,n$. We of course assume that all $x_i$ are distinct. The Lagrange interpolation formula gives the general solution to this type of problem.

For a polynomial $f(x)$ over a field $F$, the condition $f(x_i)=y_i$ is equivalent to $x_i$ being a root of the polynomial $f(x)-y_i$, and hence equivalent to $(x-x_i)\mid(f(x)-y_i)$, or $f(x)\equiv y_i\pmod{x-x_i}$. Thus the interpolation problem is equivalent to solving the system of congruences

$$\begin{cases} f(x)\equiv y_1&\pmod{x-x_1},\\ f(x)\equiv y_2&\pmod{x-x_2},\\ \cdots\\ f(x)\equiv y_n&\pmod{x-x_n}. \end{cases}$$

These linear polynomials $\{x-x_i\}_{i=1}^n$ are pairwise coprime. According to the Chinese remainder theorem, the solution must have the form

$$f(x)=\sum_{i=1}^ny_iM_i(x),$$

where $M_i(x)=m_i(x)\prod_{j\neq i}(x-x_j)$ and $M_i(x)\equiv 1\pmod{x-x_i}$. By the equivalence derived above, this is equivalent to $M_i(x_i)=1$, namely

$$m_i(x_i)\prod_{j\neq i}(x_i-x_j) = 1.$$

We may take $m_i(x)$ to be a constant polynomial, namely

$$m_i(x) = \frac{1}{\prod_{j\neq i}(x_i-x_j)}.$$

This gives the Lagrange interpolation formula

$$f(x)=\sum_{i=1}^ny_i\frac{\prod_{j\neq i}(x-x_j)}{\prod_{j\neq i}(x_i-x_j)}.$$

In general, extending this method also yields the Hermite interpolation formula, which allows prescribed values for several derivatives of the polynomial at each point.

Application: the multiplicative group of residue classes modulo integers

Related reading: Primitive roots, Fundamental theorem of finitely generated Abelian groups

As an application of the Chinese remainder theorem and related group-theoretic material, we discuss here the structure of the multiplicative group of integers modulo $n$. We omit the overline notation for residue classes in this section.

The multiplicative group of integers modulo $n$ (multiplicative group of integers modulo $n$) is $(\mathbf Z/n\mathbf Z)^\times$, namely the multiplicative group of units (also called the unit group) in the quotient ring $\mathbf Z/n\mathbf Z$. The order of the group $(\mathbf Z/n\mathbf Z)^\times$ is $\varphi(n)$, because having an inverse is equivalent to being coprime to $n$. Here $\varphi(n)$ is the Euler totient function. Moreover, the group $(\mathbf Z/n\mathbf Z)^\times$ is always Abelian.

By the fundamental theorem of arithmetic, the modulus $n$ can be decomposed as a product of powers of distinct primes:

$$n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}.$$

It is easy to verify that for ideals in the integer ring, the condition that ideals be comaximal is equivalent to their generators being coprime. Thus, applying the Chinese remainder theorem gives

$$\mathbf Z/n\mathbf Z\cong\mathbf Z/p_1^{\alpha_1}\mathbf Z\times\cdots\times\mathbf Z/p_s^{\alpha_s}\mathbf Z.$$

An isomorphism of rings implies an isomorphism of the corresponding multiplicative structures, so

$$(\mathbf Z/n\mathbf Z)^\times\cong(\mathbf Z/p_1^{\alpha_1}\mathbf Z)^\times\times\cdots\times(\mathbf Z/p_s^{\alpha_s}\mathbf Z)^\times.$$

This shows that $\varphi(n)=\varphi(p_1^{\alpha_1})\cdots\varphi(p_n^{\alpha_n})$, that is, the Euler totient function is multiplicative.

Therefore, to study the general case of a modulus, it suffices to consider the case where a prime power $p^k$ is the modulus. For prime powers, we need to consider separately the cases $p=2$ and $p$ an odd prime:

• For $p=2$, direct verification gives $(\mathbf Z/2\mathbf Z)^\times\cong C_1$ and $(\mathbf Z/4\mathbf Z)^\times\cong C_2$. For $k\ge3$, we have $(\mathbf Z/2^k\mathbf Z)^\times\cong C_2\times C_{2^{k-2}}$.

  ??? note "Proof" Direct calculation using the binomial theorem gives

  $$
  \begin{aligned}
  5^{2^{k-2}}=(1+2^2)^{2^{k-2}}&\equiv 1\pmod {2^k},\\
  5^{2^{k-3}}=(1+2^2)^{2^{k-3}}&\equiv 1+2^{k-1}\pmod {2^k}.
  \end{aligned}
  $$
  
  Thus $5$ is an element of order $2^{k-2}$ in $(\mathbf Z/2^k\mathbf Z)^\times$. At the same time, $-1$ and $5^{2^{k-3}}$ are two distinct elements of order two, so $-1\notin\langle 5\rangle$. Therefore, the intersection of $\langle-1\rangle$ and $\langle 5\rangle$ is trivial, and by the second isomorphism theorem
  
  $$
  (\mathbf Z/2^k\mathbf Z)^\times\cong\langle-1\rangle\times\langle 5\rangle\cong C_2\times C_{2^{k-2}}.
  $$
  

• For odd $p$, one can prove that $(\mathbf Z/p^k\mathbf Z)^\times$ is isomorphic to the cyclic group $C_{\varphi(p^k)}$.

  ??? note "Proof" To prove that $(\mathbf Z/p^k\mathbf Z)^\times$ is cyclic, the fundamental theorem of finite Abelian groups shows that it suffices to prove that each of its Sylow $q$-subgroups is cyclic. First, for the Sylow $p$-subgroup, direct calculation gives

  $$
  \begin{aligned}
  (1+p)^{p^{k-1}} &\equiv 1\pmod{p^k},\\
  (1+p)^{p^{k-2}} &\equiv 1+p^{k-1}\pmod{p^k}.
  \end{aligned}
  $$
  
  Hence, $(1+p)$ is an element of order $p^{k-1}$. In other words, the unique Sylow $p$-subgroup of $(\mathbf Z/p^k\mathbf Z)^\times$ is the cyclic group $\langle 1+p\rangle$.
  
  For the other Sylow $q$-subgroups ($q\neq p$), we can reduce to the case $k=1$ using a group homomorphism. Consider the group homomorphism $\varphi:(\mathbf Z/p^k\mathbf Z)^\times\rightarrow(\mathbf Z/p\mathbf Z)^\times$ that maps the coset $r+p^k\mathbf Z$ to the coset $r+p\mathbf Z$. The kernel of this map has size $p^{k-1}$. Therefore, when $\varphi$ is restricted to a Sylow $q$-subgroup ($q\neq p$) of $(\mathbf Z/p^k\mathbf Z)^\times$, the restricted map has trivial kernel, so this Sylow $q$-subgroup is isomorphic to the image, namely the Sylow $q$-subgroup of $(\mathbf Z/p\mathbf Z)^\times$. Thus it is enough to prove that every Sylow $q$-subgroup of $(\mathbf Z/p\mathbf Z)^\times$ is cyclic.
  
  Finally, prove that every Sylow $q$-subgroup of $(\mathbf Z/p\mathbf Z)^\times$ is cyclic. Since $(\mathbf Z/p\mathbf Z)^\times$ is a finite Abelian group, decompose it into invariant factors as
  
  $$
  C_{n_1}\times\cdots\times C_{n_r}.
  $$
  
  Here, $n_1\mid n_2\mid \cdots \mid n_r$. Thus each direct-product factor has $n_1$ elements whose orders divide $n_1$. If $r>1$, then strictly more than $n_1$ elements must satisfy the equation $x^{n_1}=1$. But $\mathbf Z/p\mathbf Z$ is a field, and a polynomial of degree $n_1$ over a field has at most $n_1$ roots, so $r=1$. That is, $(\mathbf Z/p\mathbf Z)^\times\cong C_{p-1}$.
  
  This proves $(\mathbf Z/p^k\mathbf Z)^\times\cong C_{p^{k-1}}\times C_{p-1}=C_{\varphi(p^{k})}$.
  

The structure of the multiplicative group in the general modulus case follows as well. The results above show that the multiplicative group of integers modulo $n$ is cyclic if and only if the modulus $n$ is one of

$$1,2,4,p^k,2p^k$$

where $p$ is an odd prime; otherwise, the multiplicative group of integers modulo $n$ necessarily has a subgroup $C_2\times C_2$ and cannot be cyclic. When the multiplicative group is cyclic, its generators are called primitive roots (primitive root) of the modulus. Thus, this theorem gives precisely the necessary and sufficient condition for primitive roots to exist.

Of course, the analysis of the multiplicative-group structure contains more information than the condition for primitive roots to exist. It clearly reflects the orders of different elements in the multiplicative group. In the group $(\mathbf Z/n\mathbf Z)^\times$, an element $x$ satisfying $x^k=1$, that is, a solution of the congruence $x^k\equiv 1\pmod n$, is called a $k$-th root of unity modulo $n$ ($k$-th root of unity modulo $n$); an element whose order is exactly $k$ is called a primitive $k$-th root of unity modulo $n$ (primitive $k$-th root of unity modulo $n$). Using the structure of the multiplicative group, the existence and number of these roots of unity can be computed precisely. Finally, the least common multiple of the orders of all elements in $(\mathbf Z/n\mathbf Z)^\times$, namely the smallest positive integer $k$ such that $x^k=1$ for every $x\in (\mathbf Z/n\mathbf Z)^\times$, regarded as a function of $n$, is the Carmichael function. Its many properties can all be obtained from the structure of the multiplicative group.

References and notes

• Dummitt, D.S. and Foote, R.M. (2004) Abstract Algebra. 3rd Edition, John Wiley & Sons, Inc.
• Quadratic integer - Wikipedia
• Formal power series - Wikipedia
• Multiplicative group of integers modulo $n$- Wikipedia

Footnotes

1. https://en.wikipedia.org/wiki/Ideal_(ring_theory)#History ↩

2. As in the case of groups, such a ring is called a simple ring (simple ring). A commutative simple ring can only be a field; the noncommutative case is much more complicated. ↩

3. An integral domain in which greatest common divisors exist is called a greatest common divisor domain. ↩

4. A brief history of ring theory can be found here. ↩