歐拉定理 (數論)

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