在數論中,歐拉定理(也稱費馬-歐拉定理或歐拉
函數定理)是一個關於同餘的性質。歐拉定理表明,若
為正整數,且
互質(即
),則
即
與1在模n下同餘;φ(n)為歐拉函數。歐拉定理得名於瑞士數學家萊昂哈德·歐拉。
歐拉定理實際上是費馬小定理的推廣。
首先看一個基本的例子。令
,
,此兩數為互質正整數。小於等於5的正整數中與5互質的數有4個(1、2、3和4),所以
(詳情見歐拉函數)。計算:
,與定理結果相符。
使用本定理可大程度地簡化冪的模運算。比如計算
的個位數時,可將此命題視為求
被10除的餘數:因7和10互質,且
,故由歐拉定理可知
。所以
。
一般在簡化冪的模運算的時候,當
和
互質時,可對
的指數取模
:
,其中
。
一般的證明中會用到「所有與
互質的同餘類構成一個群」的性質,也就是說,設
是比
小的正整數中所有與
互素的數對應的同餘類組成的集合(這個集合也稱為模n 的簡化剩餘系)。這些同餘類構成一個群,稱為整數模n乘法群。因為此群階為
,所以
。
當
是素數的時候,
,所以歐拉定理變為:
或
![{\displaystyle a^{n}\equiv a{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/578f207468d53d4691d91fa469583e2375107445)
這就是費馬小定理。
參考書籍[編輯]