欧拉定理

最新推荐文章于 2023-08-16 18:31:58 发布

liu_jiangwen

最新推荐文章于 2023-08-16 18:31:58 发布

阅读量1k

点赞数

分类专栏： ACM竞赛算法原理数论

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/liu_jiangwen/article/details/81587934

版权

ACM竞赛同时被 3 个专栏收录

7 篇文章

订阅专栏

4 篇文章

订阅专栏

2 篇文章

订阅专栏

前置技能
- 剩余系和剩余类
  - 定义 $1$ (剩余类)：设 $m$ 为自然数，称为模，所有对 $m$ 同余的整数所组成的集合叫做模 $m$ 的一个剩余类，如果一个剩余类中的数和模数 $m$ 是互素的，那么就称它为模 $m$ 的一个互素剩余类。
  - 定义 $2$ (剩余系)：在每一个剩余系 $K_\gamma(0 \leq \gamma \leq m - 1)$ 中任取一数 $a_\gamma$ ，我们把 $a_0, a_1, \dots , a_{m - 1}$ 叫做模 $m$ 的一个完全剩余系；在每一个互素剩余类 $K_\gamma（0 \leq \gamma \leq m - 1, (\gamma, m) = 1）$ 中任取一数 $a_\gamma$ ，则所有的 $a_\gamma$ 称为模 $m$ 的一个互素（简化）剩余系。
  - 定理 $1$ ：设 $m$ 为自然数， $K, l$ 为任意数且 $(K, m) = 1$ ，则当 $x$ 通过 $m$ 的完全系时， $Kx + l$ 也通过 $m$ 的一个完全系。
  - 定理 $2$ ：设 $m$ 为自然数， $K, l$ 为任意数且 $(K, m) = 1$ ，则当 $x$ 通过 $m$ 的简化系时， $Kx + lm$ 也通过 $m$ 的一个简化系。
欧拉定理表达式
$a^{φ (m)} \equiv 1 (m o d m) ((a, m) = 1)$ $a^{\varphi(m)}\equiv 1\;(mod\;m)\;\;((a, m) = 1)$
证明
欧拉定理的证明需要用到的是上述定理中的定理2。
设
$x 1, x 2, \dots, x φ (m)$ $x_1, x_2, \dots , x_{\varphi(m)}$ 是模 $m$ 的一个简化系，因为 $(a, m) =1$ ，由定理2可知 $a x 1, a x 2, \dots, a x φ (m)$ $ax_1, ax_2, \dots , ax_{\varphi(m)}$ 也是通过模 $m$ 的一个简化系。所以有 $(a x_{1}) (a x_{2}) \dots (a x_{φ (m)}) \equiv x_{1} x_{2} \dots x_{φ (m)} (m o d m)$ $(ax_1)(ax_2)\dots(ax_{\varphi(m)}) \equiv x_1x_2\dots x_{\varphi(m)}\;\;(mod\;m)$ 因为 $(x 1 x 2 \dots x φ (m), m) = 1$ $(x_1x_2\dots x_{\varphi(m)}, m) = 1$ 所以我们得到 $a φ (m) \equiv 1 (m o d m)$ $a^{\varphi(m)}\equiv 1\;\;(mod \; m)$ 证毕.

评论

被折叠的条评论为什么被折叠?

到【灌水乐园】发言

查看更多评论

添加红包

成就一亿技术人!

hope_wisdom

发出的红包

实付元

使用余额支付

点击重新获取

扫码支付

钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。