2.3 Rings

Thus far, our journey in abstract algebra has primarily focused on groups, which are algebraic structures defined by a single operation. Our logical next step would be exploring entities with two operations, typically denoted by addition ($+$) and multiplication ($\cdot$). The introduction of a second operation opens many possibilities in defining algebraic structures like rings, fields, modules, and vector spaces.

Among these, rings hold a place of special interest. What makes rings particularly intriguing is their ability to describe polynomial structures. The study of polynomial rings bridges the gap between algebra and geometry, playing a crucial role in algebraic geometry. Moreover, the manipulation and factorization of polynomials in rings are fundamental operations in number theory, calculus, and even in solving real-world problems. And of course, polynomials are central to the field of zero-knowledge cryptography.

Rings

def: Ring

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal G^{\mathcal A}_+ \\ &\cdot: R \times R \to R \\ \text{Associativity:} \,\, &\forall x, y, z \in R: (x \cdot y) \cdot z = x \cdot (y \cdot z) \\ \text{Distributivity:} \,\, &\forall x, y, z \in R: x\cdot (y + z) = x \cdot y + x \cdot z \\ &\forall x, y, z \in R: (x + y) \cdot z = x \cdot z + y \cdot z \\ \\ \hline \\ &R \in \mathcal R \,\,\,(R \text{ is a ring}) \end{align*}$$

note

Recall that we denote identity $e$ for $+$ by $0$ and inverse element $a^{-1}$ by $-a$.

note

Unlike groups, where we can use any symbol to denote group operation, for rings we will exclusively adhere to $+$ and $\cdot$ notation.

def: Ring with identity

$$\begin{align*} &\sphericalangle \\ & R \in \mathcal R \\ \text{Identity:} \,\, &\exists 1 \in R: \forall x \in R: x\cdot 1 = 1 \cdot x = x \\ \hline \\ &R \in \mathcal R^1 \,\,\,(R \text{ is a ring with identity}) \end{align*}$$

Example: Rings of numbers

$\Z, \mathbb{Q}, \R, \mathbb{C}$ with ordinary operations $+$ and $\cdot$ are rings. It can be verified relatively easily by checking that these sets, along with these operations, satisfy the defining properties of a ring.

Example: Rings of polynomials

Let $R \in \mathcal R$ be a ring from the example above (one of $\Z, \mathbb{Q}, \R, \mathbb{C}$). We define the polynomial ring $R[x] :=\{a_nx^n + a_{n-1}x^{n-1} + \ldots + a_1x + a_0, n \in \N_0, a_i \in R\}$.

This ring consists of polynomials with coefficients in $R$, and the operations of addition and multiplication are performed in the usual manner as they are with polynomials. For instance,

$$(x^2+3x+1)+(2x-1)=x^2+5x \\ (x^2+1)\cdot(x^2-1) = x^4-1$$

We will establish that $R[x]$ indeed forms a ring in the subsequent sections, providing a thorough exploration of its ring properties.

Proposition 2.3.1: Ring properties

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ \hline \\ &\begin{align*} & a0 = 0a = 0 \tag{a}\\ & a(-b) = (-a)b = -ab \hspace{1cm} \tag{b}\\ & (-a)(-b) = ab \tag{c}\\ \end{align*} \end{align*}$$

Proof

a.

$$a0 = a(0+0)=a0+a0 \implies 0=a0$$

b.

$$ab + a(-b) = a(b-b)=a0 = 0$$

c.

$$(-a)(-b) = -(a)(-b)=ab$$

$\square$

note

Sometimes the notation $R \in \mathcal R, 1 \ne 0$ is used to define a non-trivial ring with identity. If we have $1 = 0$ then $\forall a \in R: a = a \cdot 1 = a \cdot 0 \overset{(2.3.1)}=0$, so the ring is trivial.

def: Ring characteristic

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &S: = \{n \in \N: \forall r \in R: nr = 0\}\\ \hline \\ & \text{char }R := \begin{cases} \min S, &S \ne \empty \\ 0, &S=\empty \end{cases} \end{align*}$$

Proposition 2.3.2: Ring characteristic = identity order

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R^1 \\ \hline \\ &\text{char } R = \text{ord }_{(R, +)} 1 \end{align*}$$

Proof

$$n:=\text{ord }_{(R, +)} 1 \\ \forall r \in R: n \cdot r = (n \cdot 1) \cdot r = 0$$

On the other hand $\forall k < n, k\cdot 1 \ne 0$, thus $\text{char }R=n$

