0
$\begingroup$

In the most common proof of the Chinese remainder Theorem, there is this summation: $x=\sum m_1b_1a_1+m_2b_2a_2$ where $a_i$ is the inverse of $b_i$. I understand that when $i\neq j$, that $m_i\mod{j}$ is congruent to $0$. But even so, how does this summation give us the solution to a system of equations?

Thanks!

$\endgroup$
1
  • $\begingroup$ Nobody knows what your variables mean. And your summation has no index. $\endgroup$ – B. Goddard Mar 23 '18 at 12:19
0
$\begingroup$

One statement of the CRT is that the function

$$f: \mathbb Z_m \to \mathbb Z_{m_1} \oplus \mathbb Z_{m_2} \oplus \cdots \oplus \mathbb Z_{m_N}$$

defined by $f(\overline x) = (\overline x, \overline x, \dots, \overline x)$ is a group isomorphism when the $m_i$ are pairwise prime and their product is $m$. In fact, it's more than that. It's a ring isomorphism. That is

$\text{$(1.) \quad f(\overline x + \overline y) = f(\overline x) + f(\overline y)$}$

$\text{$(2.) \quad f(\overline x \cdot \overline y) = f(\overline x) \cdot f(\overline y)$ where we define}$ $$(\overline{x_1}, \overline{x_2}, \dots, \overline{x_N}) \cdot (\overline{y_1}, \overline{y_2}, \dots, \overline{y_N}) = (\overline{x_1 \cdot y_1}, \overline{x_2 \cdot y_2}, \dots, \overline{x_N\cdot y_N})$$

$\text{$(3.)\quad$ f is one-to-one and onto.}$

Let's assume that this has been proved since you only want to know about where the sum comes from.

Since $f$ is an isomorphism, then $f$ has an inverse function and $f^{-1}$ is also an isomorphism.

Here's where the trick comes in. Let $M = \prod_{i=1}^N m_i$. For $i=1$ to $N$ define $$M_i=\dfrac{M}{m_i}$$. If you think about it, $M_i$ is just the product $m_1m_2m_3 \cdots m_N$ with the $m_i$ removed. Because of this, it should be clear that

$$i \ne j \implies M_j \equiv 0 \pmod{m_i}\tag{1.}$$

It turns out that

\begin{align} \gcd(\{M_i\}_{i=1}^N) &= \gcd \left(\left\{\dfrac{M}{m_i}\right\}_{i=1}^N \right)\\ &= \dfrac{M}{\operatorname{lcm}\left(\left\{\dfrac{M}{m_i}\right\}_{i=1}^N \right)} \\ &= \dfrac MM \\ &= 1 \end{align}

So there must exists integers $\{ \lambda_i \}_{i=1}^N$ such that $$\sum_{i=1}^N \lambda_i M_i = 1$$

For $i$ equals $1$ to $N$, define $u_i \equiv \lambda_iM_i \pmod M$. We know immediately (see equation $(1.)$) that $i \ne j \implies u_j \equiv \lambda_j M_j \equiv 0 \pmod{m_i}$. It follows that $1 \equiv \sum_{j=1}^N \lambda_j M_j \equiv \lambda_i M_i \equiv u_i \pmod{m_i}$. This means that

\begin{align} f(u_1) &= (1,0,0, \dots, 0) \\ f(u_2) &= (0,1,0, \dots, 0) \\ f(u_3) &= (0,0,1, \dots, 0) \\ &\phantom n\vdots \\ f(u_N) &= (0,0,0, \dots, 1) \\ \end{align}

Because $f$ is a bijection, that means that, for all $1 \le i \ne j \le N$, $u_i^2 \equiv u_i \pmod m$ and $ui \cdot u_j \equiv 0 \pmod m$.

Clearly $\displaystyle (\overline{x_1}, \overline{x_2}, \dots, \overline{x_N}) = \sum_{i=1}^N x_i f(u_i)=\sum_{i=1}^N f(x_i \cdot u_i)$

$\endgroup$

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.