2002年第6期 中学数学
45
中国剩余定理的几点应用
223001 江苏省淮阴工学院经济管理系 张积羽430062 湖北大学数学系 刘合国
中国剩余定理在代数学里起着重要的作用, 它是我们祖先智慧的结晶. 这个定理现在已被表述成极为一般的形式, 这里我们采用多项式的语言来叙述它, 但所使用的方法具有一般性. 在高等代数里, 中国剩余定理和可以由它导出的L agrange .
例1 设1, p ) , (x . 证明对每个1≤i ≤n , 存在多项式f i (x ) , 使得
f i (x ) ≡1 (m od p i (x ) )
f i (x ) ≡0 (m od p j (x ) ) , 这里j ≠i .
+f n (x ) g n (x ) , 作如下的辗转相除:
n
F (x ) =q (x )
∏p
i =1
i
(x ) +f (x ) ,
其中f (x ) 的次数
n
(
∑m
i =1
i
,
1≤i ≤n , 均有f (x ) ≡F (x ) ≡
∑f
i =1
i
(x ) g i (x ) ≡f i (x ) (m od p i (x ) ) .
假设g (x ) 也适合f (x ) 所满足的条件, 那么易证对每个1≤i ≤n , 都有p i (x ) f (x ) -g (x ) , 注意到p 1(x ) , p 2(x ) , …, p n (x ) 是两两
n
证明 因p 1(x ) 、p 2(x ) 、…、p n (x ) 是两两互素的, 故当j ≠i 时, (p j (x ) , p i (x ) ) =1, 于是(∏p j (x ) , p i (x ) ) =1, 从而存在多项式
j ≠i
互素的, 可得∏p i (x ) f (x ) -g (x ) , 又
i =1
n
f (x ) -g (x ) 的次数小于
∏p
i =1
i
(x ) 的次数, 必
u i (x ) 、v i (x ) , 使
u i (x )
须f (x ) -g (x ) =0, 即g (x ) =f (x ) .
例3 证明L agrange 插值公式:设a 1, a 2, …, a n 是数域上n 个不同的数, 则对任意n 个数b 1, b 2, …, b n , 存在唯一的次数小于n 的多项
n
∏
j ≠i
p j (x ) +v i (x ) p i (x ) =1,
现令f i (x ) =u i (x ) ∏p j (x ) 即可.
j ≠i
例2 证明中国剩余定理:设p 1(x ) ,
p 2(x ) , …, p n (x ) 是某个数域上两两互素的多
式 L (x ) =
∑∏
b i
i =1
j ≠i
a i -a j
项式, 其次数依次为m 1, m 2, …, m n . 证明对任意n 个多项式f 1(x ) , f 2(x ) , …, f n (x ) , 存在唯一的次数小于m 1+m 2+…+m n 的多项式
f (x ) , 使得对每个1≤i ≤n , 均有
f (x ) ≡f i (x ) (m od p i (x ) ) .
适合条件L (a i ) =b i , 其中1≤i ≤n .
证明 取多项式p 1(x ) =x -a 1, p 2(x ) =x -a 2, …, p n (x ) =x -a n , 它们是两两互
素的. 对下面的同余式
f (x ) ≡b i (m od p i (x ) ) (1≤i ≤n )
证明 由例1知对每个1≤i ≤n , 存在多项式g i (x ) , 使得
g i (x ) ≡1 (m od p i (x ) )
g i (x ) ≡0 (m od p j (x ) ) , 当j ≠i 时.
运用中国剩余定理及其证明, 即可得知L (x ) 为所求.
例4 证明数域K 上的n 次多项式f (x ) 在K 里至多有n 个互异根.
证明 若f (x ) 在K 里有n +1个根a 1,
现记F (x ) =f 1(x ) g 1(x ) +f 2(x ) g 2(x ) +…
46
中学数学 2002年第6期
n
a 2, …, a n +1, 即f (a 1) =f (a 2) =…=f (a n +1)
=0, 则据例3即知f (x ) ≡0, 这与f (x ) 的次
解 设f (x ) =p (x ) ∏(x -a i ) +
i =1
数5(f (x ) ) =n 矛盾, 因此结论成立.
例5 设f (x ) 除以x 2+1, x 2+2的余式分别为4x +4, 4x +8, 求f (x ) 除以(x 2+1) (x 2+2) 的余式.
r (x ) , 其中r (x ) 的次数小于n . 由条件知对
1≤i ≤n , 均有r (a i ) =f (a i ) =a i , 故由L agrange 插值公式知r (x ) =x .
例8 设f (x ) 被x -1, x -2, x -3除后, 所得的余式分别4, 8, 16, 求f (x ) 被(x -1) (x -2) (x -3) 除后的余式.
解 由条件可得
2
f (x ) ≡4x +4 (m od x +1) 2
f (x ) ≡4x +8 (m od x +2)
解 设f (x ) =p (x ) (x -1) (x -2) (x -3) r (x ) , r (3, 从
注意到x 2+1与x 2+2互素, 且(-1) (x 2+1) +1 (x 2+2) =1, 由例2及其证明
) f (1) =4, r (2) =f (2) =8, r (3) =f (3) =16,
由L agrange 插值公式直接得到r (x ) =+8 (1-2) (1-3)
+16 =
(3-1) (3-2) 例9 设f (x ) =a 0+4
(2-1) (2-3) 2x 2-2x +4.
a 1x +…+a n x
n
可得f (x ) ≡(4x +4) 1 (x 2) + (4x +8) -2+ (m od (x (x 2) ,
因此f (x ) 除以x 2+1) (x 2+2) 的余式为 (4x +4) (x 2+2) -=4x -4x 2.
(4x +8) (x 2+1)
例6 求满足下列条件的多项式f (x ) :
232
x +1 f (x ) , x +x +1 f (x ) +1.
解 条件x 2+1 f (x ) ,
32
x +x +1 f (x ) +1可改写成2
f (x ) ≡0 (m od x +1)
是个n 次多项式. 证明对任意两两互异的数
x 0, x 1, …, x n , 总有m f (x i ) ≥
0≤i ≤n
n
i
,
f (x ) ≡-2
1 (m od x +x +1)
32
∑ w
i =0
注意到 (x 2+1, x 3+x 2+1) =1, 且(1-x -x ) (1+x ) +x (x +x +1) =1,
2
3
2
其中每个w i =
∏(x
j ≠i n
i
, (0≤i ≤n ) . -x j )
(x i -x j )
-x j )
证明 由L agrange 插值公式知
f (x ) =
由例2可得f (x ) ≡0 x (x +x +1) + (-1) (1-x -x ) (x +1) (m od (x 2+1) (x 3+x 2+1) ) 即 f (x ) =p (x ) (x 2+1) (x 3+x 2+1) +
(x 2+1) (x 2+x -1) ,
2
2
32
∑
i =0n i =0
f (x i )
∏
j ≠i
=
∑w
n
i
f (x i )
∏(x
j ≠i
n
=a 0+a 1x +…+a n x n ,
其中p (x ) 是任意多项式.
例7 设K 是个数域, a 1, a 2, …, a n 是K 的n 个互异的元素, f (x ) ∈K [x ]适合条件:
f (x ) 除以x -n
比较等式里x 的系数, 得到∑w i f (x i ) =a n ,
i =0
n
n
因此 a n =
∑w i f (x i ) ≤
i =0
∑ w
i =0n
i
a i 得余数a i (1≤i ≤n ) ,
f (x i ) , 于是m ax { f (x i ) }≥
0≤i ≤n
i
求f (x ) 除以∏(x -a i ) 所得的余式.
i =1
∑ w
i =0
例10 设f (x ) =a 0+a 1x +…+a n x n ,
2002年第6期 中学数学
47
n
n
a n =1, x 0, x 1, …, x n 是任意整数, x 0
0≤i ≤n
∑ w i =
i =0
∑∏
i =0
j
n
2
n
x i -x j
i
∏
j >i
x i -x j
j
证明 直接运用例9可得m ax { f (x i ) }≥
0≤i ≤n
n
=
-1
∑∏x
i =0n
j
-x j
∏x
j >i
-x i
i
n
=(
∑ w
i =0
∑ w i )
i =0
,
≤∑
n
=,
i ! (n -i ) ! n !
其中w i =
∏x
j ≠i
i
, 于是-x j
因此 m ax { f (x i ) }≥n 0≤i ≤n 2
(收稿日期:20020329)
读刊
随笔
李耀文
文[1]一个命题:
设△A B C 的外接圆半径为R , 内切圆半径为r , 顶点A 、B 、C 到内心的距离分别为a 0、
2
b 0、c 0, 则 4R r =a 0b 0c 0.
今给出此命题所引伸出的一个“姊妹”命题:
命题 设△A B C 的外接圆半径为R , 旁切圆半径为r ′, 顶点A 、B 、C 到对应的旁心的
′′′2′′′
距离分别为a 0、b 0、c 0, 则 4R r ′=a 0b 0c 0.
证明 如图1,
∵ r ′=a ′0sin
=c ′0co s
把②代入①式, 得
r =a 0b 0c 0
3′
′′′
, 4R
故
2
4R r ′=a ′. 0b ′0c ′0
综合文[1]及上述性
质可总述成如下命题:
设I 是△A B C 的内心或旁心, r 是内切圆半径或对应的旁切圆半径, R 是外接圆半径, 则
4R r 2=IA IB IC .
图1
2
=b ′0co s ,
2
同时, 我们还不难得到关于三角形双圆半径的又一个命题:
2
3
∴ r ′=a ′0b ′0c ′0sin
2
co s
2
co s
2
①
设I 、I 0分别是△A B C 的内心和旁心, r 、
r 0分别是内切圆半径和对应的旁切圆半径, R
(b +c -a ) =R r ′(sin B +又 △=r ′2
sin C -sin A ) =2R 2sin A sin B sin C ,
∴ =,
2R sin B +sin C -sin A
又易证知, 在△A B C 中, 有
是外接圆半径, 则
R rr 0=
4
(IA IB IC ) (I 0A I 0B I 0C ) .
参考文献
sin B +sin C -sin A =4sin
2
sin
2
co s
1 丁遵标1关于三角形的双圆半径的两个命题1中
2
,
学数学, 2002, 1
2 梁绍鸿, 赵慈庚1初等数学复习及研究(平面几=2sin co s co s , 2R 222
何) 1北京:人民教育出版社, 1978, 5
∴ =sin co s co s ②(收稿日期:20020204) 4R 222
∴
2002年第6期 中学数学
45
中国剩余定理的几点应用
223001 江苏省淮阴工学院经济管理系 张积羽430062 湖北大学数学系 刘合国
中国剩余定理在代数学里起着重要的作用, 它是我们祖先智慧的结晶. 这个定理现在已被表述成极为一般的形式, 这里我们采用多项式的语言来叙述它, 但所使用的方法具有一般性. 在高等代数里, 中国剩余定理和可以由它导出的L agrange .
例1 设1, p ) , (x . 证明对每个1≤i ≤n , 存在多项式f i (x ) , 使得
f i (x ) ≡1 (m od p i (x ) )
f i (x ) ≡0 (m od p j (x ) ) , 这里j ≠i .
+f n (x ) g n (x ) , 作如下的辗转相除:
n
F (x ) =q (x )
∏p
i =1
i
(x ) +f (x ) ,
其中f (x ) 的次数
n
(
∑m
i =1
i
,
1≤i ≤n , 均有f (x ) ≡F (x ) ≡
∑f
i =1
i
(x ) g i (x ) ≡f i (x ) (m od p i (x ) ) .
假设g (x ) 也适合f (x ) 所满足的条件, 那么易证对每个1≤i ≤n , 都有p i (x ) f (x ) -g (x ) , 注意到p 1(x ) , p 2(x ) , …, p n (x ) 是两两
n
证明 因p 1(x ) 、p 2(x ) 、…、p n (x ) 是两两互素的, 故当j ≠i 时, (p j (x ) , p i (x ) ) =1, 于是(∏p j (x ) , p i (x ) ) =1, 从而存在多项式
j ≠i
互素的, 可得∏p i (x ) f (x ) -g (x ) , 又
i =1
n
f (x ) -g (x ) 的次数小于
∏p
i =1
i
(x ) 的次数, 必
u i (x ) 、v i (x ) , 使
u i (x )
须f (x ) -g (x ) =0, 即g (x ) =f (x ) .
例3 证明L agrange 插值公式:设a 1, a 2, …, a n 是数域上n 个不同的数, 则对任意n 个数b 1, b 2, …, b n , 存在唯一的次数小于n 的多项
n
∏
j ≠i
p j (x ) +v i (x ) p i (x ) =1,
现令f i (x ) =u i (x ) ∏p j (x ) 即可.
j ≠i
例2 证明中国剩余定理:设p 1(x ) ,
p 2(x ) , …, p n (x ) 是某个数域上两两互素的多
式 L (x ) =
∑∏
b i
i =1
j ≠i
a i -a j
项式, 其次数依次为m 1, m 2, …, m n . 证明对任意n 个多项式f 1(x ) , f 2(x ) , …, f n (x ) , 存在唯一的次数小于m 1+m 2+…+m n 的多项式
f (x ) , 使得对每个1≤i ≤n , 均有
f (x ) ≡f i (x ) (m od p i (x ) ) .
适合条件L (a i ) =b i , 其中1≤i ≤n .
证明 取多项式p 1(x ) =x -a 1, p 2(x ) =x -a 2, …, p n (x ) =x -a n , 它们是两两互
素的. 对下面的同余式
f (x ) ≡b i (m od p i (x ) ) (1≤i ≤n )
证明 由例1知对每个1≤i ≤n , 存在多项式g i (x ) , 使得
g i (x ) ≡1 (m od p i (x ) )
g i (x ) ≡0 (m od p j (x ) ) , 当j ≠i 时.
运用中国剩余定理及其证明, 即可得知L (x ) 为所求.
例4 证明数域K 上的n 次多项式f (x ) 在K 里至多有n 个互异根.
证明 若f (x ) 在K 里有n +1个根a 1,
现记F (x ) =f 1(x ) g 1(x ) +f 2(x ) g 2(x ) +…
46
中学数学 2002年第6期
n
a 2, …, a n +1, 即f (a 1) =f (a 2) =…=f (a n +1)
=0, 则据例3即知f (x ) ≡0, 这与f (x ) 的次
解 设f (x ) =p (x ) ∏(x -a i ) +
i =1
数5(f (x ) ) =n 矛盾, 因此结论成立.
例5 设f (x ) 除以x 2+1, x 2+2的余式分别为4x +4, 4x +8, 求f (x ) 除以(x 2+1) (x 2+2) 的余式.
r (x ) , 其中r (x ) 的次数小于n . 由条件知对
1≤i ≤n , 均有r (a i ) =f (a i ) =a i , 故由L agrange 插值公式知r (x ) =x .
例8 设f (x ) 被x -1, x -2, x -3除后, 所得的余式分别4, 8, 16, 求f (x ) 被(x -1) (x -2) (x -3) 除后的余式.
解 由条件可得
2
f (x ) ≡4x +4 (m od x +1) 2
f (x ) ≡4x +8 (m od x +2)
解 设f (x ) =p (x ) (x -1) (x -2) (x -3) r (x ) , r (3, 从
注意到x 2+1与x 2+2互素, 且(-1) (x 2+1) +1 (x 2+2) =1, 由例2及其证明
) f (1) =4, r (2) =f (2) =8, r (3) =f (3) =16,
由L agrange 插值公式直接得到r (x ) =+8 (1-2) (1-3)
+16 =
(3-1) (3-2) 例9 设f (x ) =a 0+4
(2-1) (2-3) 2x 2-2x +4.
a 1x +…+a n x
n
可得f (x ) ≡(4x +4) 1 (x 2) + (4x +8) -2+ (m od (x (x 2) ,
因此f (x ) 除以x 2+1) (x 2+2) 的余式为 (4x +4) (x 2+2) -=4x -4x 2.
(4x +8) (x 2+1)
例6 求满足下列条件的多项式f (x ) :
232
x +1 f (x ) , x +x +1 f (x ) +1.
解 条件x 2+1 f (x ) ,
32
x +x +1 f (x ) +1可改写成2
f (x ) ≡0 (m od x +1)
是个n 次多项式. 证明对任意两两互异的数
x 0, x 1, …, x n , 总有m f (x i ) ≥
0≤i ≤n
n
i
,
f (x ) ≡-2
1 (m od x +x +1)
32
∑ w
i =0
注意到 (x 2+1, x 3+x 2+1) =1, 且(1-x -x ) (1+x ) +x (x +x +1) =1,
2
3
2
其中每个w i =
∏(x
j ≠i n
i
, (0≤i ≤n ) . -x j )
(x i -x j )
-x j )
证明 由L agrange 插值公式知
f (x ) =
由例2可得f (x ) ≡0 x (x +x +1) + (-1) (1-x -x ) (x +1) (m od (x 2+1) (x 3+x 2+1) ) 即 f (x ) =p (x ) (x 2+1) (x 3+x 2+1) +
(x 2+1) (x 2+x -1) ,
2
2
32
∑
i =0n i =0
f (x i )
∏
j ≠i
=
∑w
n
i
f (x i )
∏(x
j ≠i
n
=a 0+a 1x +…+a n x n ,
其中p (x ) 是任意多项式.
例7 设K 是个数域, a 1, a 2, …, a n 是K 的n 个互异的元素, f (x ) ∈K [x ]适合条件:
f (x ) 除以x -n
比较等式里x 的系数, 得到∑w i f (x i ) =a n ,
i =0
n
n
因此 a n =
∑w i f (x i ) ≤
i =0
∑ w
i =0n
i
a i 得余数a i (1≤i ≤n ) ,
f (x i ) , 于是m ax { f (x i ) }≥
0≤i ≤n
i
求f (x ) 除以∏(x -a i ) 所得的余式.
i =1
∑ w
i =0
例10 设f (x ) =a 0+a 1x +…+a n x n ,
2002年第6期 中学数学
47
n
n
a n =1, x 0, x 1, …, x n 是任意整数, x 0
0≤i ≤n
∑ w i =
i =0
∑∏
i =0
j
n
2
n
x i -x j
i
∏
j >i
x i -x j
j
证明 直接运用例9可得m ax { f (x i ) }≥
0≤i ≤n
n
=
-1
∑∏x
i =0n
j
-x j
∏x
j >i
-x i
i
n
=(
∑ w
i =0
∑ w i )
i =0
,
≤∑
n
=,
i ! (n -i ) ! n !
其中w i =
∏x
j ≠i
i
, 于是-x j
因此 m ax { f (x i ) }≥n 0≤i ≤n 2
(收稿日期:20020329)
读刊
随笔
李耀文
文[1]一个命题:
设△A B C 的外接圆半径为R , 内切圆半径为r , 顶点A 、B 、C 到内心的距离分别为a 0、
2
b 0、c 0, 则 4R r =a 0b 0c 0.
今给出此命题所引伸出的一个“姊妹”命题:
命题 设△A B C 的外接圆半径为R , 旁切圆半径为r ′, 顶点A 、B 、C 到对应的旁心的
′′′2′′′
距离分别为a 0、b 0、c 0, 则 4R r ′=a 0b 0c 0.
证明 如图1,
∵ r ′=a ′0sin
=c ′0co s
把②代入①式, 得
r =a 0b 0c 0
3′
′′′
, 4R
故
2
4R r ′=a ′. 0b ′0c ′0
综合文[1]及上述性
质可总述成如下命题:
设I 是△A B C 的内心或旁心, r 是内切圆半径或对应的旁切圆半径, R 是外接圆半径, 则
4R r 2=IA IB IC .
图1
2
=b ′0co s ,
2
同时, 我们还不难得到关于三角形双圆半径的又一个命题:
2
3
∴ r ′=a ′0b ′0c ′0sin
2
co s
2
co s
2
①
设I 、I 0分别是△A B C 的内心和旁心, r 、
r 0分别是内切圆半径和对应的旁切圆半径, R
(b +c -a ) =R r ′(sin B +又 △=r ′2
sin C -sin A ) =2R 2sin A sin B sin C ,
∴ =,
2R sin B +sin C -sin A
又易证知, 在△A B C 中, 有
是外接圆半径, 则
R rr 0=
4
(IA IB IC ) (I 0A I 0B I 0C ) .
参考文献
sin B +sin C -sin A =4sin
2
sin
2
co s
1 丁遵标1关于三角形的双圆半径的两个命题1中
2
,
学数学, 2002, 1
2 梁绍鸿, 赵慈庚1初等数学复习及研究(平面几=2sin co s co s , 2R 222
何) 1北京:人民教育出版社, 1978, 5
∴ =sin co s co s ②(收稿日期:20020204) 4R 222
∴