数论06_乘法逆元

吴老师

2026-08-23 13:31:13

发布于：广东

5阅读

0回复

0点赞

06 乘法逆元

学习目标

学完这一节，你应该能够：

理解乘法逆元和普通数学中“倒数”的联系与区别；
掌握乘法逆元的定义；
理解逆元存在的充要条件；
理解为什么逆元在模 $m$ 意义下唯一；
理解为什么同一个逆元可以有无穷多个整数代表；
理解模运算中的“除法”为什么本质上是“乘逆元”。

1. 从普通数学中的倒数开始

普通数学中：

$3\times\frac13=1$

所以我们说 $\frac13$ 是 3 的倒数。

这里真正重要的并不是“倒数通常写成分数”，而是：

一个数乘上它的倒数以后，结果等于 1。

一般地，对于非零数 $a$ ，如果一个数 $x$ 满足：

$ax=1$

那么 $x$ 就起到了 $a$ 的倒数的作用。

2. 到了模运算中，怎样模仿“倒数”

在模运算中，我们也希望寻找一个整数 $x$ ，使 $a$ 与它相乘以后“得到 1”。

但是这里的“得到 1”不要求普通意义下：

$ax=1$

而是要求：

$ax\equiv1\pmod m$

也就是说， $ax$ 和 1 除以 $m$ 后余数相同。

例如在模 7 下：

$3\times5=15$

普通意义下：

$15\ne1$

但是：

$15-1=14$

而：

$7\mid14$

根据同余的定义：

$15\equiv1\pmod7$

因此：

$3\times5\equiv1\pmod7$

这时，5 在模 7 的意义下，就起到了普通数学中“倒数”类似的作用。

3. 乘法逆元的定义

给定整数 $a$ 和模数 $m$ 。

如果存在整数 $x$ ，满足：

$ax\equiv1\pmod m$

那么称 $x$ 是 $a$ 在模 $m$ 下的一个乘法逆元。

通常写成：

$a^{-1}\equiv x\pmod m$

例如：

$3\times5=15\equiv1\pmod7$

所以：

$\boxed{3^{-1}\equiv5\pmod7}$

这里的 $a^{-1}$ 是“模意义下的逆元”的记号，不是在说普通分数 $\frac1a$ 。

例如：

$3^{-1}\equiv5\pmod7$

并不表示普通数学中：

$\frac13=5$

它只表示：

$3\times5\equiv1\pmod7$

4. 并不是所有数都有逆元

尝试寻找 2 在模 6 下的逆元。

我们需要找到整数 $x$ ，使：

$2x\equiv1\pmod6$

但是 $2x$ 一定是偶数。

偶数除以 6 的余数只可能是：

$0,2,4$

不可能余 1。

所以 2 在模 6 下没有逆元。

那么，一个数什么时候才有逆元？

结论是：

$\boxed{a\text{ 在模 }m\text{ 下存在逆元}\iff\gcd(a,m)=1}$

“当且仅当”意味着两个方向都成立，所以我们分别证明。

5. 如果 $\gcd(a,m)=1$ ，为什么逆元一定存在

假设：

$\gcd(a,m)=1$

根据上一章的裴蜀定理，一定存在整数 $x,y$ ，使：

$ax+my=1$

把 $my$ 移到右边：

$ax-1=-my$

因为 $-my$ 是 $m$ 的整数倍，所以：

$m\mid(ax-1)$

根据同余的定义：

$m\mid(A-B)\iff A\equiv B\pmod m$

令 $A=ax$ 、 $B=1$ ，得到：

$ax\equiv1\pmod m$

这正好符合乘法逆元的定义。

因此：

$\boxed{\gcd(a,m)=1\Rightarrow a\text{ 在模 }m\text{ 下存在逆元}}$

这里裴蜀定理只负责告诉我们：

这样的整数 $x,y$ 一定存在。

这一章只讨论“为什么存在”，暂时不讨论怎样把 $x,y$ 具体算出来。

6. 如果逆元存在，为什么一定有 $\gcd(a,m)=1$

现在反过来。

假设 $a$ 在模 $m$ 下存在逆元。

那么一定存在整数 $x$ ，使：

$ax\equiv1\pmod m$

根据同余的定义：

$m\mid(ax-1)$

所以一定存在整数 $k$ ，使：

$ax-1=km$

移项：

$ax-km=1$

令：

$y=-k$

得到：

$ax+my=1$

现在设：

$d=\gcd(a,m)$

因为：

$d\mid a$

所以：

$d\mid ax$

又因为：

$d\mid m$

所以：

$d\mid my$

因此：

$d\mid(ax+my)$

而：

$ax+my=1$

所以：

$d\mid1$

正的最大公约数只能是 1，因此：

$d=1$

也就是：

$\gcd(a,m)=1$

所以：

$\boxed{a\text{ 在模 }m\text{ 下存在逆元}\Rightarrow\gcd(a,m)=1}$

7. 两个方向合起来

前面已经证明：

$\gcd(a,m)=1\Rightarrow a\text{ 在模 }m\text{ 下存在逆元}$

同时又证明：

$a\text{ 在模 }m\text{ 下存在逆元}\Rightarrow\gcd(a,m)=1$

因此：

$\boxed{a\text{ 在模 }m\text{ 下存在逆元}\iff\gcd(a,m)=1}$

也就是说：

