1
$\begingroup$

The Chinese Remainder Theorem can be stated in a few ways:

(i) If $N = N_1N_2\cdots N_k$ and the $N_i$ are pairwise coprime we have a canonical isomorphism $$\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/N_1\mathbb{Z} \oplus \cdots \oplus \mathbb{Z}/N_k\mathbb{Z}$$ (ii) For any $a_i \bmod N_i, \quad i = 1,\ldots, k$ there exists an $a$ such that $a \equiv a_i \bmod N_i$ for all $i$.

My question is how are these definitions equivalent and how is the isomorphism in the first definition true?

Also, the value of $a$ can be found via the Euclidean Algorithm. That is, put $M_i = N/N_i$. By assumption $M_i$ and $N_i$ are relatively prime. Then find $X_i$ with $X_iM_i \equiv 1 \bmod N_i$ and put $$a = \sum_{i=1}^k a_iX_iM_i$$

I am also confused how this uses the euclidean algorithm and finds the value of $a$.

$\endgroup$
0
$\begingroup$

Very simple if you observe $M_i\equiv 0\mod N_j$ for all $j\ne i$. So this value for $a$ satisfies $$a\bmod N_j =\sum_{i+1}^k (a_i X_iM_i \bmod N_j)=a_jX_jM_j\bmod N_j=a_j\bmod N_j.$$

Finding the inverse $X_i$ of $M_i$ modulo $N_i$ is done through the Extended Euclidean algorithm, which yields the coefficients $X_i$ and $Y_i$ of a Bézout's relation between $M_i$ and $N_i$: $$X_iM_i+Y_iN_i=1.$$My answer to this question shows how it works in practice.

Why the isomorphism?

There's a natural map: \begin{align*} \varphi\colon \mathbf Z&\longrightarrow \mathbf Z/N_1\mathbf Z\times\dots\times\mathbf Z/N_k\mathbf Z\\x&\longmapsto(x\bmod N_1,\dots, x\bmod N_k)\end{align*} and its kernel is $N_1\mathbf Z\cap\dots\cap N_k\mathbf Z=N\mathbf Z\;$ because the $N_i$s are pairwise coprime. So we have an injective map $$\overline\varphi\colon \mathbf Z/N\mathbf Z\longrightarrow \mathbf Z/N_1\mathbf Z\times\dots\times \mathbf Z/N_k\mathbf Z.$$ Now, condition (ii) says $\varphi$, hence $\overline \varphi$, is surjective, hence an isomorphism.

$\endgroup$
  • $\begingroup$ I don't get why $a\bmod N_j =\sum_{i+1}^k (a_i X_iM_i \bmod N_j)$. $\endgroup$ – user19405892 Apr 18 '16 at 17:35
  • $\begingroup$ Because reduction mod $N_j$ is a group homomorphism; i.e. it is compatible with addition. $\endgroup$ – Bernard Apr 18 '16 at 17:40
  • $\begingroup$ Can any real number $N$ be written in the form $N = N_1N_2\cdots N_k$ where the $N_i$ are pairwise coprime? $\endgroup$ – user19405892 Apr 18 '16 at 17:53
  • $\begingroup$ You mean any natural number, I suppose. Why, yes. $\endgroup$ – Bernard Apr 18 '16 at 18:02
  • $\begingroup$ Yes, I mean natural number sorry. Why is that? $\endgroup$ – user19405892 Apr 18 '16 at 18:26
0
$\begingroup$

To get a decent proof, we need to be a bit more formal.

Suppose $N_0 = \prod_{i=1}^k N_i$ where the $N_i$ are pairwise coprime.

Notationally, we will define $a..b$ to be the set $\{a, a+1, a+2, \dots, b\}$

Define $[n]_i = \{x \in \mathbb Z : x \equiv n \pmod{N_i} \}$. Then $\mathbb{Z}_{N_i} = \{ [n]_i : n \in \mathbb Z\}$.

Theorem. Define $f:\mathbb{Z}_{N_0} \to \bigoplus_{i=1}^k \mathbb{Z}_{N_i}$ by $f([x]_0) = ([x]_1, [x]_2, \dots, [x]_k)$. Then $f$ is an isomorphism.

