初等数论及其应用.pdfVIP

求解同余方程组的例子

本节讨论一次同余方程组的求解.在代数方程体系中,两

个不同的一元一次方程不可能有公共解,因此不存在一

元一次方程组的求解问题.

但对于模不相同的一元一次同余方程组,该问题有意义,

因为它等价于求满足不同整除条件的整数.

韩信点兵问题:一队1000人以上的士兵,排成每行3人余2

人,每行5人余1人,每行7人余6人.问这队士兵至少有多少

人?

10912

共23

求解同余方程组的例子

例2.5.1求满足被3除余2,被5除余1,被7除余6的最小正

整数.

解:易知等价求满足如下三个同余方程组的最小正整数:

≡2(3),≡1(5),≡6(7)

由式1知,存在整数使得=3+2,代入式2得:

3+2≡1(5),即3≡4(5)

它有唯一解≡3(5).

故存在整数使得=5+3,

从而=3(5+3)+2=15+11,代入式3得:

15+11≡6(7),即15≡2(7)

它有唯一解≡2(7).

故存在整数使得=7+2,

从而=15(7+2)+11=105+41,即要求的解为41.3

共23

中国剩余定理

关于一般同余方程组的求解,我们有下面的中国剩余定理,

也称为孙子定理.该定理来源于我国古代孙子在大约公元3

世纪的数学著作《孙子算经》.宋代数学家秦九韶在《数

书九章》中对此类问题有系统的论述,称为大衍求一术.很

多数论问题的本质就是中国剩余定理,这一定理是我国古

代数学的辉煌成就!

问题:今有物不知其数,三三数之剩二,五五数之剩三,七七

数之剩二,问物几何？

解题思路:三人同行七十稀,五树梅花廿一枝,七子团圆正

半月,除百零五便得知.4

共23

中国剩余定理

问题:今有物不知其数,三三数之剩二,五五数之剩三,七七

数之剩二,问物几何？

解题思路:

三人同行七十稀,把除以3所得的余数用70乘.

五树梅花廿一枝,把除以5所得的余数用21乘.

七子团圆正半月,把除以7所得的余数用15乘.

除百零五便得知,把上述三个积加起来,减去105的倍数,所

得的差即为所求.

列式为:2×70＋3×21＋2×15=233,233－105×2=23

5

共23

中国剩余定理

定理2.5.1(中国剩余定理)设1,