中国剩余定理

物不知数

中国剩余定理最早记于《孙子算经》中的物不知数问题：

有物不知其数三三数之剩二五五数之剩三七七数之剩二问物几何

翻译成数论，物不知数也即求解下面的同余方程组：

⎩ ⎨ ⎧ x \equiv 2 (mod 3) x \equiv 3 (mod 5) x \equiv 2 (mod 7)

设 $n_{1}, n_{2}, .. n_{m} \in N$ 两两互素，以及任意整数 $a_{1}, a_{2}, .. a_{m} \in Z$ 。设 $n = \prod_{i = 1}^{m} n_{i}$ ，方程组

⎩ ⎨ ⎧ x x \equiv \dots \equiv a_{1} (mod n_{1}) a_{m} (mod n_{m})

必有解，设 $a \in Z$ 是方程组的解，则方程组的解集为 $[a]_{n}$ 。

为了求解这么一个 $a$ ，设 $n_{i}^{*} = n / n_{i}$ ，容易知道 $g c d (n_{i}, n_{i}^{*}) = 1$ 。

所以 $n_{i}^{*}$ 存在模 $n_{i}$ 下的乘法逆元 $t_{i}$ ， $t_{i} n_{i}^{*} \equiv 1 (mod 1)$ 。

设 $e_{i} = t_{i} n_{i}^{*}$ ，有：

1 \pmod {n_i}\\ 0 \pmod {n_j}, j\neq i \end{cases}$$ 容易验证$a=\sum_{i=1}^m e_ia_i$是同余方程组的解。 中国剩余定理在区间$[0, n)$有且只有唯一解。 ## 推论 设$n_1,n_2,..n_m\in \mathbb N$两两互素，$n=\prod^m_{i=1}n_i$。 映射$\tau : \mathbb Z_n \to \mathbb Z_{n_1}\times\mathbb Z_{n_2}... \mathbb Z_{n_m}$ ,$a\to (a \pmod {n_1}, a \pmod {n_2}...,a\pmod {n_m})$ 是一个双射。