Proof.

The proof that $f$ is a well-defined homomorphism can be found in just about any good group theory text. We will skip that because I am too lazy to type the whole thing out.

For $i = 1..k$, define $e_k \in \prod_{i=1}^k N_i$ by
$e_1 = ([1]_1, [0]_2, \dots, [0]_k)$
$e_2 = ([0]_1, [1]_2, \dots, [0]_k)$
$\phantom{e_8}\;\;\vdots$
$e_k = ([0]_1, [0]_2, \dots, [1]_k)$

We will show that, for $i \in 1..k$, there exists an $m_i \in \mathbb Z$ such that $f([m_i]_0) = e_i$.

We start by defining $M_1 = \dfrac{N_0}{N_1}$ Note that, for $i \in 2..k$, $M_i \equiv 0 \pmod{N_i}$. This means that $f([M_1]_0) = ([M_1]_1, [0]_2, \dots, [0]_k)$.

Also, since the $N_i$ are relatively prime, $\gcd(M_1,N_1) = 1$. So there exists an $X_1 \in \mathbb Z$ such that $X_1 M_1 \equiv 1 \pmod{N_1}$. Let $m_1 = X_1 M_1$. It follows that $f([m_1]_0) = ([1]_1, [0]_2, \dots, [0]_k)$.

Using the same reasoning but changing the things that need to be changed, it follows that for $i \in 1..k$, there exists an $m_i \in \mathbb Z$ such that $f([m_i]_0) = e_i$.

Now it's pretty easy to show that $f$ is onto. Let $([a_1]_1, [a_2]_2, \dots, [a_k]_k) \in \bigoplus_{i=1}^k \mathbb{Z}_{N_i}$. Define $a = a_1 m_1 + a_2 m_2 + \cdots + a_k m_k$. Because $f$ is a homomorphism,

\begin{align} f([a]_0) &= f\left( \left[\sum_{i=1}^k a_i m_i \right]_0 \right) \\ &= \sum_{i=1}^k f\left( [a_i m_i]_0 \right) \\ &= \sum_{i=1}^k a_i f\left([m_i]_0 \right) \\ &= \sum_{i=1}^k a_i e_i \\ &= ([a_1]_1, [a_2]_2, \dots, [a_k]_k) \end{align}

So $f$ is onto. Since $|\mathbb Z_{N_0}| = |\bigoplus_{i=1}^k \mathbb{Z}_{N_i}| = N_0$. It follows that $f$ must also be one-to-one.

$\endgroup$
-1
$\begingroup$

If, for a prime $p$, $p^{\alpha_i}|m_i$, with $\alpha_i$ being the largest exponent with that property, then $p^{\alpha}|\operatorname{lcm}(m_1,m_2,\dots,m_k)$, where $\alpha=\max\{\alpha_i\}$. Similarly, the greatest common divisor of several numbers is the product of the largest powers of the primes that divide all the given numbers.

Associativity allows one to proceed a step at a time with an inductive argument without putting all eggs into a basket at once. Jumping at the opportunity I'll prove the most basic case of $k=2$.

