歐拉定理

瑞士數學家歐拉 (Leonhard Euler 1707-1783)

(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

 

我們以歐拉 j 函數 (Euler Totient Function) j(n) 來表示不大於 n 且與 n 互素的整數個數。詳見《歐拉函數》一文。

現設 (a,m) = 1,則有 aj(m) = 1 (mod m),這便是著名的歐拉定理 (Euler Theorem)。這定理在素數論 (Prime Number Theory) 中佔有相當的地位,不下於費馬小定理 (Fermat's Little Theorem) ,在很多定理的證明上或 RSA公鑰密碼 中都有利用這定理。其實我們可以視歐拉定理為費馬小定理的一個推廣,因為對於所有素數 p, j(p) = p - 1。費馬小定理針對以素數為模的同餘 (Congruence),而歐拉定理則把模推廣至任何的正整數。