Reconstruction of Chinese Remainder Theorem without modulo reduction?

82 Views Asked by At

Let $a$ be an integer modulo $X = \prod_{i=0}^{k-1}x_i $ where each of $x_i \in \mathbb{Z}$ and for any pair of $i$ and $j$, $x_i$ and $x_j$ are coprime.

Now, using Chinese Remainder Theorem, $a$ is represented by a set of integers ($a_1, a_2, \ldots, a_{k-1}$) for $a_i \in \mathbb{Z}_{x_i}$.

With that representation, $a$ is reconstructed by

$$ a = \sum_{i=0}^{k-1}(a_i \cdot ((\frac{X}{\prod_{j\neq i}a_j})^{-1} \mod x_i)\cdot (\frac{X}{\prod_{j\neq i}a_j})) \mod X. $$

What is the value of the sum before modulo $X$?

I guess that is $a + kX$ for some $k$. What's the bound of $k$?