10.5 剩余定理新证明
对两两互素模的中国剩余定理，高德纳给出两个新证明[11]，转录如下：
定理（中国剩余定理） 设m1，m2，…，mr是两两互素的正整数，即
设m=m1m2…mr，并设a，u1，u2，…，ur是整数。于是恰有一个整数u，它满足
证明 如果对于1≤j≤r，u≡v，则对于所有j，u-v是mj的倍数，所以（1）意味着u-v是m=m1m2…mr的倍数。这证明了（2）至多有一个解。为完成证明，我们还须证明至少有一个解，而这可以用两个简单方法得出：
方法（“非构造性”证明） 当u跑遍m个不同值a≤u＜a+m时，r元组（u mod m1，…，u mod mr）必然也跑遍m个不同的值，因为（2）至多有一个解。但恰巧有m1m2…mr种可能的r元组（v1v2…vr）使得0≤vj＜mj。因此每个r元组恰出现一次，而且必然有n的某值使（u mod m1，…，u mod mr）=（u1，…，ur）。
方法2（“构造性”的证明） 我们可能找数mj≡0，使得
这是由于（1）意味着mj与m/mj互素而得出的，所以欧拉定理可以取
现在数
满足（2）的所有条件。
第一个证明是经典的，它仅仅依赖于一些非常简单的概念，即以下的事实：
（ⅰ）任何m1，m2，…和mr的倍数的数，当诸mj两两互素时，必是m1m2…mr的倍数；
（ⅱ）如果m只鸽子放入m个鸽巢当中而且没有两只鸽子同在一个鸽巢中，则在每个鸽巢中必然有一只鸽子。
按照数学的美学传统思想，这毫无疑问是中国剩余定理最漂亮的证明。但从计算观点看，它是毫无价值的！这等于说，“试验u=a，a+1，…直到你发现一个值，使得u≡u1（mod m1），…，u≡ur（mod mr）”。
中国剩余定理的第二个证明是更为明显的，它说明怎样计算r个新的常数M1，…，Mr，并且借助于这些常数通过公式（5）而得到解。这个证明使用了更复杂的一些概念（如欧拉定理），但从计算的观点看，它是更为令人满意的，仅仅需要确定一次。另一方面，通过等式（4）确定Mj肯定不是轻而易举的，因为一般来说，欧拉φ函数的计算要求把Mj分解成素因子的乘方。比起使用（4），有好得多的方法来计算Mj。在这方面我们可以再次看到数学的优美性和计算的有效性之间的区别。但即使我们通过最好的方法来求得Mj，我们仍然受阻于这样一个事实，即Mj是巨大的数m/mj的一个倍数。因此，（5）迫使我们进行大量高精度的计算，而这样的计算恰恰是我们首先希望通过模算术来加以避免的。