若m=m1⋯mkm=m_1\cdots m_km=m1⋯mk,则同余式f(x)≡0(mod m)f\left(x\right)\equiv0\left(\mod m\right)f(x)≡0(modm)与同余式组
等价。若TiT_iTi为同余式f(x)≡0(mod mi)f\left(x\right)\equiv 0\left(\mod m_i\right)f(x)≡0(modmi)的解数,则同余式解数T=T1⋯TkT=T_1\cdots T_kT=T1⋯Tk
f(x)≡0(mod pα)f\left(x\right)\equiv0\left(\mod p^\alpha\right)f(x)≡0(modpα)
STEP1: 验证有解x=x1(mod p)x=x_1\left(\mod p\right)x=x1(modp)为f(x)≡0(mod p)f\left(x\right)\equiv0\left(\mod p\right)f(x)≡0(modp)的一个解,(f′(x1),p)=1\left(f^\prime\left(x_1\right),p\right)=1(f′(x1),p)=1STEP2: 递推x≡xα(mod pα)x\equiv x_\alpha\left(\mod p^\alpha\right)x≡xα(modpα)
STEP1: 验证有解
x=x1(mod p)x=x_1\left(\mod p\right)x=x1(modp)为f(x)≡0(mod p)f\left(x\right)\equiv0\left(\mod p\right)f(x)≡0(modp)的一个解,(f′(x1),p)=1\left(f^\prime\left(x_1\right),p\right)=1(f′(x1),p)=1
STEP2: 递推
x≡xα(mod pα)x\equiv x_\alpha\left(\mod p^\alpha\right)x≡xα(modpα)
最后更新于4年前
这有帮助吗?