Chinese remainder theorem and the value of moduli

126 Views Asked by At

When we prove the Chinese Remainder Theorem, we construct for the system of linear congruences $$ x \equiv a_1 \mod m_1,\; ... \;,x \equiv a_n \mod m_n$$ we have : $$M_k = \frac{m}{m_k} $$ where m = $m_1.m_2...m_n$ and we construct $x=a_1M_1y_1+...+a_nM_ny_n$, where all $y_k$ are inverse of respective $M_k$ in $m_k$ modulo world.

Now, I get why this construction is being done for a simultaneous solution, but, there's a confusion of how m is obtained.

My reasoning is as: if $x\equiv y\mod\ m$ is not the same as $x\equiv y\mod\ m_k$ for all positive integers $k$. then, why is x obtained in a $\mod m$ world? where $m = m_1.m_2...m_n$ why is $x$ in LCM of all the moduli? i.e. why is $x \equiv a_1M_1y_1+...+a_nM_ny_n \mod m$?

1

There are 1 best solutions below

0
On

I don't want to drown you in a sea of notation. So I will show you a detailed example and let you work out the general case for yourself.

Note that $5400 = 2^3 \times 5^2 \times 3^3$. So, according to the CRT, there exists an isomorphism $$f : \mathbb Z_{5400} \to \mathbb Z_8 \oplus \mathbb Z_{25} \oplus \mathbb Z_{27}$$.

The whole idea is that, if $f(x)=(x_1,x_2,x_3)$, then we should expect that

\begin{align} x &\equiv x_1 \pmod {\phantom{2}8} \\ x &\equiv x_2 \pmod {25} \\ x &\equiv x_3 \pmod {27} \end{align}

This suggest the interesting identity $f(x)=(x,x,x)$; which makes it very easy to prove that $f$ is a homomorphism. Because $|\mathbb Z_{5400}| = |\mathbb Z_8 \oplus \mathbb Z_{25} \oplus \mathbb Z_{27}| = 5400$, we need only show that $f$ is one-to-one or onto in order to prove that $f$ is bijective, and hence an isomorphism.

Let's try to show that $f$ is onto. We define \begin{align} e_1 &= (1,0,0) \\ e_2 &= (0,1,0) \\ e_3 &= (0,0,1) \end{align}

Then $(x_1, x_2, x_3) = x_1e_1+x_2e_2+x_3e_3$. If we could find $m_1, m_2,m_3 \in \mathbb Z_{5400}$ such that

\begin{align} f(m_1) &= e_1 \\ f(m_2) &= e_2 \\ f(m_3) &= e_3 \end{align}

Now we finally get down to your question. How do we find the values of the $m_is$?

First $m_1$ must satisfy

\begin{align} m_1 &\equiv 1 \pmod {\phantom{2}8} \\ m_1 &\equiv 0 \pmod {25} \\ m_1 &\equiv 0 \pmod {27} \end{align}

If we let $m_1 \equiv 25 \cdot 27 \cdot \alpha \equiv \left(\dfrac{5400}{8}\right) \alpha \equiv 675 \alpha \pmod{5400}$,

then we see immediately that $m_1 \equiv 0 \pmod {25}$ and $m_1 \equiv 0 \pmod {27}$. We still need to make one more equivalence true.

\begin{align} m_1 &\equiv 1 \pmod 8 \\ 675\alpha &\equiv 1 \pmod 8 \\ 3\alpha &\equiv 1 \pmod 8 \\ \alpha &\equiv 3 \pmod 8 \\ \hline m_1 &\equiv 3\cdot 675 \pmod{5400} \\ m_1 &\equiv 2025 \pmod{5400} \end{align}

Next we let $m_2 \equiv 8 \cdot 27 \cdot \alpha \equiv \left(\dfrac{5400}{25}\right) \alpha \equiv 216 \alpha \pmod{5400}$

So $m_2 \equiv 0 \pmod {8}$ and $m_2 \equiv 0 \pmod {27}$.

\begin{align} m_2 &\equiv 1 \pmod{25} \\ 216\alpha &\equiv 1 \pmod{25} \\ 16\alpha &\equiv 1 \pmod{25}\\ \alpha &\equiv 11 \pmod 8 \\ \hline m_2 &\equiv 216\cdot 11 \pmod{5400} \\ m_2 &\equiv 2376 \pmod{5400} \end{align}

Finally, we let $m_3 \equiv 8 \cdot 25 \cdot \alpha \equiv \left(\dfrac{5400}{27}\right) \alpha \equiv 200 \alpha \pmod{5400}$

So $m_3 \equiv 0 \pmod {8}$ and $m_2 \equiv 0 \pmod {25}$.

\begin{align} m_3 &\equiv 1 \pmod{27} \\ 200\alpha &\equiv 1 \pmod{27} \\ 11\alpha &\equiv 1 \pmod{27}\\ \alpha &\equiv 5 \pmod{27} \\ \hline m_3 &\equiv 200\cdot 5 \pmod{5400} \\ m_3 &\equiv 1000 \pmod{5400} \end{align}

We have not only shown now that $f$ is onto, we have also shown that $$f^{-1}(x,y,z) \equiv 2025x + 2376y + 1000z \pmod{5400}$$

This should be enough information to see what is required of a real proof of CRT. Can you see why it was necessary for $8, 25$, and $27$ to be pairwise prime?