模逆元

问题描述

如果$a*b \equiv 1 \pmod n$，$\equiv$符号表示$a*b \% n=1$，$\%$表示模运算，模运算就是取余，$x\%y=x-\lfloor\frac{x}{y}\rfloor*y$，例如$5\%3=2$

则$a,b$在模$n$情况下互为模逆元，模逆元可以记为$a^{-1}$，即$a^{-1} \equiv b \pmod n,b^{-1} \equiv a \pmod n$

$a$在模$n$的情况下，存在模逆元的充要条件是$gcd(a,n)=1$，$gcd(a,n)$表示$a$和$n$的最大公约数，即$a$与$n$互素。

简单描述一下，非正式的证明：

• 必要条件证明：如果$a$与$n$不互素，设$gcd(a,n)=d \gt 1$，对于任意的整数$b$，$a*b \pmod n \equiv a*b - k*n \pmod n$，其中$0 \le a*b - k*n \lt n$，由于$a$是$d$的倍数，$n$也是$d$的倍数，因此$a*b - k*n$也是$d$的倍数，即对任意的$b$，$a*b \pmod n$整除$d,d>1$，与存在模拟元的前提矛盾，所以若存在$a*b \equiv 1 \pmod n$，则$a,n$必须互素

• 充分条件证明：如果$a$与$n$互素，我们首先证明$a*k$在$1 \le k \le n-1$时，任意两个不同的$k$乘以$a$模$n$必定不相等，且不为$0$，

  • 首先若要$a*k \equiv 0\pmod n$，则$a*k$是$n$的倍数，由于$gcd(a,n)=1$，则$k$必须是$n$的倍数，与$1 \le k \le n-1$矛盾，因此$a*k \ne 0\pmod n$
  • 其次证明对于任意两个$k_1,k_2$，$a*k_1 \ne a*k_2 \pmod n$：假设$a*k_1 \equiv a*k_2 \pmod n$，则意味着$a*k_1 - a*k_2 = a*(k_1-k_2) \equiv 0 \pmod n$，而$1 \le k_1,k_2 \le n-1$，所以$1 \le |k_1-k_2| \lt n-1$，根据上面的证明，在$1 \le k \le n-1$时，$a*k \ne 0\pmod n$，与假设矛盾，得证

  由上可知$a*k$模$n$在$1 \le k \le n-1$时，结果集合为$\{1,2,3,...,n-1\}$，因此必定存在某个$k$，使得$a*k \equiv 1 \pmod n$

求解模拟元的方法

方法1-欧拉定理

$a^{-1}=a^{\phi(n)-1}$，$\phi(n)$表示小于$n$且与$n$互素的数的个数

证明：
设$\{a_1,a_2,...,a_{\phi(n)}\}$为所有与$n$互素的数，由上面模逆元存在性的证明可知：

$a*a_i \ne a*a_j \pmod n (1\le i,j\le \phi(n), i \ne j)$，

因此：$\{a*a_1,a*a_2,...,a*a_{\phi(n)}\} \pmod n$ 每个都不相等，且与$n$互素

即：两个集合在模$n$的情况下完全相等，$\{a*a_1,a*a_2,...,a*a_{\phi(n)}\} = \{a_1,a_2,...,a_{\phi(n)}\} \pmod n$

可以得出：$a*a_1*a*a_2*...*a*a_{\phi(n)} \equiv a_1*a_2*...*a_{\phi(n)} \pmod n$

$a^{\phi(n)}*a_1*a_2*...*a_{\phi(n)} \equiv a_1*a_2*...*a_{\phi(n)} \pmod n$

$a^{\phi(n)}*a_1*a_2*...*a_{\phi(n)} - a_1*a_2*...*a_{\phi(n)} \equiv 0 \pmod n$

$(a^{\phi(n)}-1) * a_1*a_2*...*a_{\phi(n)} \equiv 0 \pmod n$

由于$(a^{\phi(n)}-1) \lt n$且$a_i$与$n$互素，因此$(a^{\phi(n)}-1)=0$，即$a^{\phi(n)}=1=a*a^{\phi(n)-1}$，所以$a^{\phi(n)-1}$是$a$的模逆元，如果$n$是素数，则$a^{\phi(n)-1}=a^{n-2}$

方法2-扩展欧几里得算法

关于扩展欧几里得算法的详细介绍，可以参考这篇文章：最大公约数：扩展欧几里得算法

通过扩展欧几里得算法，可以求得$ax+ny=gcd(a,n)=1, ax+ny \equiv ax \equiv 1 \pmod n$，求得的$x$即为$a$的模拟元