Chinese Remainder Theorem - unclear step in algorithm

Question

I have a question regarding the CRT. There's one step in the algorithm that I don't understand, and I couldn't find the explanation anywhere.

I'll give an example question and point out which part confuses me.

Let's look at this system of linear congruences:

$x\equiv1\ (mod\ 41)$

$x\equiv2\ (mod\ 42)$

$x\equiv3\ (mod\ 43)$.

Now, we start solving the system and we get this:

$42\cdot43\cdot x_{1}\equiv1 \ (mod\ 41)$

$41\cdot43\cdot x_{2}\equiv2 \ (mod\ 42)$

$41\cdot42\cdot x_{3}\equiv3 \ (mod\ 43)$.

The next step is to simplify the congruences above and this is the part that confuses me. For example, we can simplify $42\cdot43\cdot x_{1}\equiv1 \ (mod\ 41)$ to $2\cdot x_{1}\equiv1 \ (mod\ 41)$.

I know how we get $2\cdot x_{1}$, but I don't know why we're allowed to do this.

From what I understand, the congruence $42\cdot43\cdot x_{1}\equiv1 \ (mod\ 41)$ means $41|(42\cdot43\cdot x_{1} - 1)$. How can we just reduce one of the coefficients? Is there maybe a theorem that explains why this is alright? I've looked in my textbook but couldn't find any.

Answer 1

You don't need a special theorem for that. Just look at $$ 42 \cdot 43 \cdot x_1 - 1 = (41+1) \cdot (41+2) \cdot x_1 -1 = 41^2 \cdot x_1 +41 \cdot 2 \cdot x_1 + 1 \cdot 41 \cdot x_1 + 2 \cdot x_1 -1. $$ In the sum on the RHS the first three terms are divisible by $41$. Hence, the term on the LHS is divisible by $41$ iff it is $2x_1-1$.

Answer 2

In general, if $a\equiv b \ (mod\ n)$ then $a\cdot c \equiv b \cdot c\ (mod\ n)$.
This is because $$a\equiv b \ (mod\ n) \Leftrightarrow \\n|a-b \Rightarrow \\n|(a-b) \cdot c \Leftrightarrow \\ n|a \cdot c - b \cdot c \Leftrightarrow \\a \cdot c \equiv b \cdot c \ (mod \ n)$$ Apply this twice on your problem using the fact that $42 \equiv 1 \ (mod \ 41)$ and $43 \equiv 2 \ (mod \ 41)$ and you get $42 \cdot 43 \cdot x_1 \equiv 1 \cdot 2 \cdot x_1 \equiv 2 \cdot x_1 \ (mod \ 41)$.