0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.