专栏文章

乘法逆元

SSuperMarxet
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miphz5cp
此快照首次捕获于
2025/12/03 12:18
3 个月前
此快照最后确认于
2025/12/03 12:18
3 个月前
查看原文
在实数范围内，当a≠0a≠0时，一定有a×1a=1a\times\frac{1}{a}=1
在mod P意义下，我们同样想要这么一个的东西使 “ax≡1(modP)ax\equiv1(mod P) ” ，那么这个x就称作a在模P意义下的逆元。
为什么我们需要逆元呢？ 首先，在计算当中，我们可能需要计算形如“6417 mod 16\frac {64}{17}\bmod16 ”这种算式。由于除法特殊的性质，“(a/b) mod M(a/b)\bmod M并不一定等于(a mod M/b mod M) mod M(a\bmod M/b\bmod M) \bmod M”。这个时候我们就需要用逆元把除法转换成乘法。
或者，当我们计算模意义下的除法的时候，我们通常需要边做边模，这样比较省空间，可以有效防止爆范围，这个时候我们也需要使用逆元来把除法转换成乘法。
总之逆元非常的好用，但是怎么去求呢？
首先我们要知道一个定理：裴蜀定理：
对于整数a,b，设他们的最大公约数gcd(a,b)=dgcd(a,b)=d，则一定存在一组整数解使得 ax+by=dax+by=d。
那么我们从这个定理又能推出一个定理：对于整数a,b,c,ax+by=ca,b,c, ax+by=c有整数解当且仅当 gcd(a,b)∣cgcd(a,b)|c 。
充分性：如果c是gcd(a,b)gcd(a,b)的倍数，那么可以先通过裴蜀定理ax+by=gcd(a,b)ax+by=gcd(a,b)的一组解x,yx,y。然后将x,yx,y同乘以cgcd(a,b)\frac{c}{gcd(a,b)}，就得到了不定方程ax+by=cax+by=c的一组解。
必要性：如果不定方程有解，因为aa是gcd(a,b)gcd(a,b)的倍数，bb同样也是，并且x,yx,y都是整数，所以ax+byax+by，也就是c，也一定是gcd(a,b)gcd(a,b)的倍数。
——《深进》
通过这个定理我们就只需要求出 ax+by=gcd(a,b)=dax+by=gcd(a,b)=d的一组解就好了。怎么求呢？这个时候我们就要使用伟大的扩欧了。
回忆一下求最大公约数用的欧几里得算法（辗转相除法），然后用它的经验求解这个不定方程：
1.当b=0b=0时，ax+by=dax+by=d的解就是x=da，yx=\frac{d}{a}，y任意。
2.求出bx+(a mod b)y=dbx+(a \bmod b)y=d的一组解，记作(x0,y0)(x_0,y_0)。
现在我们有了方程的一组解，接下来的问题就是怎么从这组解生成一组新的(x,y)(x,y)。
已知bx0+(a mod b)y0=dbx_0+(a \bmod b)y_0=d，那么可以把a mod ba \bmod b用a−⌊ab⌋×b a-\lfloor \frac{a}{b} \rfloor \times b来表示，得到 bx0+(a−⌊ab⌋×b)y0=dbx_0+(a-\lfloor \frac{a}{b}\rfloor \times b)y_0=d 提公因式，得 ay0+b(x0−⌊ab⌋y0)=day_0+b(x_0-\lfloor \frac{a}{b} \rfloor y_0)=d 又因为ax+by=dax+by=d
所以有 ay0+b(x0−⌊ab⌋y0)=ax+byay_0+b(x_0-\lfloor \frac{a}{b} \rfloor y_0)=ax+by 这个时候可以发现，只要令(x,y)=(y0,x0−⌊ab⌋y0)(x,y)=(y_0,x_0-\lfloor \frac{a}{b} \rfloor y_0)，这个问题就可以解决了，这样裴蜀定理也就得到了证明。
代码实现：
CPP
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
ll a,p;
void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>a>>p;
		ll x,y;
		exgcd(a,p,x,y); 
		x=(x%p+p)%p;
		cout<<x<<endl;
	return 0;
}
这样我们得出的x就是a在模P意义上的逆元。
或者，如果我们不想用扩欧，也有另一种方法来做。
费马小定理，指的是如果p是一个质数而整数a不是p的倍数，则有 ap−1≡1(modp)a^{p-1}\equiv 1(modp)
那通过这个定理我们就能知道, a×ap−2=ap−1(modp)≡1(modp)a\times a^{p-2}=a^{p-1}(modp)\equiv1(modp) 所以ap−2(modp)a^{p-2}(modp)就是a在模P意义下的逆元，那么我们就只需要求ap−2(modp)a^{p-2}(modp)就好了
代码实现：
CPP
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int mod=19260817;
string s,t;
ll a,b;
ll fpow(ll x,ll y){
	ll t=1;
	while(y){
		if(y&1) t=t*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return t;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>s>>t;
	for(int i=0;i<s.size();i++) a=(a*10+s[i]-'0')%mod;
	for(int i=0;i<t.size();i++) b=(b*10+t[i]-'0')%mod;
	if(a%mod&&!(b%mod)) cout<<"Angry!";
	cout<<a*fpow(b,mod-2)%mod;
	return 0;
}
这样我们就算出了a在模P意义上的逆元。但是现在问题又来了：怎么证明在0到p的范围内模P的逆元是唯一的？
我们假设
∃0≤x1,x2<p,x1<x2,ax1≡ax2≡1( mod p)\exists 0≤x_1,x_2<p,x_1<x_2,ax_1\equiv ax_2\equiv 1(\bmod p) ，
那么就有a(x2−x1)≡0( mod p)a(x_2-x_1)\equiv 0(\bmod p)。
也就是说a(x2−x1)a(x_2-x_1)是pp的倍数，但是可以发现0<x2−x1<p，0<x_2-x_1<p，所以 x2−x1x_2-x_1不是pp的倍数，于是这个东西就矛盾了。
那么我们就可以证明：在0到pp的范围内模P的逆元确实是唯一的。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...