How do you use the Chinese Remainder Theorem?

111 Views Asked by At

I know that the theorem is

$$x \equiv b_1\pmod {m_1}$$ $$x \equiv b_2\pmod {m_2}$$ $$x \equiv b_3\pmod {m_3}$$ $$\cdot\quad\cdot\quad\cdot$$ $$x \equiv b_k\pmod {m_k}$$ has a unque solution modulo $m_1m_2...m_k$

but I don't know how to use it. I can multiply the $m$'s together, but what do I do after that? How do I know what to multiply the whole expression by?

2

There are 2 best solutions below

0
On BEST ANSWER

We also need to suppose that $\gcd (m_1,\ldots, m_k) = 1$, otherwise the theorem does not hold.

For each $i = 1,\ldots,k$, let us define $n_i = \frac {m_1\cdots m_k}{m_i}$. Note that $\gcd (n_i, m_i) = 1$, because $\gcd (m_j,m_i) = 1, \forall j \neq i$. Let $\alpha_i$ be the inverse of $n_i$ modulo $m_i$, i. e., $\alpha_i$ is such that $\alpha_i n_i + \beta_i m_i = 1$, for some $\beta_i$.

Fact: $x_0 = b_1\alpha_1 n_1 + \cdots + b_k\alpha_k n_k$ is solution to the system.

Indeed, notice that if $j \neq i$, $n_j \equiv 0 \pmod{m_i}$ and, therefore, $$x_0 \equiv b_i\alpha_i n_i + \sum_{\substack{j = 1\\j \neq i}}^k b_j\alpha_j n_j \equiv b_i (\alpha_i n_i) + 0\equiv b_i1 \equiv b_i\pmod{m_i}.$$

Since the solution is unique modulo $m_1\cdots m_k$, we have that all solutions are of the form $$x = x_0 + k(m_1\cdots m_k), \quad k \in \mathbb{Z}.$$

2
On

You may also use it in its other form: Znm~Zn×Zm if and only if (m,n)=1. (also working for more than two numbers)