孙子定理的一个证明
A Proof of Chinese Remainder Theorem

作者: 杨继明 :玉溪师范学院数学系,云南 玉溪;

关键词: 孙子定理证明同余式Chinese Remainder Theorem Proof Congruence

摘要:
本文给出了孙子定理的一个证明。

Abstract: A proof of Chinese Remainder Theorem is given.

1. 引言

在公元四、五世纪的《孙子算经》中的“物不知数”问题:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”答案为:“23”。这个问题也就是求解同余式组

x 2 ( mod 3 ) , x 3 ( mod 5 ) , x 2 ( mod 7 ) .

明朝程大位根据孙子算经里所用的方法用歌谣给出了该题的解法:“三人同行七十稀,五树梅花廿一枝,七子团圆月正半,除百零五便得知。”即解为

x 2 × 70 + 3 × 21 + 2 × 15 233 23 ( mod 105 ) .

在西方,与《孙子算经》同类的算法,最早见于1202年意大利数学家斐波那契的《算经》。1801年,德国数学家高斯的《算术探究》中,才明确写出了这一问题的求法。

把孙子算经给出的结果加以推广,就得到了著名的孙子定理。孙子定理及其证明参阅 [1] [2] 。文 [3] 给出了一个求解孙子问题的简便方法。文 [4] 研究了一般的线性同余式组的有解判别条件及其求解方法。文 [5] 把线性同余式组、线性不定方程组、线性代数方程组、常系数线性微分方程组和常系数线性差分方程组统一成为了R-模上的方程组,并分别给出了各种方程组的解法。

2. 主要结果及应用

下面的定理1就是著名的孙子定理。

定理1 (孙子定理) 设 m 1 , m 2 , , m k 是k个两两互质的正整数,

m = m 1 m 2 m k , m = m i M i , i = 1 , 2 , , k ,

则同余式组

x b 1 ( mod m 1 ) , x b 2 ( mod m 2 ) , , x b k ( mod m k ) . (1)

的解是

x M 1 M 1 b 1 + M 2 M 2 b 2 + + M k M k b k ( mod m ) , (2)

其中

M i M i 1 ( mod m i ) , i = 1 , 2 , , k . (3)

文 [1] 给出了该定理的三种证明方法。下面我们再给出一种证法。

证 因 m 1 , m 2 , , m k 是k个两两互质的正整数,故 ( M i , m i ) = 1 , i = 1 , 2 , , k 。于是,满足(3)式的整数是存在的。

要证明同余式组(1)的解是(2),只需证明(1)式和(2)式等价即可。

设整数x满足(1)式,则 x b i ( mod m i ) , i = 1 , 2 , , k ,从而

M i M i x M i M i b i ( mod m i ) , i = 1 , 2 , , k .

因为当 i j 时, m i | M j ,故

( M 1 M 1 + + M k M k ) x M 1 M 1 b 1 + + M k M k b k ( mod m i ) , i = 1 , 2 , , k .

从而

( M 1 M 1 + + M k M k ) x M 1 M 1 b 1 + + M k M k b k ( mod m ) . (4)

M i ( i = 1 , 2 , , k ) 满足(3)式,故

M 1 M 1 + M 2 M 2 + + M k M k 1 ( mod m i ) , i = 1 , 2 , , k . (5)

m 1 , m 2 , , m k 两两互质,故由(5)式得

M 1 M 1 + M 2 M 2 + + M k M k 1 ( mod m ) (6)

由(4)和(6)两式即知,(2)式成立。

反之,设整数x满足(2)式,则由 m i | M j ( i j ) 和(3)式得

x M 1 M 1 b 1 + M 2 M 2 b 2 + + M k M k b k M i M i b i b i ( mod m i ) , i = 1 , , k .

即整数x满足(1)式。

应用定理1求解孙子问题的例子参见文 [1] [2] 。下面给出一个更便于求解孙子问题的方法。

定理2 设 m 1 , m 2 , , m k 是k个两两互质的正整数,则同余式组(1)的解为

x c 1 + M 1 c 2 + M 2 c 3 + + M k 1 c k ( mod m ) , (7)

其中,

M i = m 1 m 2 m i , i = 1 , 2 , , k , (8)

m = M k

(9)

M i M i 1 ( mod m i + 1 ) , i = 1 , 2 , , k 1 . (10)