Theorem 1 : Two simultaneous congruences $$\left\{\begin{array}{cccc}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 & (\mod m_2)\end{array}\right.$$ are only solvable when $n_1\equiv n_2 \ (\mod gcd(m_1,m_2))$. The solution is unique modulo $lcm(m_1,m_2)$. (When $m_1$ and $m_2$ are coprime their gcd is $1$. By convention, $a\equiv b\ (\mod 1)$ holds for any integers $a$ and $b$.)

Proof: By a generalization of Euclid's algorithm, there are integers $s$ and $t$ such that $$tm_1+sm_2=gcd(m_1,m_2).$$ Since $n_2−n_1\equiv 0 \ (\mod gcd(m_1,m_2))$, for some $t'$ and $s'$, $$t'm_1+s'm_2=n_2−n_1.$$ Then $n=t'm_1+n_1=−s'm_2+n_2$ satisfies both congruences in the theorem. This proves the existence of a solution.

To prove the uniqueness part, assume $n$ and $N$ satisfy the two congruences. Taking the differences we see that $N−n\equiv 0 \ (\mod m1)$ and $N−n\equiv 0\ (\mod m_2)$, which implies $N−n\equiv 0 \ (\mod lcm(m_1,m_2))$.

As was previously stated, a more general theorem can now be proved by induction.

Theorem 2 : The simultaneous congruences $$\left\{\begin{array}{cccc}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 & (\mod m_2) \\ & & \vdots & \\ n & \equiv & n_k & (\mod m_k)\end{array}\right.$$ are only solvable when $n_i=n_j \ (\mod gcd(m_i,m_j))$, for all $i$ and $j$, $i\neq j$. The solution is unique $\mod lcm(m_1,m_2,\dots,m_k)$.

Proof : Theorem 1 serves the initial step verification. Assume the theorem holds for $k$ congruences and consider $k+1$ of them.

$$\left\{\begin{array}{cccc}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 & (\mod m_2) \\ & & \vdots & \\ n & \equiv & n_k & (\mod m_k) \\ n & \equiv & n_{k+1} & (\mod m_{k+1})\end{array}\right.$$

Let $s$ be a solution of the first $k$ equations. Then the congruence $n\equiv s \ (\ mod lcm(m_1,m_2,\dots,m_k))$ has a solution. (Observe that every solution of the latter also satisfies the first $k$ congruences.) To be able to apply the already proven Theorem 1, we need to show that $$s\equiv n_k+1 (mod gcd(lcm(m_1,\dots,m_k),m_{k+1})).$$ Let's write $g_u=gcd(m_,m_{k+1})$, $u=1,\dots,k$. Then we know that $n_u \equiv n_{k+1}\ (\mod g_u)$ for these values of u. But $n_u=s+t_um_u$, for some $t_u$, implying $n_{k+1}=s+t_um_u\ (\mod g_u)$ so that

$$s=n_{k+1} \ (\mod g_u), u=1,2,\dots ,k.$$

If so,

\begin{align} s & \equiv n_{k+1} \ (\mod lcm(g_1,\dots,g_k))\\ & \equiv n_{k+1}\ (\mod lcm(gcd(m_1,m_{k+1}),\dots ,gcd(m_k,m_{k+1}))) \\ & \equiv n_{k+1}\ (\mod gcd(lcm(m1,…,mk),mk+1)),\end{align}

because $lcm(gcd(m_1,m_{k+1}), \dots,gcd(m_k,m_{k+1})) =gcd(lcm(m_1,\dots,m_k),m_{k+1})$. Thus the system

$$\left\{\begin{array}{cccl}n & \equiv & s & (\mod lcm(m_1,m_2,\dots,m_k)) \\ n & \equiv & n_{k+1} & (\mod m_{k+1})\end{array}\right.$$

has a solution which is unique modulo $lcm(lcm(m_1,m_2,\dots,m_k),m_{k+1})=lcm(m_1,m_2,\dots,m_k,m_{k+1})$.

It also satisfies the whole set of $k+1$ congruences.

Corollary : The simultaneous congruences $$\left\{\begin{array}{cccl}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 & (\mod m_2) \\ & & \vdots & \\ n & \equiv & n_k & (\mod m_k)\end{array}\right.$$ where all $m_i$'s are pairwise coprime has a unique solution modulo $m_1\cdot m2\cdots m_k$.

If some $m_i$'s are not mutually prime, a solution may not exist unless the corresponding congruences agree. For example, the system

$$\left\{\begin{array}{cccc}n & \equiv & 1 & (\mod 2) \\ n & \equiv & 2 & (\mod 4) \end{array}\right.$$ has no solutions, while the system

$$\left\{\begin{array}{cccc}n & \equiv & 1 & (\mod 2) \\ n & \equiv & \pm 1 & (\mod 4)\end{array}\right.$$ does.

$\endgroup$
  • 1
    $\begingroup$ Please, typeset correctly this post, for it is quite hard to read. Moreover, it seems to contain the typical issues that arise when someone copy-pastes the output of a latex document in plain text. $\endgroup$ – user228113 Apr 27 '16 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.