四、歐拉定理

歐拉函數(shù)的用處，在于[歐拉定理]。"歐拉定理"指的是：

如果兩個正整數(shù)a和n互質(zhì)，則n的歐拉函數(shù) φ(n) 可以讓下面的等式成立：

也就是說，a的φ(n)次方被n除的余數(shù)為1?；蛘哒f，a的φ(n)次方減去1，可以被n整除。比如，3和7互質(zhì)，而7的歐拉函數(shù)φ(7)等于6，所以3的6次方（729）減去1，可以被7整除（728/7=104）。

歐拉定理的證明比較復(fù)雜，這里就省略了。我們只要記住它的結(jié)論就行了。

歐拉定理可以大大簡化某些運算。比如，7和10互質(zhì)，根據(jù)歐拉定理，

已知 φ(10) 等于4，所以馬上得到7的4倍數(shù)次方的個位數(shù)肯定是1。

因此，7的任意次方的個位數(shù)（例如7的222次方），心算就可以算出來。

歐拉定理有一個特殊情況。

假設(shè)正整數(shù)a與質(zhì)數(shù)p互質(zhì)，因為質(zhì)數(shù)p的φ(p)等于p-1，則歐拉定理可以寫成

這就是著名的費馬小定理。它是歐拉定理的特例。

歐拉定理是RSA算法的核心。理解了這個定理，就可以理解RSA。