---
title: Notes on Multiplicative Inverse
tags:
  - GCD-LCM
  - Multiplicative Inverse
  - Note
id: "915"
categories:
  - - OI
    - Number Theory
date: 2017-07-01 18:20:58
---

### 扩展欧几里得算法求$a$对模$b$的逆

当$(a, b)=1$时，有

$$
\exists x, y \in Z, \; ax+by=1
$$

扩展欧几里得算法证明如下：

> 设$a \gt b$。
>
> 当$b=0$时，有
>
> $$
> a \times 1+b \times 0=a=(a, b)=1
> $$
>
> 此时$x=1, \; y=0$。
>
> 当$b \neq 0$时，有
>
> $$
> \left\\{
> \begin{align}
> a \times x_1+b \times y_1&=1 \\\\
> b \times x_2+a \bmod b \times y_2&=1
> \end{align}
> \right.
> $$
>
> 所以
>
> $$
> a \times x_1+b \times y_1=b \times x_2+a \bmod b \times y_2
> $$
>
> 将$a \bmod b=a-a/b \times b$代入，得
>
> $$
> a \times x_1+b \times y_1=b \times x_2+a \times y_2-a/b \times b \times y_2
> $$
>
> 那么$x_1=y_2, \; y_1=x_2-a/b \times y_2$。

由此得证。

```cpp
void extend_gcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    int ret = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
}
```

---

### 费马小定理求$a$对模$p$的逆

当$p$是质数且$p \nmid x$时，有

$$
x^{-1} \equiv x^{p-2} \pmod p
$$

证明如下：

> 根据费马小定理，当$p$是质数时，有
>
> $$
> \forall x \in Z, \; x^p \equiv x \pmod p
> $$
>
> 当$p \nmid x$时，有
>
> $$
> \begin{align}
> x^{p-1} &\equiv 1 \pmod p \\\\
> x^{-1} &\equiv x^{p-2} \pmod p
> \end{align}
> $$

由此得证。

---

### $O(n)$时间求出$1..n$对模$p$的逆

当$p$是质数且$1 \lt i \lt p$时，有

$$
i^{-1} \equiv (p-p/i) \times (p \bmod i)^{-1} \pmod p
$$

证明如下：

> 令$t=p/i, \; k=p \bmod i$。易知
>
> $$
> \begin{align}
> t \times i+k &\equiv 0 \pmod p \\\\
> k &\equiv -t \times i \pmod p
> \end{align}
> $$
>
> 等式两边同时除以$ik$，得
>
> $$
> \begin{align}
> i^{-1} &\equiv -t \times k^{-1} \pmod p \\\\
> i^{-1} &\equiv -p/i \times (p \bmod i)^{-1} \pmod p
> \end{align}
> $$
>
> 即
>
> $$
> i^{-1} \equiv (p-p/i) \times (p \bmod i)^{-1} \pmod p
> $$

由此得证。

```cpp
void get_inv() {
    inv[1] = 1;
    for (int i = 2; i < MOD; ++i) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
}
```

---

### 求$b \mid a$时${a \over b}$在模$n$意义下的值

当$b \mid a$时，有

$$
{a \over b} \bmod n=a \bmod (bn) / b
$$

证明如下：

> 设
>
> $$
> {a \over b} \bmod n = x
> $$
>
> 则有
>
> $$
> \begin{align}
> {a \over b}&=kn+x \\\\
> a&=kbn+bx
> \end{align}
> $$
>
> 因为$0 \le x \lt n$，所以
>
> $$
> \begin{align}
> a \bmod (bn)&=bx \\\\
> x&=a \bmod (bn) / b
> \end{align}
> $$

由此得证。