在数论中,欧拉定理(也称费马-欧拉定理或欧拉
函数定理)是一个关于同余的性质。欧拉定理表明,若
为正整数,且
互素(即
),则
即
与1在模n下同余;φ(n)为欧拉函数。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。
欧拉定理实际上是费马小定理的推广。
首先看一个基本的例子。令
,
,此两数为互素正整数。小于等于5的正整数中与5互素的数有4个(1、2、3和4),所以
(详情见欧拉函数)。计算:
,与定理结果相符。
使用本定理可大程度地简化幂的模运算。比如计算
的个位数时,可将此命题视为求
被10除的余数:因7和10互素,且
,故由欧拉定理可知
。所以
。
一般在简化幂的模运算的时候,当
和
互素时,可对
的指数取模
:
,其中
。
一般的证明中会用到“所有与
互素的同余类构成一个群”的性质,也就是说,设
是比
小的正整数中所有与
互素的数对应的同余类组成的集合(这个集合也称为模n 的简化剩余系)。这些同余类构成一个群,称为整数模n乘法群。因为此群阶为
,所以
。
当
是素数的时候,
,所以欧拉定理变为:
或
![{\displaystyle a^{n}\equiv a{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/578f207468d53d4691d91fa469583e2375107445)
这就是费马小定理。
参考书籍[编辑]