一次同余方程组

一次同余方程组是一类简单的同余方程组，指形如x≡bi(mod mi) (i=1，2，…，k)的同余方程构成的组。k=2是最简单的一次同余方程组，指x≡bi(mod mi) (i=1，2)的同余方程构成的组1。

基本概念所谓一次同余方程组，是指k(k∈Z+，k>1)个一次同余方程构成的方程组

或记为

同余方程中的模 。当k=2时是最简单的一次同余方程组，即

在同余方程组(2)中，设(m1，m2)=d，M=m1m2。若d∤(b2-b1)，则同余方程组(2)无解。若d|(b2-b1)，则方程(2)对模M有解。设解为x≡x0(mod M)，则x0=b1+m1t0，t0为m1t≡b2-b1(mod m2)的任一解，关于一般同余方程组(1)的解法参见下文2。

一次同余方程组的解法一次同余方程组的方法及解的充要条件由以下两个定理给出。

定理1（孙子定理）设 是k个两两互素的正整数，令

则同余方程组(1)有唯一解：

其中 是由 得出的。

定理2 一次同余式

可解的充要条件是 ，且当(2)可解时，对模 有唯一解2。

上面的孙子定理其实是《孙子算经》卷中记载的“今有物不知其数”一题的解法的推广，这道题是：

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”答曰二十三。

术日：三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之，得二百三十三，以二百一十减之，即得二十三。

术中说：三三数之剩一，则置七十，三三数之剩二，就置一百四

十；五五数之剩一，则置二十一，五五数之剩三，则置六十三；七七数之剩一，则置十五，七七数之剩二，就置三十。若在一百六十五以上，就以一百零五减之，或多则退二百一十。

宋朝周密《志雅堂杂钞》卷中记载有鬼谷算，又叫隔墙算，将此题的解法用一句诗隐括为：

“三岁孩儿七十稀，五留廿一事由奇。七度上元重相会，寒食清明便可知。”

明朝程大位《算法统宗》卷中记载孙子歌，隐括此题解法，更是脍炙人口，孙子歌曰（又名韩信点兵）：

“三人同行七十稀，五树梅花廿一枝。七子团圆正月半，除百零五便得知。”

设x为所求，依题意列式：

孙子歌中所隐含的解法，与孙子算经术日中所说的是一致的，现列表解释如下

|| ||

现在我们用孙子定理来解“今有物不知其数”这一题。

按孙子定理，先解同余方程

35x≡1( mod 3),21x≡1( mod 5),15x≡1( mod7)，

分别得其解

所以

变量x的通解式为

且23为最小正整数2。

例题解析例1解同余方程组：

解 由4·5·7=4·35=5·28=7·20得出公式中的

m₁=4，M₁= 35，

m₂ =5，M₂= 28，

m₃=7，M₃= 20，

其中 依次为同余方程的模， 依次为它的衍数， 依次为各个同余方程的常数项。按孙子定理，先来解同余方程

由35x≡1(mod 4)，解得x≡3( mod 4)，

由28x≡1( mod 5)，解得x≡2( mod 5)，

由20x≡1( mod 7)，解得x≡6( mod 7)，

由此得乘率： ，所以

本词条内容贡献者为:

胡建平 - 副教授 - 西北工业大学