定理已证明

中国剩余定理

命题陈述

若 $n_1,\dots,n_k$ 是两两互素的正整数,则对任意整数 $a_1,\dots,a_k$ ,同余方程组 $x\equiv a_i \pmod{n_i}$ ( $i=1,\dots,k$ )有解 $x$ ,且模 $N=n_1n_2\cdots n_k$ 唯一。

为什么成立?

两两互素的模携带着相互独立的信息,因此为每个模各指定一个余数,就能唯一确定模其积的一个剩余——就像从几个以互素周期运转的时钟上读出同一个数。

证明思路

对每个 $i$ ,令 $N_i=N/n_i$ 。由 $\gcd(N_i,n_i)=1$ ,贝祖等式给出 $y_i$ 使得 $N_iy_i\equiv1\pmod{n_i}$ 。于是 $x=\sum_i a_iN_iy_i$ 满足 $x\equiv a_i\pmod{n_i}$ (对每个 $i$ 都成立),因为 $N_j\equiv0\pmod{n_i}$ 当 $j\ne i$ 时成立。模 $N$ 的唯一性由此得出:两个解之差必是每个 $n_i$ 的倍数,从而是 $N$ 的倍数。

证明者

1801 年证明卡尔·弗里德里希·高斯

用到此定理的主题

中国剩余定理

参考文献

Carl Friedrich Gauss (trans. Arthur A. Clarke) (1986). Disquisitiones Arithmeticae · DOI:10.1016/B978-044450871-3/50117-0
Jean-Claude Martzloff (1997). A History of Chinese Mathematics · DOI:10.1007/978-3-540-33783-6