在模
p
的群中
ax=1(mod p)
,则称
x
为
a
的逆(
inv
).在这种运算中,
a/b=a*inv[b](mod p)
逆元存在的条件是
gcd(a,p)=1
这里简单证明一下,假设
gdc(a,p)=d ax%p=t 即 ax+bp=t
,则
t%d=0
,显然
t!=1
,即
ax%p!=1
,
a
没有逆元
一般情况下我们可以用扩展欧几里得求某个元素的逆元:
ax=1(mod p)
即
ax+bp=1
求得的
x=(x%p+p)%p
就是一个逆元啦.
求一个逆元的时候这样做完全没有什么问题,但是当求很多元素的逆元的时候这样做效率就比较低.看书上学习了一种递推法求逆元的方法:
-
1*inv[1]=1
,即
1
的逆元为
1
-
加入我们要求的是
x%p
的逆元
我们令
p=kx+r
,即
k=[p/x]
,
r=p%x
kx+r=0(%p)
等式左右两边同时乘以
inv[x]和inv[r]
就可以得到:
k*inv[r]+inv[x]=0
即
inv[x]=-k*inv[r]
, 所以
inv[x]=-p/x*inv[(p%x)]
,
p%x
小于
x
,所以
x
肯定是已经求得的.
这样就可以递推求得逆元.当然也可以用这种方法求单个元素的逆元,复杂度和扩展欧几里得的复杂度是差不多的.
当我们确定a和p互质的时候，我们先求得p的欧拉函数值，再根据欧拉公式得到a的逆元就是a
f§-2
.(好像不是很常用的样子)。