重模同余式(congruence with respect to double modulus)是同余式的一种推广，给定素数p和多项式φ(x)，若f1(x)-f2(x)为φ(x)之倍式mod p，则称f1(x)与f2(x)对重模p，φ(x)同余，记为f1(x)≡f2(x)(mod dp，φ(x))。例如x5+3x4+x2+4x+3≡0(mod d5，2x2-3)。重模同余式有下述性质：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为正整数。