乘法逆元 | 木杉の小窝

type

Post

status

Published

date

Jul 22, 2022

slug

article-8

summary

数学知识, 乘法逆元, 解决除法取模问题

深入理解乘法逆元

模运算下的除法：

对于运算，我们可以先将被余数先进行如上的化简，但是始终不是最终解，因为一个数求余的结果一定是一个整数，那么上式中的一定可以转化成某个整数，这个整数就是所谓的乘法逆元。

乘法逆元可以理解成：在mod状态下的倒数

继续上面的样例来一步理解此话的含义

为何可以将替换成3呢？

如果两数相乘结果为1，那么这两个数一定互为倒数。此时由于可以理解为3 和 2 在 mod5 的状态下互为倒数，也就是说：

这时我们就可以说3是模为5情况下2的乘法逆元，2是模为5的情况下3的乘法逆元。

（注意：乘法逆元一定是在某一个模的状态下定义的，不同的模状态下相同的数字也会得到不同的逆元）

定义

乘法逆元（Modular inverse）

【定义】若在意义下，对于一个整数，有，那么这个整数即为的乘法逆元，同时也为的乘法逆元

【充要条件】存在模的乘法逆元的充要条件是，即与互斥。

【应用】求取等同于

除法运算(qmi为计算逆元的函数)


	// calculate (7 / 2) mod 5;
	cout << 7 * qmi(2, 5) % 5 << endl;
	// calculate (1 / 3) mod 5;
	cout << qmi(3, 5) % 5 << endl;
	// calculate (1 / 27) mod 5;
	cout << qmi(27, 5) % 5 << endl;
	// calculate (4 / 3) mod 7;
	cout << 4 * qmi(3, 7) % 7 << endl;
	
	// result: 1 2 3 6

求解乘法逆元

求解乘法逆元的几种方式：

费马小定理（p为质数）、拓展欧几里得、线性递推……

费马小定理

【定义】假如 a 是一个整数，p 是一个质数，那么

~~如果 a 是 p 的倍数，~~

如果a不是p的倍数，

由于乘法逆元存在的充要条件保证了a 和 p 互质，因此定理的第一条在求解乘法逆元中无意义。

根据费马小定理第二条推出逆元求解公式：

式子中就是我们要得到的乘法逆元

基础代码实现


int qmi(int a, int p){
	return (int)pow(a, p - 2ll) % p;
}
int main(){
	int a, p;
	cin >> a >> p;
	int res = qmi(a, p);
	if(__gcd(a, p) == 1 && a % p) cout << qmi(a, p) << endl;
	else cout << "impossible\n";
}

快速幂加强版


// 【快速幂实现】计算a在模为p情况下的乘法逆元. 
int qmi(int a, int p) {
	int k = p - 2;
	int res = 1;
	while (k) {
		if (k & 1) res = (int)res * a % p;
		k >>= 1;
		a = (int)a * a % p;
	}
	return res;
}
int main() {
	int a, p;
	cin >> a >> p;
	int res = qmi(a, p);
	if (__gcd(a, p) == 1) printf("%d\n", res);
	else printf("impossible\n");
}