# 乘法逆元

***

数学上乘法逆元的定义是 $$ax=1，则x是a的乘法逆元$$。

我们这里讨论关于取模运算的乘法逆元。

定义：

满足 $$ax\mod b = 1$$时，称 $$x为a关于模b的逆元$$。

所以逆元有什么用呢？

题目中可能会出现操作中间树很大的情况，如求解：

$$3 \* 6 / 3 \mod 7$$

规定中间变量不能超过7，于是操作步骤为：

$$原式 = ((3\*6)\mod 7)/3 \mod 7$$

$$= 4/3$$

发现无法整除。

可以求出除数3关于模数7的逆元为5，根据定义，在7模数下，3 \* 5 = 1，所以1/3 = 5.

于是我们可以把$$/3$$替换成$$5$$，避免了无法整除的问题。

于是问题来到了如何求逆元。

费马小定理：

$$a^{b-1} \mod b = 1$$

改写一下：

$$a^{b-2} \* a\mod b = 1$$

所以 $$a^{b-2}$$ 就是a模b的逆元。一般这个数用快速幂来算。