数论11_欧拉定理

吴老师

2026-08-23 15:02:20

发布于：广东

7阅读

0回复

0点赞

11 欧拉定理

学习目标

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

说出欧拉定理的条件和结论；
理解“与 $n$ 互质的剩余类”是什么；
理解为什么把所有互质剩余类乘上 $a$ 后只是重新排列；
一步一步证明欧拉定理；
理解欧拉定理与费马小定理的关系；
理解欧拉定理怎样得到一种逆元公式。

1. 欧拉定理

如果：

$\gcd(a,n)=1$

那么：

$\boxed{a^{\varphi(n)}\equiv1\pmod n}$

这就是欧拉定理。

其中：

$\varphi(n)$

表示与 $n$ 互质的剩余类数量。

2. 先找出所有与 $n$ 互质的剩余类

例如：

$n=10$

在：

$1,2,\dots,10$

中与 10 互质的是：

$1,3,7,9$

所以：

$\varphi(10)=4$

一般地，把模 $n$ 下所有与 $n$ 互质的剩余类代表记成：

$r_1,r_2,\dots,r_{\varphi(n)}$

它们满足：

$\gcd(r_i,n)=1$

并且任意两个不同的 $r_i,r_j$ 在模 $n$ 下不同余。

3. 把每一个 $r_i$ 都乘上 $a$

考虑：

$ar_1,ar_2,\dots,ar_{\varphi(n)}$

我们想证明：

它们模 $n$ 后，仍然只是原来这些互质剩余类的一次重新排列。

要证明这一点，需要完成两件事：

每个 $ar_i$ 仍然与 $n$ 互质；
不同的 $r_i,r_j$ 乘上 $a$ 后不会变成同一个剩余类。

4. 为什么 $ar_i$ 仍然与 $n$ 互质

已经知道：

$\gcd(a,n)=1$

并且：

$\gcd(r_i,n)=1$

根据裴蜀定理，由：

$\gcd(a,n)=1$

可知存在整数 $u,v$ ，使：

$au+nv=1$

两边乘 $r_i$ ：

$ar_i u+nr_i v=r_i$

现在设 $d$ 是 $ar_i$ 与 $n$ 的任意公共因子。

那么：

$d\mid ar_i$

并且：

$d\mid n$

所以：

$d\mid ar_i u$

同时：

$d\mid nr_i v$

因此：

$d\mid(ar_i u+nr_i v)$

而：

$ar_i u+nr_i v=r_i$

所以：

$d\mid r_i$

现在 $d$ 同时整除 $r_i$ 和 $n$ 。

但：

$\gcd(r_i,n)=1$

所以只能：

$d=1$

因此：

$\boxed{\gcd(ar_i,n)=1}$

也就是说：

每一个 $ar_i$ 模 $n$ 后仍然属于“与 $n$ 互质的剩余类”。

5. 为什么不会出现两个相同的剩余类

假设：

$ar_i\equiv ar_j\pmod n$

因为：

$\gcd(a,n)=1$

所以 $a$ 在模 $n$ 下存在逆元 $a^{-1}$ 。

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

$a^{-1}ar_i\equiv a^{-1}ar_j\pmod n$

于是：

$r_i\equiv r_j\pmod n$

但 $r_i,r_j$ 本来就是不同的剩余类代表。

所以只有在：

$i=j$

时才可能成立。

因此：

乘上 $a$ 后，不会有两个不同的互质剩余类变成同一个。

6. 为什么这就说明只是重新排列

原来一共有：

$\varphi(n)$

个与 $n$ 互质的剩余类。

乘上 $a$ 后：

每一个结果仍然与 $n$ 互质；
这些结果两两不同。

所以我们又得到了 $\varphi(n)$ 个互不相同的互质剩余类。

而模 $n$ 下这样的剩余类总共也只有 $\varphi(n)$ 个。

因此：

$ar_1,ar_2,\dots,ar_{\varphi(n)}$

模 $n$ 后一定只是：

$r_1,r_2,\dots,r_{\varphi(n)}$

的一次重新排列。

7. 把所有数乘起来

既然两边只是顺序不同，那么乘积同余：

$(ar_1)(ar_2)\cdots(ar_{\varphi(n)})\equiv r_1r_2\cdots r_{\varphi(n)}\pmod n$

左边有 $\varphi(n)$ 个因子 $a$ ，所以：