证 因 m 1 , m 2 , , m k 两两互质,故满足(10)式的整数 M i 是存在的。首先证明,

c 1 + M 1 c 2 + M 2 c 3 + + M k 1 c k b i ( mod m i ) , i = 1 , 2 , , k . (11)

显然, c 1 + M 1 c 2 + M 2 c 3 + + M k 1 c k b i ( mod m i ) , i = 1 , 2 .而当 3 i k 时,由(8),(9)和(10)式得

c 1 + M 1 c 2 + M 2 c 3 + + M k 1 c k c 1 + M 1 c 2 + + M i 2 c i 1 + M i 1 c i c 1 + M 1 c 2 + + M i 2 c i 1 + M i 1 M i 1 [ b i ( c 1 + M 1 c 2 + + M i 2 c i 1 ) ] c 1 + M 1 c 2 + + M i 2 c i 1 + 1 [ b i ( c 1 + M 1 c 2 + + M i 2 c i 1 ) ] = b i ( mod m i ) .

要证明同余式组(1)的解是(7),只需证明(1)式和(7)式等价即可。设整数x满足(1)式,则

x b i ( mod m i ) , i = 1 , 2 , , k . (12)

由(11)和(12)式得

x c 1 + M 1 c 2 + M 2 c 3 + + M k 1 c k ( mod m i ) , i = 1 , 2 , , k .

m 1 , m 2 , , m k 两两互质,故(7)式成立。

反之,设整数x 满足(7)式,则

x c 1 + M 1 c 2 + M 2 c 3 + + M k 1 c k ( mod m i ) , i = 1 , 2 , , k . (13)

由(11)和(13)式得,(1)式成立。

推论 设 m 1 , m 2 , , m k 是k个两两互质的正整数, M i = m 1 m 2 m i ( i = 1 , 2 , , k ) m = M k ,整数 M i 满足

M i M i 1 ( mod m i + 1 ) , i = 1 , 2 , , k 1 ,

c 1 b 1 m 1 除所得的余数, c 2 M 1 ( b 2 c 1 ) m 2 除所得的余数, c 3 M 2 [ b 3 ( c 1 + M 1 c 2 ) ] m 3 除所得的余数, M k 1 [ b k ( c 1 + M 1 c 2 + + M k 2 c k 1 ) ] m k 除所得的余数,则同余式组(1)的解为

x c 1 + M 1 c 2 + + M k 1 c k ( mod m ) , (14)

其中 0 c 1 + M 1 c 2 + + M k 1 c k m 1

证 根据定理2,(14)为同余式组(1)的解.下面证明

0 c 1 + M 1 c 2 + + M k 1 c k m 1 .

易知, 0 c i m i 1 , i = 1 , 2 , , k 。故

0 c 1 + M 1 c 2 m 1 1 + M 1 ( m 2 1 ) = M 1 1 + M 1 ( m 2 1 ) = M 2 1 ,

0 c 1 + M 1 c 2 + M 2 c 3 M 2 1 + M 2 ( m 3 1 ) = M 3 1 ,

0 c 1 + M 1 c 2 + + M k 1 c k M k 1 1 + M k 1 ( m k 1 ) = M k 1 = m 1 .

例1 解同余式组

x 1 ( mod 3 ) , x 1 ( mod 5 ) , x 2 ( mod 7 ) , x 2 ( mod 11 ) .

解 为了更便于应用定理2的推论求解,把这个同余式组改写为

x 2 ( mod 11 ) , x 2 ( mod 7 ) , x 1 ( mod 5 ) , x 1 ( mod 3 ) .

这里, m 1 = 11 , m 2 = 7 , m 3 = 5 , m 4 = 3 , b 1 = 2 , b 2 = 2 , b 3 = 1 , b 4 = 1

M 1 = m 1 = 11 , M 2 = m 1 m 2 = 11 × 7 = 77 , M 3 = m 1 m 2 m 3 = 77 × 5 = 385 , M 4 = m 1 m 2 m 3 m 4 = 385 × 3 = 1155 = m .

取满足 M 1 M 1 1 ( mod m 2 ) 11 M 1 1 ( mod 7 ) 的一个整数 M 1 = 2

取满足 M 2 M 2 1 ( mod m 3 ) 77 M 2 1 ( mod 5 ) 的一个整数 M 2 = 2

