欧拉定理 (数论)

此條目已列出參考文獻，但因為沒有文內引註而使來源仍然不明。 (2014年11月8日) 请加上合适的文內引註来改善这篇条目。

提示：此条目的主题不是欧拉定理 (几何)或欧拉方程。

在数论中，欧拉定理（也称费马-欧拉定理或欧拉${\displaystyle {\varphi }}$函数定理）是一个关于同余的性质。欧拉定理表明，若${\displaystyle n,a}$为正整数，且${\displaystyle n,a}$互素（即${\displaystyle \gcd(a,n)=1}$），则

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$

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

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

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

使用本定理可大程度地简化幂的模运算。比如计算${\displaystyle 7^{222}}$的个位数時，可將此命題視為求${\displaystyle 7^{222}}$被10除的余数：因7和10互質，且${\displaystyle \varphi (10)=4}$，故由欧拉定理可知${\displaystyle 7^{4}\equiv 1{\pmod {10}}}$。所以${\displaystyle 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}}}$。

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

${\displaystyle a^{x}\equiv a^{y}{\pmod {n}}}$，其中${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$。

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

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

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$或

${\displaystyle a^{n}\equiv a{\pmod {n}}}$

这就是费马小定理。

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

• 潘承洞 潘承彪. 《初等数论》. 北京大学出版社. 2003. ISBN 9787301060759. 
• Albert H. Beiler 著，谈祥柏 译. 《数论妙趣--数学女王的盛情款待》. 上海教育出版社. 1998. ISBN 9787532054732.