Subrings

def: Subring

$$\begin{align*} &\sphericalangle \\ &S_1 \in \mathcal R \\ &S_2 \subseteq S_1 \\ &S_2 \in \mathcal R \\ \hline \\ &S_2 \subseteq_R S_1 \,\,\, (S_2\text{ is a subring of } S_1) \end{align*}$$

Proposition 2.3.3: Subring criterion

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &S \subseteq R \\ &\begin{align*} &S \ne \empty \tag{a}\\ & \forall r, s \in S: r-s \in S \hspace{1cm} \tag{b} \\ & \forall r, s \in S: rs \in S \tag{c}\\ \end{align*} \\ \hline \\ &S \subseteq_R R \end{align*}$$

Proof

$(a), (b) \overset{(2.2.3)}{\implies} S \subseteq_{(G, +)} R$.

$(c)$ implies that operation $\cdot$ is well-defined, thus it inherits associativity and distributivity property from $R$.

$\square$

Example: A subring of integers

$n\Z:=\{nk, k \in \Z\} \subseteq_R \Z$. Let's use criterion $(2.3.3)$:

$$n\Z \ne \empty \\ \forall r_1, r_2: r_1=nk_1, r_2=nk_2 \implies \\ r_1-r_2=n(k_1-k_2)=nk_3\in n\Z \\ r_1r_2=nk_1nk_2=nk_4\in n\Z$$

Note that this ring is a ring without the identity.

Ideals and factor rings

The concept of an ideal in ring theory is analogous to that of a normal subgroup in group theory, particularly in the context of homomorphisms. Just as a normal subgroup is a subgroup that remains invariant under conjugation by any group element, an ideal is a special subset of a ring that is closed under the ring's addition and compatible with its multiplication. This similarity becomes especially visible when exploring homomorphisms, as ideals play a key role in the formation of factor rings, much like normal subgroups are used in the construction of factor groups.

def: Ideal

$$\begin{align*} &\sphericalangle \\ &S \in \mathcal R \\ &I \subseteq_R S \\ &\forall s \in S: sI \subseteq I, Is \subseteq I \\ \hline \\ &I \lhd_R S, I - \text{ideal in } S \end{align*}$$

note

We only require that $I \subseteq_R S$, but since a ring by definition is abelian in $+$, it follows from $(2.2.20)$ that $I \lhd_{(G, +)} S$.

Example: Trivial ideals

$\{0\}$ and $R$ are trivial ideals in the ring $R$.

Example: An ideal in integers

$n\Z:=\{nk, k \in \Z\} \lhd_R \Z$. We already know that $n\Z \subseteq_R \Z$. Now $\forall s \in \Z, r \in n\Z: sr = snr_1=nsr_1=nk \in n\Z \implies sn\Z \subseteq n\Z$, similarly $n\Z s \subseteq n\Z$.

def: Sum and product of ideals

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &I \lhd_R R \\ &J \lhd_R R \\ \hline \\ &\begin{align*} &I+J := \{a+b, a \in I, b \in J\} \tag{a}\\ &IJ := \{\sum_{i \leq n}{a_ib_i}, \forall n \in \Z, a_i \in I, b_i \in J\} \hspace{1cm} \tag{b}\\ \end{align*} \end{align*}$$

note

In contrast to the product concepts in set theory or group theory, the product of ideals in ring theory involves more than merely multiplying two elements together. Instead, the product of two ideals consists of all possible finite sums of products of elements from each ideal. This approach is necessary to ensure closure under the addition operation.

Many rings (inluding those that are of interest for us) are infinite and thus, their ideals are infinite as well. The study of infinite objects gives rise to a certain set of obstacles. Hoewever, we can simplify the study of ideals introducing the notion of finitely generated ideals.

def: Finitely generated ideal

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &S \subseteq R, S = \{a_1, \ldots, a_k\} \\ &\lang S \rang_I: S \subseteq \lang S \rang_I \lhd_R R \\ &\forall I: S \subseteq I \lhd_R R: \lang S \rang_I \subseteq I \\ \hline \\ &\lang S \rang_I \equiv \lang a_1, \ldots, a_k \rang_I - \text{ finitely generated ideal} \end{align*}$$

In other words finitely generated ideal for a set $S$ is a minimal ideal containing this set.

