中国剩余定理（Chinese Remainder Theorem）是一个关于一元线性同余方程组的定理。这是数论中一个很重要的定理，在密码学中经常会用到，可用于破解 DHKE 和 RSA 算法。

中国剩余定理定义： 设有 个正整数：，，...，，并且他们两两互质。对于任意的整数 ，，...，，下列一元线性同余方程组有解。 设 ，方程组小于 的解有且只有一个，且方程组任意两个解 ， 模 同余。

证明

首先证明方程组的任意两个解模 同余。

设 ， 是方程组的两个解，对于任意 ，它必定整除 ，由于 两两互质，因此他们的乘积 也整除 。因此方程组的任意两个解模 同余，小于 的解只有一个。

接下来证明方程组有解。

设 ，由于 ，，...， 两两互质，因此有 。对于每一对 、，根据裴蜀定理（Bézout's identity），存在整数 、，使得 。由于 ，因此有 ， 也被称为 模 的数论倒数，可以记为 。

接下来我们证明下面的等式是方程组的一个解：

对任意 ，只要 ，那么 整除 ，因此有 。由此可以得到：

又因为之前我们得到 ，因此有：

也就是说 满足方程组里面的每一个方程，因此它就是方程组的一个解。之前我们证明了任意两个解模 同余。因此方程组的通解可表示为：

其中 为任意整数。 通解也可以写作如下形式：

历史

中国剩余定理出自于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

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

《孙子算经》中首次提到了同余方程组问题，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

1801 年，数学家高斯在他出版的《Disquisitiones Arithmeticae》一书中，正式定义了同余的概念，并且发明了同余符号 。在这本书中高斯也写到了中国同余定理，并且给出了一元线性同余方程组的一般解法，上文证明中给出的方程组通解就出自于高斯这本书。

参考文献
[1] Bézout's identity: https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
[2] Chinese remainder theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem