Chinese Remainder Theorem

Beschreibung

The Chinese Remainder Theorem describes conditions under which a Kongruenz (Ring) can be split into multiple independent congruences.

Since this is a very old theorem, there are multiple versions floating around.

Definition (General Definition)

Let $R$ be a Ring and let ${\mathfrak{a}}_1,{\mathfrak{a}}_2,...,{\mathfrak{a}}_r$ be ideals with ${\mathfrak{a}}_i+{\mathfrak{a}}_j=R$ for any two different $i,j$. Then, the following map is a ring isomorphism

a + \bigcap_{i=1}^{n} \frak{a}_{i} &\mapsto (a + {\frak{a}_{1}}, ..., a + \frak{a}_n)\end{align}$$

On $\mathbb{Z}$, this becomes slightly simpler.

Definition (Definition on $\mathbb{Z}$)

We want to find a number which is congruent to numbers $a_1,a_2,...,a_r$ modulo $n_1,n_2,...,n_r$, where $n_1,n_2,...,n_r$ are pairwise coprime integers. (i.e. $ggT(n_1,n_2,...,n_r)=1$) We write:

\vdots\ x &\equiv a_r \mod n_r\end{align}$$

The theorem states that all solutions are congruent to $n=n_1\cdot ...\cdot n_r$. Finding one solution then gives all the others.

Definition (For cyclic groups)

Let $m,n\in \mathbb{N}$ be coprime, then we have the following groups isomorphism $\mathbb{Z}/(mn)\mathbb{Z}\cong \mathbb{Z}/(m)\mathbb{Z}\times \mathbb{Z}/(n)\mathbb{Z}$ The converse is also true

Above we required coprime congruences. If those are not given, the solution might not necessarily exist.

Requirement for existence of solution

Let $m,n\in \mathbb{N}$ and $a,b\in \mathbb{Z}$. We examine the solutions $\mathcal{L}\subseteq \mathbb{Z}$ of $x\equiv a\mathrm{mod}n,x\equiv b\mathrm{mod}n$

1. A solution exists exactly if $a\equiv b\mathrm{mod}d$, where $d=ggT(m,n)$
2. Let $l\in \mathbb{Z}$ where $b=a+ld$ and $m^{\prime }=m/d$, $n^{\prime }=n/d$. If $c$ is a solution of $x\equiv 0\mathrm{mod}{m}^{\prime },x\equiv l\mathrm{mod}{n}^{\prime }$. Then the solution set of the original problem is given be $\mathcal{L}=a+dc+lcm(m,n)\mathbb{Z}$