[科普中國]-重模同余式

重模同余式(congruence with respect to double modulus)是同余式的一種推廣，給定素數(shù)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，2x2-3)1。重模同余式有下述性質(zhì)：1.重模同余是一種等價關(guān)系，即具有自反性、對稱性和傳遞性。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.設(shè)φ(x)對p之次數(shù)為n，任一多項式必與下列多項式a1+a2x+…+anxn-1(0≤ai≤p-1)之一重模同余。

基本介紹下面討論的多項式皆為整系數(shù)多項式，M為正整數(shù)。

定義1 若兩多項式f(z)和g(z)之對應(yīng)系數(shù)皆關(guān)于模M同余，則稱此兩多項式關(guān)于模M同余，以

f(z)≡g(z)modM

表示2。

例如

7z3+8z2+2z+10≡3z3+2z+2mod4.

定義2 設(shè)f?(z)，f?(z),φ(z)是多項式，若存在多項式u(z)，使

f?(z)-f?(z)=u(z)φ(z)modM,

則稱f?(z)和f?(z)關(guān)于重模M,φ(z)同余，記作

f?(z)≡f?(z)(moddM，φ(x)).

例如

7z3+8z2+2z+10≡2z-1modd4,z3+1.

重模同余式的性質(zhì)性質(zhì)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) 設(shè)φ(z)的首項系數(shù)為1，關(guān)于模M的次數(shù)為n, 則任一多項式必與下列多項式之一

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

關(guān)于重模M,φ(z)同余，并且這Mn個多項式關(guān)于重模M,φ(z)兩兩互不同余2。

性質(zhì)1容易用定義證明。

性質(zhì)21)若f(z)≡0 moddM，φ(z)，當(dāng)且僅當(dāng)存在多項式u(z)和v(z)，使

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

2)若f(z)≡0 moddaM，φ(z)，a為非零整數(shù)，則f(z)≡0 moddM，φ(z)；

3)若af(z)≡0 moddaM，φ(z),a為非零整數(shù)，φ(z)是Za[z]中的非零因子，則

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

4)若f(z)≡0 moddM，φ(z)，則對任何整數(shù)a，有af(z)≡0 moddaM，φ(z)2。

性質(zhì)31) 若(M?,M?)=1，且f(z)≡0 moddMi，φ(z)(i=1,2)，則f(z)≡0 moddM，φ(z)，這里M = M?M?；

2) 設(shè)M?，M?，.，Mn是兩兩互素的非零整數(shù)，M=M?M?...Mn，則方程組

有解，并且解關(guān)于重模M,φ(z)唯一2。

本詞條內(nèi)容貢獻(xiàn)者為:

杜強 - 高級工程師 - 中國科學(xué)院工程熱物理研究所