重模同余式

重模同余式(congruence with respect to double modulus)是同余式的一种推广，给定素数p和多项式φ(x)，若f₁(x)-f₂(x)为φ(x)之倍式mod p，则称f₁(x)与f₂(x)对重模p，φ(x)同余，记为f₁(x)≡f₂(x)(mod dp，φ(x))。例如x5+3x4+x2+4x+3≡0(mod d5，2x²-3)1。重模同余式有下述性质：1.重模同余是一种等价关系，即具有自反性、对称性和传递性。2.若f(x)≡g(x)，f1(x)≡g1(x)(mod dp，φ(x))，则f(x)±f1(x)≡g(x)±g1(x)(mod dp，φ(x))，f(x)f1(x)≡g(x)g1(x)(mod dp，φ(x))。3.设φ(x)对p之次数为n，任一多项式必与下列多项式a1+a2x+…+anxn-1(0≤ai≤p-1)之一重模同余。

基本介绍下面讨论的多项式皆为整系数多项式，M为正整数。

定义1 若两多项式f(z)和g(z)之对应系数皆关于模M同余，则称此两多项式关于模M同余，以

f(z)≡g(z)modM

表示2。

例如

7z³+8z²+2z+10≡3z³+2z+2mod4.

定义2 设f₁(z)，f₂(z),φ(z)是多项式，若存在多项式u(z)，使

f₁(z)-f₂(z)=u(z)φ(z)modM,

则称f₁(z)和f₂(z)关于重模M,φ(z)同余，记作

f₁(z)≡f₂(z)(moddM，φ(x)).

例如

7z³+8z²+2z+10≡2z-1modd4,z³+1.

重模同余式的性质性质11) f(z)≡f(z)moddM,φ(z)；

2) 若f(z)≡g(z)modM,φ(z)，则g(z)≡f(z )moddM,φ(z)；

3) 若f(z)≡g(z)moddM, φ(z), g(z)≡h(z )moddM,φ(z)，则f(z)≡h(z)moddM，φ(z)；

4) 若f₁(z)≡g1(z)moddM, φ(z), f2(z)≡g2(z)moddM,φ(z)，则

f1(z)±f2(z)≡g1(z)±g2(z)(moddM，φ(z))，

f1(z)f2(z)≡g1(z)g2(z)(moddM，φ(z))；

5) 设φ(z)的首项系数为1，关于模M的次数为n, 则任一多项式必与下列多项式之一

a0+a1z+…+an-1zn-1(0≤ai≤M-1)

关于重模M,φ(z)同余，并且这Mn个多项式关于重模M,φ(z)两两互不同余2。

性质1容易用定义证明。

性质21)若f(z)≡0 moddM，φ(z)，当且仅当存在多项式u(z)和v(z)，使

f(z)=u(z)φ(z)+ Mv(z)；

2)若f(z)≡0 moddaM，φ(z)，a为非零整数，则f(z)≡0 moddM，φ(z)；

3)若af(z)≡0 moddaM，φ(z),a为非零整数，φ(z)是Za[z]中的非零因子，则

f(z)≡0 moddM，φ(z)；

4)若f(z)≡0 moddM，φ(z)，则对任何整数a，有af(z)≡0 moddaM，φ(z)2。

性质31) 若(M₁,M₂)=1，且f(z)≡0 moddMi，φ(z)(i=1,2)，则f(z)≡0 moddM，φ(z)，这里M = M₁M₂；

2) 设M₁，M₂，.，Mn是两两互素的非零整数，M=M₁M₂...Mn，则方程组

有解，并且解关于重模M,φ(z)唯一2。

本词条内容贡献者为:

杜强 - 高级工程师 - 中国科学院工程热物理研究所