extension of CRT from $k$ primes to $n$ primes

Question

Let $1 \leq k \leq n$ be integers and let $p_1 <\dots< p_n$ be $n$ distinct primes.

We denote $N=\prod\limits_{i=1}^n p_i$ and $K=\prod\limits_{i=1}^kp_i$.

We Consider the mapping $E:\mathbb{Z}_K\to \mathbb{Z}_{p_1}\times\cdots \mathbb{Z}_{p_n}$ defined by: $$E(m)=(m \ \text{mod} \ p_1,\dots,m \ \text{mod}\ p_n)$$

Let $m_1\neq m_2$ be two distinct members of $\mathbb{Z}_K$ and define: $$\forall\ i\in[n] : b_i = \begin{cases} 1 & \text{if}:\ E(m_1)_i\neq E(m_2)_i \\ 0 & \text{if}:\ E(m_1)_i=E(m_2)_i \\ \end{cases} $$ Prove that $\prod\limits_{i=1}^n p_i^{b_i}>N/K$.

Important Note: As I talk about the domain $\mathbb{Z}_K$ I talk about the set of numbers $S=\{0,1,2,\dots,K-1\}$ not about the group $(\mathbb{Z}_K,+_{K})$ so actually $E$ is well defined and it can be thought of as a set of $K$ pairs.

Another Important Note: This mapping is the basis for a family of error correcting codes called CRT codes. But, this question is about number theory and not about cs.

Answer 1

Assume $m_1 < m_2$ and consider the product $$ (m_2 - m_1) \prod_{i=1}^n p_i^{b_i}. $$ Then for each $i$ with $1 \le i \le n$, $p_i$ divides this product, because one of two cases must hold:

• Either $p_i \mid m_2 - m_1$, in which case it appears in the first factor,
• Or $m_1 \not\equiv m_2 \pmod {p_i}$, in which case $b_i = 1$ and $p_i$ appears in the second factor.

Since all $n$ primes divide this product, so does their product $N$:

$$N \mid (m_2 - m_1) \prod_{i=1}^n p_i^{b_i}.$$

In particular, we have the inequality $$ (m_2 - m_1) \prod_{i=1}^n p_i^{b_i} \ge N \implies \prod_{i=1}^n p_i^{b_i} \ge \frac{N}{m_2 - m_1} $$ and this implies the inequality you want, because $\frac{N}{m_2-m_1} > \frac N K$.