乘法逆元 — Lalande.

Multiplicative Inverse.

Definition. If for a given integer $b$ , there exists an integer $c$ such that $bc=1\mod{N}$ , we say that $b$ is invertible modulo $N$ , and call $c$ a multiplicative inverse of $b$ modulo $N$ .

The multiplicative inverse is NOT unique. For an invertible $b$ , if $c$ is an inverse of $b$ , every $x$ congruent with $c$ modulo $N$ is also an inverse of $b$ . ( $x\equiv c\mod{N}$ ). We use $b^{-1}$ to denote the inverse of $b$ that $b^{-1}\in\{1,2,...N-1\}$ .

Theorem. Let $b,N$ be integers, with $b\geq 1$ , and $N>1$ . Then $b$ is invertible modulo $N$ if and only if $b$ is relatively prime to $N$ . Note that integers $b,N$ are relatively prime (or coprime) means $\gcd(b,N)=1$ .

Therefore, for a prime $p$ , every $b\in \{1,2,...p-1\}$ is invertible modulo $p$ .

The above theorem could be proved by applying **Bezout's identity: ** it states that for every positive integer $a,b$ , there exists a pair of integers $\langle X,Y \rangle$ that $Xa+Yb=\gcd(a,b)$ .

Eureka moment!

逆元这个概念算是老熟人了；它将模意义下的除法转化为乘法。

求逆元的常见方法：扩展欧几里得算法，欧拉定理，费马小定理。这些方法在接下来都会进行介绍。