欧拉定理 (数论)

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

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

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

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

例子

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

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

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

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

证明

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