Algorithm for solving system of congruences

Question

I'm trying to understand an algorithm shown in my textbook for solving a system of congruences. The problem states:

Let $r$ and $m$ be arrays of size $n$, such that every two numbers (modulos) from $m$ are coprime. Find $x$ such that

$$x \bmod m_0=r_0\\x \bmod m_1=r_1\\...\\x \bmod m_{n-1}=r_{n-1}$$

So yeah, the classic congruence system problem. The naiive approach is shown first and then comes this:

Let $M = m_0 \cdot m_1 \cdot ... \cdot m_{n-1}$. Let's assume we can find the numbers $w_0, w_1, ...w_{n-1}$ such that $w_i \bmod m_i = 1$ and $w_i \bmod m_j = 0$ for $i \neq j$. So we're finding numbers $w_j$ such that it is divisible by every number except for $m_j$ where the remainder is $1$. Then the solution x can be constructed as: $$x = r_0\cdot w_0 + r_1\cdot w_1 + ...+r_{n-1}\cdot w_{n-1} (\bmod M)$$

Well I guess my question is simply - why? I can't seem to reason this out. It seems to me that $x$ is always going to be zero. If we take the sum given above and break it up into sums $$(r_0\cdot w_0)\bmod M + (r_1\cdot w_1)\bmod M + ...$$

it seems like everything should be zero? Let's take the first expression $(r_0 \cdot w_0) \bmod M$. We've got $r_0$ times something that's a multiple of every $m$ except for $m_0$ (because of the way the numbers $w$ were defined), meaning that whole thing will be a multiple of every $m$ except for $m_0$. And then we're taking a modulo $M$ which is also a multiple of every $m$.

How does this give us a solution? The textbook is pretty vague about this and doesn't explain why it works this way. So, any ideas?

Thanks.

Answer 1

It is often less confusing to refrain from using congruences and simply write what it means in extension. I.e. when the textbook says to take an $x$ which is equal modulo $M$ to $r_0\cdot w_0 + \dots + r_{n-1}\cdot w_{n-1}$, it means that any $x$ of the form $x=r_0\cdot w_0 + \dots + r_{n-1}\cdot w_{n-1} + k\dot M$, with $k\in \mathbb{Z}$, is a solution. Under this form it should be clearer that $x$ is indeed a solution since $\forall i\in \mathbb{N}_n,x\equiv_{(m_i)}r_i\cdot w_i + \sum_{j\neq i}r_j\cdot w_j+ k\cdot M\equiv_{(m_i)}r_i$ (as $m_i|M$, $w_i\equiv_{(m_i)}1$, and for $j\neq i$ $m_i|w_j$).