模数为素数幂的同余方程解法

本节考虑形如：

f(x)=a_nxⁿ+a_n-1x^n-1+...+a₁x¹+a^₀≡0 mod p^k

的方程，其中a>=2,p为素数，p不整除a。

方程解法步骤：

1.求出 f(x)≡0 mod p 的解 x≡c mod p

2.设 f(x)≡ 0 mod p² 的解为x≡=c+yp^2-1

求出y，带入解得x的值

3.设 f(x)≡ 0 mod p^k 的解为 x≡c+y^k-1

求出y，带入解得x的值

y的求法：

^{f'(c)y ≡ -f(c)/pk-1 mod p}

下面分三种情况：

1.p∤f^'(c),y有唯一解：

y ≡ -f(c)/p^k-1(f'(c))^-1 mod p

注：k为当前所求方程模的幂次

       原式可化为f^'(c)y ≡ -f(c)/p^k-1 mod p 进行求解

2.p|^'(c),但p ∤ f(c)/p^k-1 因此方程无解

注：k为当前所求方程模的幂次

3.p|f^'(c)，且p | f(c)/p^k-1

   此时y为p^k中的所有正整数（p^k除外）

注：为了计算方便，这里一般将y取±p/2和0

下面为例题：