$a$ 在模 $m$ 下存在乘法逆元，当且仅当 $a$ 与 $m$ 互质。

8. 为什么逆元在模 $m$ 意义下唯一

假设 $x_1,x_2$ 都是 $a$ 在模 $m$ 下的逆元。

那么：

$ax_1\equiv1\pmod m$

并且：

$ax_2\equiv1\pmod m$

所以：

$ax_1\equiv ax_2\pmod m$

根据同余的减法性质：

$a(x_1-x_2)\equiv0\pmod m$

也就是：

$m\mid a(x_1-x_2)$

这里不能直接说“把 $a$ 约掉”。

因为我们已经知道 $a$ 有逆元，所以设它的一个逆元为 $a^{-1}$ 。

从：

$a(x_1-x_2)\equiv0\pmod m$

两边同时乘 $a^{-1}$ ：

$a^{-1}a(x_1-x_2)\equiv a^{-1}\cdot0\pmod m$

因为：

$a^{-1}a\equiv1\pmod m$

所以：

$x_1-x_2\equiv0\pmod m$

因此：

$\boxed{x_1\equiv x_2\pmod m}$

所以：

逆元在模 $m$ 意义下是唯一的。

9. 为什么整数形式的逆元又有无穷多个

考虑：

$3x\equiv1\pmod7$

我们知道：

$x=5$

满足条件。

但是：

$x=12$

也满足，因为：

$12\equiv5\pmod7$

同样：

$19\equiv5\pmod7$

$26\equiv5\pmod7$

所以：

$5,12,19,26,\dots$

都可以作为整数解。

它们之间都相差 7 的整数倍：

$12=5+7$

$19=5+2\times7$

$26=5+3\times7$

所有整数解都可以写成：

$x=5+7k$

其中 $k$ 是整数。

所以：

整数代表可以有无穷多个，但它们都属于同一个模 7 的剩余类。

真正唯一的是逆元所在的剩余类。

10. 为什么限定 $0\le x<m$ 后只有一个

模 $m$ 的每一个剩余类，在：

$0\le x<m$

中恰好有一个代表。

所以如果逆元存在，那么在这个范围中恰好只有一个整数满足：

$ax\equiv1\pmod m$

例如：

$3^{-1}\equiv5\pmod7$

虽然：

$5,12,19,26,\dots$

都代表同一个逆元，但在：

$0\le x<7$

中只有：

$x=5$

11. 模运算中的“除法”

普通数学中，如果：

$ax=b$

并且 $a\ne0$ ，那么：

$x=\frac ba$

也可以理解成：

$x=b\cdot\frac1a$

所以普通数学中的“除以 $a$ ”，可以理解为“乘以 $a$ 的倒数”。

模运算中也采用类似思想。

假设：

$ax\equiv b\pmod m$

并且 $a$ 在模 $m$ 下存在逆元 $a^{-1}$ 。

根据同余的乘法性质，两边同时乘 $a^{-1}$ ：

$a^{-1}ax\equiv a^{-1}b\pmod m$

因为：

$a^{-1}a\equiv1\pmod m$

所以：

$x\equiv ba^{-1}\pmod m$

因此：

$\boxed{x\equiv b\cdot a^{-1}\pmod m}$

所以模运算中所谓的“除以 $a$ ”，本质上是：

乘上 $a$ 的逆元。

但前提一定是：

$\gcd(a,m)=1$

否则 $a$ 没有逆元，也就不能用这种方式“除”。

12. 小练习

练习 1

求 2 在模 5 下的逆元。

练习 2

求 4 在模 7 下的逆元。

练习 3

2 在模 6 下有逆元吗？

练习 4

为什么逆元“模 $m$ 唯一”，但整数代表可以有无穷多个？

13. 答案

练习 1

因为：

$2\times3=6\equiv1\pmod5$

所以：

$2^{-1}\equiv3\pmod5$

练习 2

因为：

$4\times2=8\equiv1\pmod7$

所以：

$4^{-1}\equiv2\pmod7$

练习 3

没有，因为：

$\gcd(2,6)=2\ne1$

练习 4

因为所有整数代表彼此相差 $m$ 的整数倍，所以它们虽然是不同整数，却属于同一个模 $m$ 的剩余类。

有帮助，赞一个

去预览

0/2000

这里空空如也

06 乘法逆元

学习目标

1. 从普通数学中的倒数开始

2. 到了模运算中，怎样模仿“倒数”

3. 乘法逆元的定义

4. 并不是所有数都有逆元

5. 如果 gcd⁡(a,m)=1\gcd(a,m)=1gcd(a,m)=1，为什么逆元一定存在

6. 如果逆元存在，为什么一定有 gcd⁡(a,m)=1\gcd(a,m)=1gcd(a,m)=1

7. 两个方向合起来

8. 为什么逆元在模 mmm 意义下唯一

9. 为什么整数形式的逆元又有无穷多个

10. 为什么限定 0≤x<m0\le x<m0≤x<m 后只有一个

11. 模运算中的“除法”

12. 小练习

练习 1

练习 2

练习 3

练习 4

13. 答案

练习 1

练习 2

练习 3

练习 4

热门讨论

5. 如果 $\gcd(a,m)=1$ ，为什么逆元一定存在

6. 如果逆元存在，为什么一定有 $\gcd(a,m)=1$

8. 为什么逆元在模 $m$ 意义下唯一

10. 为什么限定 $0\le x<m$ 后只有一个