Proposition 2.3.4: Ideal properties

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &I \lhd_R R \\ &J \lhd_R R \\ \hline \\ &\begin{align*} &I+J \lhd_RR \tag{a}\\ &I+J = \lang I \cup J \rang_I \hspace{1cm} \tag{b}\\ &IJ \lhd_RR \tag{c}\\ &IJ \subseteq_R I \cap J \tag{d}\\ \end{align*} \end{align*}$$

Proof

a.

$$I+J\ne \empty \\ \forall i_1, i_2 \in I, j_1, j_2 \in J: (i_1+j_1)-(i_2+j_2)=(i_1-i_2)+(j_1-j_2) \in I+J \\ \forall r \in R, i \in I, j \in J: r(i+j) = ri + rj \in I+J \\ \forall r \in R, i \in I, j \in J: (i+j)r = ir + jr \in I+J$$

b.

Obviously, $I \cup J \subseteq I+J$ and any ideal containing $I \cup J$ should contain all sums of $I+J$.

c.

Obviously $IJ \ne \empty$. The diffence between two elements which are finite sums is still a finite sum. And $rI \subseteq I \implies rIJ \subseteq IJ$. Similarly $Jr \subseteq J \implies IJr \subseteq IJ$.

d.

Since $Ib \subseteq I, aJ \subseteq J$, it implies that any $\forall a_i \in I, b_i \in J: a_ib_i \in I \cap J$. Thus any finite sum is in $I \cap J$ as well

$\square$

As we'll see further there are many different types of rings. Actually factor rings can fall themselves into different categories depending on the underlying ideal. That's why, we need to introduce several types of ideals.

def: Principal ideal

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ & a \in R \\ \hline \\ &\lang a \rang_I - \text{principal ideal} \end{align*}$$

def: Prime ideal

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ & I \lhd_R R \\ & I \subset R \text{ (proper subset)} \\ & \forall ab \in R: ab \in I \implies (a \in I) \vee (b \in I) \\ \hline \\ &I \in \mathfrak P_I(R) \,\,\,(I \text{ is a prime ideal}) \end{align*}$$

def: Maximal ideal

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ & Q \lhd_R R, Q \ne R \\ & \forall J \lhd_R R, J \ne R: Q\cancel{\subset}J \\ \hline \\ &Q \in \mathfrak M_I(R) \,\,\,(I \text{ is a maximal ideal in } R) \end{align*}$$

Proposition 2.3.5: Each ideal is contained in some maximal ideal

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ \hline \\ &\forall I \lhd_R R, I \ne R: \exists M \in \mathfrak M_I(R): I \subseteq M\\ \end{align*}$$

Proof

Fix some $I \lhd_R R, I \ne R$, and define $S:=\{J \lhd_R R, J\ne R, I\subseteq J\}$. Then $S$ is non-empty and it has partial order $\subseteq$. Consider a chain $C$ of $S$ (that is, any non-empty subset that is fully ordered). Define $J:=\bigcup_{A \in C}A$.

Let's prove that $J \lhd_R R$:

$$\forall A \in C: 0 \in A \implies 0 \in J \implies J \ne \empty \\ \forall a, b \in J: \exists A, B \in C: a \in A, b \in B \implies \\ \begin{cases} A \subseteq B \implies a-b \in B \implies a-b \in J \\ B \subseteq A \implies a-b \in A \implies a-b \in J \end{cases}\\ \forall A \in C, r \in R: rA \subseteq A, Ar \subseteq A \implies rJ \subseteq J, Jr \subseteq J$$

Now assume $J = R \implies 1 \in J \implies \exists A \in C: 1 \in A \implies A=R \implies A \notin S$, which is a contraction to $C \subseteq S$. Thus, $J \ne R$ and $J \lhd_R R, J \ne R \implies J \in S$.

We proved that any chain in $S$ has an upper bound in $S$, by Zorn's lemma $(2.1.3)$ we finish the proof.

$\square$

note

This proposition does not imply that there is only a single maximal ideal in a ring. Instead, it suggests that for every given ideal in a ring, there exists some maximal ideal that contains it.

Proposition 2.3.6: Maximal ideal is a prime ideal

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R^{\mathcal C} \\ &I \lhd_R R \\ \hline \\ &I \in \mathfrak M_I(R) \implies I \in \mathfrak P_I(R) \end{align*}$$

Proof

For this proof we'll use propositions and definitions from section $2.4$ so you can skip this proof for now and come back to it later:

