歐拉定理 (數論)

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