跳至內容

歐拉定理 (數論)

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

數論中,歐拉定理(也稱費馬-歐拉定理歐拉函數定理)是一個關於同餘的性質。歐拉定理表明,若為正整數,且互質(即),則

與1在模n下同餘φ(n)為歐拉函數。歐拉定理得名於瑞士數學家萊昂哈德·歐拉

歐拉定理實際上是費馬小定理的推廣。

例子

[編輯]

首先看一個基本的例子。令,此兩數為互質正整數。小於等於5的正整數中與5互質的數有4個(1、2、3和4),所以(詳情見歐拉函數)。計算:,與定理結果相符。

使用本定理可大程度地簡化冪的模運算。比如計算的個位數時,可將此命題視為求被10除的餘數:因7和10互質,且,故由歐拉定理可知。所以

一般在簡化冪的模運算的時候,當互質時,可對的指數取模

,其中

證明

[編輯]

一般的證明中會用到「所有與互質的同餘類構成一個」的性質,也就是說,設是比 小的正整數中所有與 互質的數對應的同餘類組成的集合(這個集合也稱為模n簡化剩餘系)。這些同餘類構成一個群,稱為整數模n乘法群。因為此群階為,所以

質數的時候,,所以歐拉定理變為:

這就是費馬小定理

參看

[編輯]

參考書籍

[編輯]
  • 潘承洞 潘承彪. 《初等数论》. 北京大學出版社. 2003. ISBN 9787301060759. 
  • Albert H. Beiler 著,談祥柏 譯. 《数论妙趣--数学女王的盛情款待》. 上海教育出版社. 1998. ISBN 9787532054732.