Algorithm for solving system of congruences

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.

1 Answer

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