中文数学 Wiki
Advertisement

中国剩余定理(Chinese Remainder Theorem)又称孙子定理,是求解同余方程组的方法的定理。其源于《孙子算经》的“物不知其数”问题,故称。

内容[]

两两互素,则对任意整数,同余方程组

在模同余意义下有唯一解。

其证明是构造性的,我们不打算给出其证明,但基于证明思路我们给出求解方程组的方法:

解同余方程组[]

下面我们据此证明方法来解同余方程组,令。设满足,我们可以找出符合题意的这样的一个,最后,方程组的解就是

例如,对于同余方程组

首先,两两互素,

所以,最后的解为

不互素的情况[]

不全两两互素时,我们需要将不互素的相应同余方程做拆解,找到它的一个同解方程组。例如

它等价于
可知,第二个方程含于第一个方程,第三、四个方程等价,于是解原方程就是解
用中国剩余定理,解出

实际上,对于一般的一元一次同余方程组

其有解的充要条件是,在有解的情况下模的解数为

应用[]

上下节[]

Advertisement