欧拉定理 (数论)

Template:NoteTA Template:No footnotesTemplate:Distinguish在数论中，欧拉定理（也称费马-欧拉定理或欧拉$\phi$函数定理）是一个关于同余的性质。欧拉定理表明，若$n,a$为正整数，且$n,a$-{zh-hans:互素; zh-hant: 互質}-（即$\gcd (a,n)=1$），则

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

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

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

例子

首先看一个基本的例子。令$a=3$，$n=5$，此两数為互質正整數。小於等於5的正整数中与5互質的数有4個（1、2、3和4），所以$\phi (5)=4$（详情见欧拉函数）。计算：$a^{\phi (n)}=3^4=81\equiv 1(\mathrm{mod}5)$，与定理结果相符。

使用本定理可大程度地简化幂的模运算。比如计算$7^{222}$的个位数時，可將此命題視為求$7^{222}$被10除的余数：因7和10互質，且$\phi (10)=4$，故由欧拉定理可知$7^4\equiv 1(\mathrm{mod}10)$。所以$7^{222}=7^{4\cdot 55+2}=(7^4{)}^{55}\cdot 7^2\equiv 1^{55}\cdot 7^2\equiv 49\equiv 9(\mathrm{mod}10)$。

一般在简化幂的模运算的时候，当$a$和$n$互質時，可对$a$的指数取模$\phi (n)$：

$a^x\equiv a^y(\mathrm{mod}n)$，其中$x\equiv y(\mathrm{mod}\phi (n))$。

证明

一般的证明中会用到“所有与$n$互質的同余类构成一个群”的性质，也就是说，设$\{\overline{a_1},\overline{a_2},\cdots ,\overline{a_{\phi (n)}}\}$是比$n$ 小的正整数中所有与$n$ 互素的数对应的同余类组成的集合（这个集合也称为模n 的简化剩余系）。这些同余类构成一个群，称为整数模n乘法群。因为此群阶为$\phi (n)$，所以$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$。

当$n$是素数的时候，$\phi (n)=n-1$，所以欧拉定理变为：

$a^{n-1}\equiv 1(\mathrm{mod}n)$或

$a^n\equiv a(\mathrm{mod}n)$

这就是费马小定理。

参看

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

参考书籍

• Template:Cite book
• Template:Cite book