欧拉定理 (数论)

在数论中，欧拉定理（也称费马-欧拉定理或欧拉函数定理）是一个关于同余的性质。欧拉定理表明，若为正整数，且-{zh-hans:互素; zh-hant: 互質}-（即），则

即与1在模n下同余；φ(n)为欧拉函数。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。

欧拉定理实际上是费马小定理的推广。

 例子 
首先看一个基本的例子。令，，此两数為互質正整數。小於等於5的正整数中与5互質的数有4個（1、2、3和4），所以（详情见欧拉函数）。计算：，与定理结果相符。

使用本定理可大程度地简化幂的模运算。比如计算的个位数時，可將此命題視為求被10除的余数：因7和10互質，且，故由欧拉定理可知。所以。

一般在简化幂的模运算的时候，当和互質時，可对的指数取模：

，其中。

 证明 

一般的证明中会用到“所有与互質的同余类构成一个群”的性质，也就是说，设是比 小的正整数中所有与 互素的数对应的同余类组成的集合（这个集合也称为模n 的简化剩余系）。这些同余类构成一个群，称为整数模n乘法群。因为此群阶为，所以。

当是素数的时候，，所以欧拉定理变为：
或

这就是费马小定理。

 参看 
 初等数论
 欧拉定理
 欧拉函数
 同余
 群论
 RSA加密算法

 参考书籍 



Category:同余
Category:数论定理
Category:包含证明的条目
Category:莱昂哈德·欧拉