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)$.
逆元这个概念算是老熟人了；它将模意义下的除法转化为乘法。
求逆元的常见方法：扩展欧几里得算法，欧拉定理，费马小定理。这些方法在接下来都会进行介绍。