# Problem in proof of Chinese remainder theorem, and applying it.

So Chinese Remainder Theorem states that,:
Let $n_1,n_2,...,n_k$ be $k$ positive integers which are pairwise relatively prime. If $a_1,a_2,...,a_k$ are such that $(a_j,n_j)=1$ for $j=1,2,...k$ then the congruences $$a_1x \equiv b_1(\mod n_1),a_2x \equiv b_2(\mod n_2),...,a_kx \equiv b_k(\mod n_k)$$
have a common solution which is unique modulo $[n_1,n_2,...n_k]$.
PROOF: Consider $a_jx \equiv b_j(\mod n_j)$. Since, $(a_j,n_j)=1$, we always have a solution for $a_jx \equiv b_j(\mod n_j)$ whatever be $b_j$. $(1)$
Choose a solution $C_j$ for $a_jx \equiv b_j(\mod n_j)$ for $j=1,2,...,k$. We have $[n_1,...,n_k]=n_1..n_k$ since they all are co-prime. Call this number $M$. If $m_j=\frac M{n_j}$ we see that $(m_j,n_j)=1$ Solving $m_jx\equiv 1(\mod n_j)$ we have a unique solution $x\equiv m_j'(\mod n_j)$. $(2)$
Wherever I have marked a number $(1)$ or $(2)$, I didn't understand the step.
Also, I didn't understand the steps that are taken from now onwards.
This gives $m_jm_j' \equiv 1(\mod n_j)$. Take $x_0=c_1m_1m_1'+c_2m_2m_2'+...+c_km_km_k'.$ For $i\neq j$, $n_i$ divides $m_j=\frac{n_1n_2...n_k}{n_j}$. Therefore $$a_jx_0=\sum\limits_{i=1}^{k}a_ic_im_im_i'\equiv a_jc_jm_jm_j' (\mod n_j)$$
$$\equiv a_jc_j(\mod n_j)$$ since $m_jm_j' \equiv 1(\mod n_j)$
$$\equiv b_j(\mod n_j)$$ for $j=1,2,...,k$.
Thus, $x_0$ is a common solution to our system of congruences. If $x$ is any other solution of the same system then $x_0 \equiv c_j \equiv x(\mod n_j)$. This means that $x_0-x$ is a common multiple of $n_1,n_2,...,n_k$ and hence $x_0-x$ is a multiple of $[n_1,n_2,...,n_k]=M$. Therefore $x\equiv x_0(\mod [n_1,...,n_k])$

Now what does the writer mean by $m_j'$? Where did the $'$ come from?

Also, how to apply it, like in this example: There are $x$ eggs in a basket.
If counted in pairs, $1$ remains.
If counted in groups of three, $2$ remain.
If in groups of four, $3$ remain.
If in groups of five, $4$ remain.
If in groups of six, $5$ remain.
If in groups of seven, $0$ remain. So find $x$.

I made the congruences easily, but how to use CRT here?

• Do you know how to combine congruences? For example, the first 2 congruences given would form x being congruent to 5 mod 6. Jul 15, 2015 at 16:53
• I know, but I don't know even the basics of application of CRT. Jul 16, 2015 at 8:12

Here

we have a unique solution $x\equiv m_j(\mod n_j)$. $(2)$

it should say instead $x\equiv m_j'(\mod n_j)$. The $m_j'$ is the solution of $m_jx\equiv 1(\mod n_j)$. To use the notation $m_j'$ is somewhat common, but it is not crucial either. You could just as well say let $u_j$ be the solution of $m_jx\equiv 1(\mod n_j)$, and then write $u_j$ wherever you have $m_j'$.

For you specific question to apply CRT in the form you quote there, you need to work on the congruences a bit to have co-prime moduli, or you use a version of CRT that allows for non co-prime moduli.

• What is $m_j'$? Jul 16, 2015 at 8:12

To clear up your first bit of misunderstanding: the sentence

"Solving $m_j x \equiv 1(\bmod n_j)$ we have a unique solution $x \equiv m_j (\bmod n_j).$"

should be

"Solving $m_j x \equiv 1(\bmod n_j)$ we have a unique solution $x \equiv m_j' (\bmod n_j).$"

(Note the addition of the "prime" on the last $m_j$.)

That makes the rest of the proof more readable, I believe. The point is that $m_j'$ is the multiplicative inverse of $m_j$, at least mod $n_i$.

As for the second, you need not to use the theorem, but its proof, which is constructive: it tells you how to find $x$. (Actually, things a little subtle, since the theorem involves pairwise relatively prime integers, but 2, 4, 6 are not pairwise relatively prime.)

• Okay, but won't the multiplicative inverse be a fraction? And I solved the problem without theorem. Just by modular congruences. The answer is $119$. But how to apply the theorem to solve it? Jul 15, 2015 at 16:23
• And I don't think that it is the multiplicative inverse. Because their product is not $1$. Jul 15, 2015 at 16:27
• It's the multiplicative inverse in the semi-group (or monoid) of integers mod $n_j$. If you've not studied group theory, you can safely ignore that statement and any mention of the multiplicative inverse. Jul 15, 2015 at 17:34

Taking the second part here:

Also, how to apply it, like in this example: There are x eggs in a basket.

If counted in pairs, 1 remains. If counted in groups of three, 2 remain. If in groups of four, 3 remain. If in groups of five, 4 remain. If in groups of six, 5 remain. If in groups of seven, 0 remain. So find x.

The first couple of these are unnecessary as some of the later congruences will take this over. For example, the first pair of congruences are noted in the solution of 5 remaining in groups of 6. Thus, there is the need to only work with the last 4 lines.

Now, taking the last pair, consider multiples of 7 under mod 6 to find which produces the remainder of 5.

Multiples of 7: 7, 14, 21, 28, 35, 42

Mod 6: 1, 2, 3, 4, 5, 0

35 mod 42 would be that part in terms of fulfilling those lines.

Now, to add the 4 mod 5 to this, note that 42 mod 5 is 2 and thus add $2*42=84$ giving 119 mod 210 as the next level here.

Last, there is the check for 3 mod 4 here which that congruence does satisfy.