在数论中，欧拉定理（也称费马-欧拉定理或欧拉{\varphi}函数定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a 互質}-（即\gcd(a,n)=1），则
a^{\varphi(n)} \equiv 1 \pmod n
即a^{\varphi(n)}与1在模n下同余；φ(n)为欧拉函数。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。
欧拉定理实际上是费马小定理的推广。
例子
首先看一个基本的例子。令a = 3，n = 5，此两数為互質正整數。小於等於5的正整数中与5互質的数有4個（1、2、3和4），所以\varphi(5)=4（详情见欧拉函数）。计算：a^{\varphi(n)} = 3^4 = 81 \equiv 1 \pmod{5} ，与定理结果相符。
使用本定理可大程度地简化幂的模运算。比如计算7^{222}的个位数時，可將此命題視為求7^{222}被10除的余数：因7和10互質，且\varphi(10)=4，故由欧拉定理可知7^4\equiv 1\pmod {10}。所以7^{222}= 7^{4\cdot 55+2}= (7^4)^{55}\cdot 7^2\equiv 1^{55}\cdot 7^2\equiv 49\equiv 9\pmod{10}。
一般在简化幂的模运算的时候，当a和n互質時，可对a的指数取模\varphi(n)：
a^x \equiv a^y \pmod n，其中x\equiv y \pmod {\varphi(n)}。
证明
一般的证明中会用到“所有与n互質的同余类构成一个群”的性质，也就是说，设\left\{ \overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}} \right\}是比n 小的正整数中所有与n 互素的数对应的同余类组成的集合（这个集合也称为模n 的简化剩余系）。这些同余类构成一个群，称为整数模n乘法群。因为此群阶为 \varphi(n)，所以a^{\varphi(n)} \equiv 1 \pmod n。
当n是素数的时候，\varphi(n) =n -1 ，所以欧拉定理变为：
:a^{n - 1} \equiv 1 \pmod n或
:a^{n} \equiv a \pmod n
这就是费马小定理。
参看
- 初等数论
- 欧拉定理
- 欧拉函数
- 同余
- 群论
- RSA加密算法
参考书籍
*
*
评论 (0)