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

发布时间 2023-11-14 13:14:11作者: _729_×

本节考虑形如:

f(x)=anxn+an-1xn-1+...+a1x1+a0≡0 mod pk

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

方程解法步骤:

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

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

求出y,带入解得x的值

3.设 f(x)≡ 0 mod pk 的解为 x≡c+yk-1

求出y,带入解得x的值

y的求法:

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

下面分三种情况:

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

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

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

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

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

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

3.p|f'(c),且p | f(c)/pk-1

   此时y为pk中的所有正整数(pk除外)

:为了计算方便,这里一般将y取±p/2和0

下面为例题: