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

Question

Please don't mark it as duplicate. First read the whole question.
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?

Answer 1

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.

Answer 2

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.)

Answer 3

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.