$a^{\varphi(n)}r_1r_2\cdots r_{\varphi(n)}\equiv r_1r_2\cdots r_{\varphi(n)}\pmod n$

令：

$P=r_1r_2\cdots r_{\varphi(n)}$

得到：

$a^{\varphi(n)}P\equiv P\pmod n$

8. 为什么可以消掉 $P$

每个 $r_i$ 都与 $n$ 互质，所以每个 $r_i$ 在模 $n$ 下都存在逆元：

$r_i^{-1}$

也就是说：

$r_ir_i^{-1}\equiv1\pmod n$

把所有这些同余式相乘：

$(r_1r_2\cdots r_{\varphi(n)})(r_1^{-1}r_2^{-1}\cdots r_{\varphi(n)}^{-1})\equiv1\pmod n$

而：

$P=r_1r_2\cdots r_{\varphi(n)}$

所以：

$r_1^{-1}r_2^{-1}\cdots r_{\varphi(n)}^{-1}$

就是 $P$ 在模 $n$ 下的一个逆元。

因此 $P$ 可以在模 $n$ 下消去。

从：

$a^{\varphi(n)}P\equiv P\pmod n$

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

$a^{\varphi(n)}\equiv1\pmod n$

所以：

$\boxed{a^{\varphi(n)}\equiv1\pmod n}$

欧拉定理得证。

9. 一个具体例子

取：

$a=3,\qquad n=10$

因为：

$\gcd(3,10)=1$

并且：

$\varphi(10)=4$

所以：

$3^4\equiv1\pmod{10}$

而：

$3^4=81$

所以：

$81\equiv1\pmod{10}$

正确。

10. 欧拉定理怎样得到逆元公式

欧拉定理：

$a^{\varphi(n)}\equiv1\pmod n$

可以写成：

$a\cdot a^{\varphi(n)-1}\equiv1\pmod n$

根据逆元的定义：

$a^{\varphi(n)-1}$

就是 $a$ 在模 $n$ 下的一个逆元代表。

所以：

$\boxed{a^{-1}\equiv a^{\varphi(n)-1}\pmod n}$

前提仍然是：

$\gcd(a,n)=1$

11. 欧拉定理和费马小定理是什么关系

如果 $p$ 是素数，那么：

$\varphi(p)=p-1$

把 $n=p$ 代入欧拉定理：

$a^{\varphi(p)}\equiv1\pmod p$

得到：

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

这正是费马小定理。

所以：

费马小定理是欧拉定理在模数为素数时的特殊情况。

12. 小练习

练习 1

为什么欧拉定理要求：

$\gcd(a,n)=1$

练习 2

已知：

$\varphi(9)=6$

验证：

$2^6\equiv1\pmod9$

练习 3

为什么从：

$ar_i\equiv ar_j\pmod n$

可以推出：

$r_i\equiv r_j\pmod n$

练习 4

为什么费马小定理是欧拉定理的特殊情况？

13. 答案

练习 1

因为证明中需要 $a$ 存在逆元，并且需要乘上 $a$ 后仍然在互质剩余类之间形成一一对应。

练习 2

$2^6=64=9\times7+1$

所以：

$2^6\equiv1\pmod9$

练习 3

因为 $a$ 有逆元。两边同时乘 $a^{-1}$ 即可消去 $a$ 。

练习 4

因为素数 $p$ 满足：

$\varphi(p)=p-1$

代入欧拉定理就得到费马小定理。

有帮助，赞一个

去预览

0/2000

这里空空如也

11 欧拉定理

学习目标

1. 欧拉定理

2. 先找出所有与 nnn 互质的剩余类

3. 把每一个 rir_iri​ 都乘上 aaa

4. 为什么 ariar_iari​ 仍然与 nnn 互质

5. 为什么不会出现两个相同的剩余类

6. 为什么这就说明只是重新排列

7. 把所有数乘起来

8. 为什么可以消掉 PPP

9. 一个具体例子

10. 欧拉定理怎样得到逆元公式

11. 欧拉定理和费马小定理是什么关系

12. 小练习

练习 1

练习 2

练习 3

练习 4

13. 答案

练习 1

练习 2

练习 3

练习 4

热门讨论

2. 先找出所有与 $n$ 互质的剩余类

3. 把每一个 $r_i$ 都乘上 $a$

4. 为什么 $ar_i$ 仍然与 $n$ 互质

8. 为什么可以消掉 $P$