高次同余式

高次同余式解数

m=m1mkm=m_1\cdots m_k,则同余式f(x)0(modm)f\left(x\right)\equiv0\left(\mod m\right)与同余式组

等价。若TiT_i为同余式f(x)0(modmi)f\left(x\right)\equiv 0\left(\mod m_i\right)的解数,则同余式解数T=T1TkT=T_1\cdots T_k

高次同余式求解

f(x)0(modpα)f\left(x\right)\equiv0\left(\mod p^\alpha\right)

  • STEP1: 验证有解

    x=x1(modp)x=x_1\left(\mod p\right)f(x)0(modp)f\left(x\right)\equiv0\left(\mod p\right)的一个解,(f(x1),p)=1\left(f^\prime\left(x_1\right),p\right)=1

  • STEP2: 递推

    xxα(modpα)x\equiv x_\alpha\left(\mod p^\alpha\right)

最后更新于

这有帮助吗?