1.定义

逆元素，是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。

如果说 $a$ 在模 $p$ 意义下的乘法逆元是 $x$，那么 $ax \equiv 1 \pmod{p}$

2.求逆元的方法

·扩展欧几里得

同余方程的转化
$ax \equiv 1 \pmod{p}$ $-->$ $ax+by=$$gcd(a,b)$

∵$b≥2$

∴$ax$ $mod$ $b$ = $1$ $mod$ $b$

∴$ax$ $mod$ $b$ =$1$

根据模的定义，我们设 $y$ ，使 $y$ 满足 $ax+by=1$ （此时 $y$ 为负数）。令 $m=ax+by$ 。

∵令 $k=gcd(a,b)$

根据 $gcd$的定义，设 $a=kc1$ , $b=kc2$

∴ $m=kc1x+kc2y$
$m=k(c1x+c2*y)$

∴$m$ 为 k的倍数

∴ $m$ $%$ $gcd(a,b)$ $=0$

∵ $ax+by=1$

∴ $1$ $%$ $gcd(a,b)$ $=0$

当 $x$ , $y$ 有整数解时， $gcd(a,b)$ 只能等于 $1$。

∴ $ax+by=$ $gcd(a,b)$

扩展欧几里得的求解

设 $G=$$gcd(a,b)$，则 $ax+by=G$ 。

设 $x'$ , $y'$，使其满足
$bx'+($ $a$ $mod$ $b$ $)y'=G$

那么 $ax+by=bx'+($ $a$ $mod$ $b$ $)y'$

∵ $a$ $mod$ $b$ $=$ $a-b \times (a/b)$

∴ $bx'+($ $a$ $mod$ $b$ $)y'$

$=bx'+($ $a-b \times (a/b)$)$\times$$y'$

$=bx'+ay'-b \times (a/b) \times y'$

$=ay'+b \times(x'-(a/b)y') $

∴ $ax+by=ay'+b \times(x'-(a/b)y')$

$$\left{
\begin{aligned}
x & = & y' \
y & = & x'-（a/b）\times y' \
\end{aligned}
\right.
$$

代码如下

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y;
void exgcd(int a,int b){
	//ax+by=gcd(a,b);
	if(b==0){
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b);
	int tmp=x;
	x=y;
	y=tmp-a/b*y;
}
signed main(){
	long a,b;
	cin>>a>>b;
	exgcd(a,b);
	x=(x%b+b)%b;
	cout<<x;
	return 0;
}

JZTXT

[数学]乘法逆元

1.定义

2.求逆元的方法

·扩展欧几里得