Exercise 3.22

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Formulate and prove the Chinese Remainder Theorem in a principal ideal domain.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

{\bf Proposition}. Let $R$ a principal ideal domain, and $m_1,\ldots,m_t \in R$. Suppose that $(m_i,m_j) = 1$ for $i
eq j$ (that is $(m_i) + (m_j) = (1), m_iR +n_i R = R$). Let $b_1,\ldots,b_t \in R$ and consider the system of congruences:
$$x \equiv b_1 \pmod {m_1}, x \equiv b_2 \pmod {m_2},\ldots, x \equiv b_t \pmod {m_t}.$$
This system has solutions and any two solutions differ by a multiple of $m_1m_2\cdots m_t$.
\begin{proof} 
Let $m = m_1m_2\cdots m_t$, and $n_i =m/m_i,\ i=1,2,\ldots,t$.

As $(m_1,m_i)=(1)$, we can find $u_i,v_i \in R$ such that $m_1u_i+m_iv_i= 1$ for $i=2,\ldots,t$.

Therefore $1 = \prod\limits_{i=2}^t(m_1u_i+m_iv_i ) = m_1 u +(m_2\cdots m_t)v$ for some elements $u,v \in R$, thus $(m_1,n_1) = (m_1,m_2m_3\cdots m_t) = (1)$, and similarly $(m_i,n_i)=1$ for all $i =1,\ldots,t$. So there are $r_i,s_i \in R$ such that $r_im_i+s_in_i = 1$. Let $e_i = s_in_i$. Then $e_i \equiv 1 \pmod{m_i}$ and $e_i \equiv 0 \pmod{m_j}$ for $j
eq i$.

Set $x_0 =\sum_{i=1}^t b_ie_i$. Then we have $x_0 \equiv b_i e_i \equiv b_i \pmod{m_i}$ and so $x_0$ is a solution.

Suppose that $x_1$ is another solution. Then $x_1 -x_0 \equiv 0 \pmod{m_i}$ for $i=1,2,\ldots,t$, in other words $m_1,m_2,\ldots,m_t$ divide $x_1-x_0$, with $(m_i,m_j)=1$. By the generalization of Lemma 2 to principal rings, $m$ divides $x_1-x_0$.
\end{proof}

\bigskip

This result can be generalized to any commutative ring, not necessarily a PID (see S.LANG, Algebra):

{\bf Proposition}. Let $A$ a commutative ring. Let ${	extfrak a}_1,\ldots, {	extfrak a}_n$ be ideals of $A$ such that ${	extfrak a}_i+{	extfrak a}_j = A$ for all $i
eq j$. Given elements $x_1,\ldots,x_n \in A$, there exists $x\in A$ such that $x\equiv x_i \pmod {{	extfrak a}_i}$ for all $i$.

Exercise 3.22

Answers

Comments

Exercise 3.22

Answers

Comments

Add answer