$$I \in \mathfrak M_I(R) \overset{(2.4.21)}\implies R/I \in \mathcal F \overset{(2.4.19)}\implies \\ R/I \in \mathcal R^{\mathcal{ID}} \overset{(2.4.8)}\implies I \in \mathfrak P_I(R)$$

$\square$

Like normal groups give rise to factor groups, ideals give rise to factor rings.

def: Factor ring

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &I \lhd_R R \\ &R/I - \text{factor group of } (R, +) \\ &\cdot: (r_1+I) \cdot (r_2 + I) := r_1r_2 + I \\ \hline \\ &R / I- \text{factor ring} \end{align*}$$

Proposition 2.3.7: Factor ring is a ring

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &I \lhd_R R \\ \hline \\ &R / I- \text{is a ring} \end{align*}$$

Proof

By definition $R/I$ is an abelian group under $+$.

Let's prove that multiplication is well-defined. That is no matter what represetative of the cosets we chose, the result of multiplication is the same coset:

$$r' \in r+I, s' \in s+I \implies r' = r+j_1, s' = s+j_2, j_i \in I \implies \\ r's'=rs+j_1s+rj_2+j_1j_2 \in rs+I$$

The multiplication of cosets translates to the multiplication of ring elements, thus it's associative. The identity is $1+I$. All that's left to prove is distributivity:

$$(r+I)(s+I+t+I)= (r+I)(s + t +I) = r(s+t)+I = rs+rt+I = \\ = rs+I + rt+I = (r+I)(s+I)+(r+I)(t+I)$$

The other distributive property is proved similarly.

$\square$

Homomorphisms and isomorphisms

def: Ring homomorphism

$$\begin{align*} &\sphericalangle \\ &R_1, R_2 \in \mathcal R \\ &\phi: R_1 \rightsquigarrow_{(G, +)} R_2 \\ &\forall a, b \in R_1: \phi(ab) = \phi(a)\phi(b) \\ \hline \\ &\phi: R_1 \rightsquigarrow_R R_2, \text{ or } R_1 \overset{\phi}{\rightsquigarrow}_R R_2 \,\,\, (\phi- \text{ring homomorphism}) \end{align*}$$

Proposition 2.3.8: Ring homomorphism properties

$$\begin{align*} &\sphericalangle \\ &R_1, R_2 \in \mathcal R\\ &\phi: R_1 \rightsquigarrow_R R_2 \\ \hline \\ &\begin{align*} &\phi(0)=0 \tag{a}\\ &R_1, R_2 \in \mathcal R^1, \phi(R_1)= R_2 \implies \phi(1_{R_1})=\phi(1_{R_2}) \hspace{1cm}\tag{b}\\ &\phi(R_1) \subseteq_R R_2 \tag{c}\\ &\ker \phi \lhd_R R_1 \tag{d}\\ &I \lhd_R R_2 \implies \phi^{-1}(I) \lhd_R R_1 \tag{e}\\ &I \in \mathfrak P_I(R_2) \implies \phi^{-1}(I) \in \mathfrak P_I(R_1) \tag{f}\\ \end{align*} \end{align*}$$

Proof

a.

Follows from $(2.2.23)$

b.

$$\forall y \in R_2: \exists x \in R_1: y = f(x)=f(x \cdot 1_{R_1})=f(x) \cdot f(1_{R_1})=y \cdot f(1_{R_1})$$

Similarly, $\forall y \in R_2: y = f(1_{R_1}) \cdot y$

c.

$$(2.2.23) \implies \phi(R_1) \subseteq_G R_2 \\ \forall a, b \in \phi(R_1) \implies \exists x, y \in R_1: \phi(x) = a, \phi(y)=b \implies \\ ab = \phi(x)\phi(y)= \phi(xy) = c \in \phi(R_1)$$

d.

$$(2.2.24) \implies \ker \phi \lhd_G R_1 \\ \forall r \in R_1, x \in \ker \phi: \phi(rx)=\phi(r)\phi(x) = 0 \implies rx \in \ker \phi$$

e.

$$I \lhd_R R_2, \forall a \in \phi^{-1}(I), r \in R_1: \phi(ra)=\phi(r)\phi(a) \in I \implies ra \in \phi^{-1}(I)$$

Similarly $ar \in \phi^{-1}(I)$.

f.

$$\text{(e)} \implies \phi^{-1}(I) \lhd_R R_1\\ ab \in \phi^{-1}(I) \implies \phi(ab)=\phi(a)\cdot\phi(b) \implies (\phi(a) \in I) \vee (\phi(b) \in I) \implies \\ (a \in \phi^{-1}(I)) \vee (b \in \phi^{-1}(I))$$