取满足 M 3 M 3 1 ( mod m 4 ) 385 M 3 1 ( mod 3 ) 的一个整数 M 3 = 1

b 1 = 2 9 ( mod 11 ) , c 1 = 9.

M 1 ( b 2 c 1 ) = 2 ( 2 9 ) 0 ( mod 7 ) c 2 = 0 ,则

c 1 + M 1 c 2 = 9 + 11 × 0 = 9 .

M 2 [ b 3 ( c 1 + M 1 c 2 ) ] = 2 ( 1 9 ) 0 ( mod 5 ) c 3 = 0 ,则

c 1 + M 1 c 2 + M 2 c 3 = 9 + 77 × 0 = 9 .

M 3 [ b 4 ( c 1 + M 1 c 2 + M 2 c 3 ) ] = 1 × ( 1 9 ) = 8 1 ( mod 3 ) c 4 = 1 ,则

c 1 + M 1 c 2 + M 2 c 3 + M 3 c 4 = 9 + 385 × 1 = 394 .

故由定理2的推论得,该同余式组的解为

x 394 ( mod 1155 ) .

例2 解同余式组

x b 1 ( mod 11 ) , x b 2 ( mod 7 ) , x b 3 ( mod 6 ) , x b 4 ( mod 5 ) .

解 这里 m 1 = 11 , m 2 = 7 , m 3 = 6 , m 4 = 5

M 1 = m 1 = 11 , M 2 = m 1 m 2 = 77 , M 3 = 462 , M 4 = 2310 = m .

11 M 1 1 ( mod 7 ) M 1 = 2

77 M 2 1 ( mod 6 ) M 2 = 1

462 M 3 1 ( mod 5 ) M 3 = 2

c 1 b 1 ( mod mod 11 ) c 1 = b 1

c 2 M 1 ( b 2 c 1 ) = 2 b 2 2 b 1 ( mod 7 ) c 2 = 2 b 2 2 b 1 ,则

c 1 + M 1 c 2 = b 1 + 11 ( 2 b 2 2 b 1 ) = 22 b 2 21 b 1 .

c 3 M 2 [ b 3 ( c 1 + M 1 c 2 ) ] = [ b 3 ( 22 b 2 21 b 1 ) ] b 3 2 b 2 + 3 b 1 ( mod 6 ) c 3 = b 3 2 b 2 + 3 b 1 ,则

c 1 + M 1 c 2 + M 2 c 3 = 22 b 2 21 b 1 + 77 ( b 3 2 b 2 + 3 b 1 ) = 77 b 3 132 b 2 + 210 b 1 .

c 4 M 3 [ b 4 ( c 1 + M 1 c 2 + M 2 c 3 ) ] = 2 [ b 4 ( 77 b 3 132 b 2 + 210 b 1 ) ] 2 b 4 + b 3 + b 2 ( mod 5 ) ,

c 4 = 2 b 4 + b 3 + b 2 ,则

c 1 + M 1 c 2 + M 2 c 3 + M 3 c 4 = 77 b 3 132 b 2 + 210 b 1 + 462 ( 2 b 4 + b 3 + b 2 ) = 924 b 4 + 385 b 3 + 330 b 2 + 210 b 1 .

故由定理2得,同余式组的解为

x 924 b 4 + 385 b 3 + 330 b 2 + 210 b 1 ( mod 2310 ) ,

x 1386 b 4 + 385 b 3 + 330 b 2 + 210 b 1 ( mod 2310 ) .

参考文献

文章引用: 杨继明 (2019) 孙子定理的一个证明。 理论数学, 9, 265-269. doi: 10.12677/PM.2019.93034

参考文献

[1] 潘承洞, 潘承彪. 初等数论(第二版) [M]. 北京: 北京大学出版社, 2003.

[2] 闵嗣鹤, 严士健. 初等数论(第三版) [M]. 北京: 高等教育出版社, 2003.

[3] 杨继明. 解一元线性同余式组的一个简便方法[J]. 抚州师专学报(自然科学版), 1996(3): 22-23.

[4] 杨继明, 李桂仙. 关于线性不定方程组与线性同余式组[J]. 甘肃教育学院学报(自然科学版), 2000, 14(2): 16-21.

[5] 杨继明. 关于R-模上的方程组[J]. 南都学坛, 1994, 14(6): 18-25.

分享
Top