# 乘法逆元

***

数学上乘法逆元的定义是 $$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的逆元。一般这个数用快速幂来算。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/suan-fa/cheng-fa-ni-yuan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.