$\square$

note

It is not a universal rule that a homomorphism maps the identity element to the identity element. For instance, consider the mapping defined by the homomorphism $\phi: x \mapsto 0$.

def: Ring isomorphism

$$\begin{align*} &\sphericalangle \\ &R_1, R_2 \in \mathcal R \\ &\phi: R_1 \rightsquigarrow_{R} R_2 \\ &\phi: R_1 \leftrightarrow R_2 \\ \hline \\ &\phi: R_1 \cong_R R_2 \text{ or } R_1 \overset{\phi}{\cong}_R R_2 \,\,\, (\phi - \text{isomorphism}) \end{align*}$$

def: Natural homomorphism

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &I \lhd_R R \\ &\phi: R \to R/I, g \mapsto g+I \\ \hline \\ &\phi - \text{natural homomorphism} \end{align*}$$

We now introduce the isomorphism theorems for rings. These theorems bear a strong resemblance to their counterparts in group theory, both in terms of their statements and their proofs. Consequently, for the sake of conciseness, we will omit the detailed proofs here.

Proposition 2.3.9: First isomorphism theorem

$$\begin{align*} &\sphericalangle \\ &R_1, R_2 \in \mathcal R \\ &R_1 \overset{\psi}{\rightsquigarrow}_R R_2 \\ &\phi:R_1 \to R_1/\ker \psi - \text{natural homomorphism} \\ \hline \\ &\exists! \eta: R_1/\ker \psi \overset{\eta}{\cong}_R \psi(R_1), \psi = \eta \phi \end{align*}$$

Theorem 2.3.10: Second isomorphism theorem

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &S \subseteq_R R \\ &I \lhd_R R \\ \hline \\ &\begin{align*} & S+I \subseteq_R R \tag{a}\\ & S \cap I \lhd_R R \tag{b}\\ & (S+I)/I \cong_R S / (S \cap I) \hspace{1cm} \tag{c}\\ \end{align*} \end{align*}$$

Theorem 2.3.11: Third isomorphism theorem

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &I \lhd_R R \\ &J \lhd_R R \\ &J \subseteq I \\ \hline \\ &R/I \cong \frac{R/J}{I/J} \end{align*}$$

Theorem 2.3.12: Correspondence theorem (fourth isomorphism theorem)

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R \\ &I \lhd_R R \\ &\mathfrak S :=\{S: I\subseteq_R S \subseteq_R R\} \\ &\mathfrak S_I :=\{S_I: S_I \subseteq_R R/I\} \\ &\phi: \mathfrak S \to \mathfrak S_I, S \mapsto S/I \\ \hline \\ &\begin{align*} & \phi - \text{well-defined} \tag{a} \\ & \phi^{-1}(S_I) =\{g \in R: g+I \in S_I\} \tag{b}\\ & \phi: \mathfrak S \leftrightarrow \mathfrak S_I \tag{c}\\ &I \subseteq_R S \lhd_R R \implies \phi(S) \lhd_R R / I \hspace{1cm} \tag{d}\\ & S_I \lhd_R R/I \implies \phi^{-1}(S_I) \lhd_R R \hspace{1cm} \tag{e}\\ & S_I \in \mathfrak P_I(R/I) \implies \phi^{-1}(S_I) \in \mathfrak P_I(R) \hspace{1cm} \tag{f}\\ \end{align*} \end{align*}$$

Proof

f.

$$\forall a, b \in R, ab \in \phi^{-1}(S_I): \phi(ab)=\phi(a)\phi(b)=(a+I)(b+I) \in S_I\implies \\ ((a+I) \in S_I)\vee((b+I) \in S_I) \overset{(b)}{\implies} (a \in \phi^{-1}(S_I)) \vee (b \in \phi^{-1}(S_I))$$

$\square$

Proposition 2.3.13: Chinese remainder theorem

$$\begin{align*} &\sphericalangle \\ &R \in \mathcal R^{\mathcal C} \\ &\forall i \in \{1, \ldots, n\}: I_i \lhd_R R \\ &\forall i \ne j: I_i + I_j = R \\ \hline \\ &R / (I_1\ldots I_n) \cong_R R/I_1 \times \ldots \times R/I_n \end{align*}$$

Proof

Let's prove for $n=2$ first.

