大家對費馬小定理都非常熟悉，它是說如果p為素數，則對於任意的正整數a都有p整除a^p-a。到了1736年，歐拉給出了費馬小定理的嚴格證明。而到了1760年，歐拉又給出了費馬小定理的重要推廣。他首先考慮了小於給定正整數n且與n互素的正整數個數，高斯為此專門引入了一個記號Φ(n)，稱之為歐拉函數。
使用這個新的函數，歐拉證明了如果a和n互素，則n整除a^Φ(n)-1。注意到當n為素數p時，每個小於p的正整數都和p互素，即Φ(n)=p-1，此時歐拉推廣的定理變成了對每個與p互素的a，均有p整除a^(p-1)-1當然也整除a^p-a。如果a和p不互素，即p整除a，顯然有p整除a^p-a。其實這就是費馬小定理。
令人驚奇的是，歐拉這個定理的證明非常簡單，相比之下他的發現和提出要難的多。接下來我們來看看他的證明過程。
首先假設a和n互素，並且在1,2,3,…,n中和n互素的數為R1,R2,R3,…,Rk，則歐拉函數Φ(n)=k。接著歐拉又考慮k個數aR1,aR2,aR3,…,aRk除以n後所得的餘數。一方面a和n互素，Ri也分別和n互素，所以他們的餘數也和n互素。另一方面，如果aRi和aRj除以n所得的餘數相同，則n必整除他們之差，即n整除Ri-Rj，而這是不可能的。所以aR1,aR2,aR3,…,aRk除以n所得的餘數不僅和n互素且兩兩不同。因此餘數就是R1,R2,R3,…,Rk的某一個排列。所以n整除下面乘積之差：
又因為R1R2R3…Rk也和n互素，因此n整除a^k-1。至此就證明了歐拉對於費馬小定理的擴展。