乘法逆元

乘法逆元

首先来普及一下同余定理:

  1. $(a+b)%p=(a%p+b%p)%p$
  2. $(a-b)%p=((a%p-b%p)+p)%p$ (防止出现负数的情况)
  3. $(a\times b)%p=(a%p\times b%p)%p$
  4. $(b\div a)%p=(b%p\div a%p)%p$ (并不成立)

很显然第4个公式是不对的,那么当我们碰到要边除边取模的情况,该怎么处理呢?答案是使用乘法逆元。

就笔者个人理解,我们知道除一个数相当于乘这个数的倒数,那么在模运算的前提下,对于$(b\div a)%p$这个式子,我们也可以按照这个思想找到一个数x来代替b,使得$(b\times x)%p=(b\div a)%p$,这样的数x,我们就称之为对于%p时a的逆元,记为x=inv(a,p)

Tips:x的值由a和p共同决定,这点和倒数有点不太一样,即对于一个固定的a,p不同时x的值也不同。

那么,inv(a,p)要怎么去求呢?一般是通过费马小定理或者拓展欧几里德去求。

逆元定义

我们将$(b\times x)%p=(b\div a)%p$两边同乘一个a,得到一个线性同余方程$ax\equiv 1(mod;p)$,x就记为a mod p的逆元。(a和p互质的情况下才存在逆元)

费马小定理求法(只适用于p为质数)

直接给出结论,$inv(a,p)=a^{p-2}$

下面是证明,不敢兴趣的可以直接跳过。

费马小定理:

若p为质数,a为正整数,且a,p互质,则$a^{p-1}\equiv 1(mod;p)$

因为$ax\equiv 1(mod;p) $

所以$ax\equiv a^{p-1}(mod;p)$

所以$x=a^{p-2}(mod;p)$

用快速幂求解即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
ll quickpow(ll x,ll n,ll mod)
{
	ll res=1;
	while(n)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
x=quickpow(a,mod-2,mod);

拓展欧几里得求法

这里涉及到用exgcd解线性同余方程组的方法。

鉴于这是一块新的知识点,所以从头开始介绍了exgcd。

请移步:拓展欧几里得

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
//ax%b=1%b,ax+by=1;
ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = exgcd(b, a % b, x, y);
  ll t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}
ll inv(ll a,ll p)
{   ll x=1,y=0;
    exgcd(a,p,x,y);
    x=(x%p+p)%p;
    return x;
}