Consider natural homomorphism $\phi: R \rightsquigarrow R/I_1 \times R/I_2, r \mapsto (r+I_1, r+I_2)$. The kernel of this isomorphism $\ker \phi=I_1 \cap I_2$.

Now let's prove that $I_1I_2 = I_1 \cap I_2$:

$$(2.3.4.d) \implies I_1I_2 \subseteq I_1 \cap I_2$$ $$I_1 + I_2 = R \implies \exists x \in I_1, y \in I_2: x+y = 1 \\ c \in I_1 \cap I_2 \implies c = c(x+y)=cx+cy \in I_1I_2 \\ I_1 \cap I_2 \subseteq I_1I_2$$

Finally, we need to prove that $\phi(R)=R/I_1 \times R/I_2$:

$$I_1 + I_2 = R \implies \exists x \in I_1, y \in I_2: x+y = 1 \\ \phi(x)=(x+I_1, x+I_2) = (I_1, 1-y+I_2)=(I_1,1+I_2) \\ \phi(y)=(y+I_1, y+I_2) = (1-x+I_1, I_2)=(1+I_1,I_2) \\$$ $$b \in R/I_1 \times R/I_2 \implies b = (r_1+I_1, r_2 + I_2) \\ a:=r_2x+r_1y \\ \phi(a)=\phi(r_2)\phi(x)+\phi(r_1)\phi(y)= \\ (r_2+I_1, r_2+I_2)(I_1, 1+I_2)+(r_1+I_1, r_1+I_2)(1+I_1, I_2) = \\ (I_1, r_2+I_2)+(r_1+I_1, I_2)=(r_1+I_1, r_2+I_2) = b$$

So we have $\ker \phi = I_1 \cap I_2 = I_1I_2, \phi(R)=R/I_1 \times R/I_2$, using $(2.3.9)$ we finish the proof for $n=2$.

Now assume we proved the theorem for $k<n$. Define $J:=I_2\ldots I_n$. Let's priove that $I_1+J = R$:

$$\forall i \ge 2: \exists x_i \in I_1, y_i \in I_i: x_i+y_i = 1 \\ 1=(x_2+y_2)\ldots(x_n+y_n) \in I_1+J$$

The last inclusion is because when we open the brackets whenever there's $x_i$ in the factor, it means the whole factor is in $I_1$. The only factor that's left is $y_2\ldots y_n \in J$.

Now we can use the case $n=2$ for $I_1$ and $J$:

$$R/(I_1\ldots I_n)=R/(I_1J)\cong_R R/I_1 \times R/(I_2 \ldots I_n)$$

By induction we decompose $R/(I_2 \ldots I_n)$ and finish the proof

$\square$

Corrolary 2.3.14: Chinese remainder theorem for integers

$$\begin{align*} &\sphericalangle \\ &n_1, \ldots n_k \in \mathbb N \\ &\forall i, j:\gcd(n_i, n_j) = 1 \\ \hline \\ &\Z_{n_1 \cdot \ldots \cdot n_k} \cong_R \Z_{n_1} \times \ldots \times \Z_{n_k} \end{align*}$$

Proof

Define $R:=\Z, I_i := n_i\Z$. Then

$$\gcd(n_i, n_j) = 1 \implies \exists x, y \in \Z: xn_i+yn_j=1 \implies \\ n_i\Z+n_j\Z = \Z \\ I_1\ldots I_k = n_1\ldots n_k\Z$$

By applying $(2.3.13)$ we finish the proof.

$\square$

Exercises

1. Consider a ring $\Z_{12}$:

   a. How many ideals does it have?

   b. How many prime ideals does it have?

   c. How many maximal ideals does it have?

2. Consider a ring $R$ where $\forall r \in R: r^2=r$.

   a. Is it true that $\forall x, y \in R: xy=yx$?

   b. What is $\text{char }R$?

3. Consider two polynomials: $p(x)=x^2+x+1, q(x)=x^3+x+1$

   a. What is $p(x)q(x)$?

   b. What is $p(x)q(x)$ in $\Z_2$?

4. Is $2\Z \cong_R 3\Z$

Practice exercises

1. Let's consider a ring $\mathbb{Z}_n$ where $n = 1000358031641$. We are given a public key $y = 336072790455$. The public key $y$ is derived from a private key $x$ using the congruence relation $3^x \equiv y \pmod{n}$.

   a. How many positive private key values $\leq n$ exists? (1 point)

   b. What is the minimum positive value of the private key? (4 points)

Hint: Use expontiation by squaring algorithm for computing powers of 3.