歐拉函數的用處,在于[歐拉定理]。"歐拉定理"指的是:
> 如果兩個正整數a和n互質,則n的歐拉函數 φ(n) 可以讓下面的等式成立:
>
> 
也就是說,a的φ(n)次方被n除的余數為1。或者說,a的φ(n)次方減去1,可以被n整除。比如,3和7互質,而7的歐拉函數φ(7)等于6,所以3的6次方(729)減去1,可以被7整除(728/7=104)。
歐拉定理的證明比較復雜,這里就省略了。我們只要記住它的結論就行了。
歐拉定理可以大大簡化某些運算。比如,7和10互質,根據歐拉定理,

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

因此,7的任意次方的個位數(例如7的222次方),心算就可以算出來。
歐拉定理有一個特殊情況。
> 假設正整數a與質數p互質,因為質數p的φ(p)等于p-1,則歐拉定理可以寫成
>
> 
這就是著名的[費馬小定理](http://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86)。它是歐拉定理的特例。
歐拉定理是RSA算法的核心。理解了這個定理,就可以理解RSA。