「笔记」模运算的乘法逆元

Caleb

2023 年 03 月 02 日

807 次浏览

暂无评论

1898字数

学习笔记

# 定义

对于正整数 $a、x、n$ ，满足 $a·x \equiv 1 (\text{mod}\  n)$  则$x$是$a$的乘法逆元，即 $x \equiv a^{-1}(\text{mod}\ n)$ 。

# 存在性

### 结论

$a$ 存在 $\text{mod}\ n$ 的乘法逆元，当且仅当 $a$ 和 $n$ 互质。

### 证明：

**充分性（逆元->互质）**
假设 $a$ 和 $n$ 存在公因数 $p$，即  $\gcd(a,n)=p$ 。 设  $a=s*p\ \ \ \  n=t*p$ 。

由逆元的定义得到：

$$
(a*x) \mod n=1
$$

则

$$
(a*x-1) \mod n=0
$$

即

$$
(a*x-1) = k*n
$$

代入 $p$

$$
\begin{split}
(s*p*x-1) &= k*t*p\\
p*(s*x+k*t)&=1 \\
s*x+k*t&=\frac{1}{p}
\end{split}
$$

由于 $p、s、x、k、t$ 都是正整数，所以当且仅当 $p=1$ 时，表达式成立，即 $a$ 和 $n$ 互质。

**必要性（互质->逆元）**

因为

$$
\gcd{(a,n)} = \gcd {(n,a \text{mod}\ n)}
$$

以此递推，因为 $a$ 和 $n$ 互质，所以 $\gcd{(a,n)}=1$

$$
\begin{split}
\gcd{(a,n)} &= \gcd {(n,r_1)}\\
&=\gcd {(r_1,r_2)}\\
&=\gcd {(r_2,r_3)}\\
&...\\
&=1
\end{split}
$$

换种写法:

$$
\begin{split}
a &= k_1*n + r_1\\
n &= k_2*r_1 + r_2\\
r_1 &= k_3*r_2 + r_3\\
&...\\
r_{j-2} &= k_j*r_{j-1} + r_j\\
r_{j-1} &= k_{j+1}*r_j + 1
\end{split}
$$

从最后一条一条公式向上逆推，$1=r_{j-1} - k_{j+1}*r_j$。依次将 $r_{j-1}、r_{j-2}、...、r_1$ 代入式中，得到一个 $ax+ny=1$的式子，通过变形（加、减 $n$ 个 $a$ ）让 $x$>0 。 则得到 $x$ 是$a$ 关于 $\text{mod}\ n$ 的乘法逆元。

# 求法

### 方法一、 拓展欧几里得法

其实上文必要性的证明，就是求解逆元的过程，下面举一个例子。
求7对于模19的乘法逆元

**辗转相除:**

$$
\begin{split}
19 = 7 * 2 + 5\\
7 = 5 * 1 + 2\\
5 = 2 * 2 + 1\\
\end{split}
$$

**逆推：**

$$
\begin{align}
1& = 5 - 2 * 2\\
&=5 - 2*(7-5*1)=-7*2+3*5\\
&=-7*2 + 3*(19-7*2)=-7*8+3*19\\
&=7*(-8+19)+(3-7)*19=7*11-4*19
\end{align}
$$

所以7对于模19的乘法逆元是11。

### 方法二、 费马小定理

**费马小定理**：如果$n$是素数，$a$ 不能被 $n$ 整除，则 $a^{m-1} \equiv1(\text{mod}\ n)$。

$$
\begin{split}
a*a^{m-2}=s*n + t\\
a*(p*n+q)=s*n+t\\
\end{split}
$$

化简后可以得到