上一篇我講了費馬小定理，後來聽人說它是歐拉定理的一種特殊情況。那麼本篇我就來學習一下歐拉定理。
歐拉函數
\Phi(n)是歐拉函數，其中n是正整數，\Phi(n)則表示小於n而與n互質的正整數的個數。比如\Phi(10)=4，因為小於10的正整數中只有{1,3,7,9}與10互質。
剩餘系
歐拉函數跟剩餘系的定義有直接關聯。下面是我的理解：
- 剩餘系：對於任何正整數n，非n的倍數的集合的子集就是n的剩餘系。
- 完全剩餘系：在包含了所有非n倍數的整數的集合中，剔除「對n求模同餘」的整數，使任意兩個數對n求模都不同餘。
- 既約剩餘系（縮系）：在n的完全剩餘系中，剔除不與n互質的數。
可知\Phi(n)就是n的既約剩餘數的項數。
歐拉定理
若n、a為正整數，且n與a互質，則有：
a^{\Phi(n)}≡1\pmod n證明
若正整數n的縮系為\{a_1,a_2,\cdots,a_{\Phi(n)}\}，則\{aa_1,aa_2,\cdots,aa_{\Phi(n)}\}也是n的縮系，則有：
\prod_{i=1}^{\Phi(n)}a_i≡\prod_{i=1}^{\Phi(n)}aa_i≡a^{\Phi(n)}\prod_{i=1}^{\Phi(n)}a_i\pmod n則推出：
a^{\Phi(n)}≡1\pmod n