# Notes on Multiplicative Inverse

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

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

$$a \times 1+b \times 0=a=(a, b)=1$$

\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 \times x_1+b \times y_1=b \times x_2+a \times y_2-a/b \times b \times y_2$$

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$的逆

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

$$\forall x \in Z, \; x^p \equiv x \pmod p$$

\begin{align} x^{p-1} &\equiv 1 \pmod p \\ x^{-1} &\equiv x^{p-2} \pmod p \end{align}

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

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

\begin{align} t \times i+k &\equiv 0 \pmod p \\ k &\equiv -t \times i \pmod p \end{align}

\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$$

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$意义下的值

$${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}

\begin{align} a \bmod (bn)&=bx \\ x&=a \bmod (bn) / b \end{align}

418 I'm a teapot