欧拉定理 (数论)

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

在数论中，欧拉定理（也称费马-欧拉定理或欧拉${\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.