欧拉定理 (数论)

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

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

其中 $\varphi(n)$ 为欧拉函数， $\mod n$ 为同余关系。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。

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

[编辑] 例子

首先看一个基本的例子。令 $a = 3$ ， $n = 5$ ，这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4，所以 $\varphi(5)=4$ 。计算： $a^{\varphi(n)} = 3^4 = 81$ ，而 $81 \equiv 80 + 1 \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)$ ：

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

[编辑] 证明

一般的证明中会用到“所有与 $n$ 互素的同余类构成一个群”的性质，也就是说，设 $\left\{ \overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}} \right\}$ 是比 $n$ 小的正整数中所有与 $n$ 互素的数对应的同余类组成的集合（这个集合也称为模n 的简化剩余系）。这些同余类构成一个群，称为整数模n乘法群。所以当对这些数进行变换 $\pi_a : \overline{a_i} \longmapsto \overline{a \cdot a_i} = \overline{a} \cdot \overline{a_i}$ 的时候（ $a$ 是和 $n$ 互素的一个数，从而也属于某个同余类），变换所得的同余类集合仍然是原来的 $\overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}}$ 。即是说，集合 $\left\{ \overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}} \right\}$ 和 $\left\{ \overline{a a_1}, \overline{a a_2}, \cdots , \overline{a a_{\varphi(n)}} \right\}$ 相同。因此， $a^{\varphi(n)} a_1 a_2 \cdots a_{\varphi(n)} \equiv (a a_1)(a a_2) \cdots (a a_{\varphi(n)}) \equiv a_1 a_2 \cdots a_{\varphi(n)} \pmod n$ 。从而 $a^{\varphi(n)} \equiv 1 \pmod n$