歐拉定理（數論）

在數論中，歐拉定理（也稱費馬-歐拉定理或歐拉 ${\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$ 。