欧拉定理

• 定理内容
  对于两个互质的整数a,n有\(a^{\varphi(n)}\equiv1(mod\enspace n)\) 这里的\(\varphi(n)\)指的是欧拉函数。
  -数学证明
  由\(\varphi(n)\)可知从1到n与n互质的有\(m_1,m_2,m_3\dots m_{\varphi(n)}\)。全部乘以a得\(am_1,am_2,am_3\dots am_{\varphi(n)}\),由起始条件a与n互质可得\(am_i\)与n互质，且\((am_i)\)%n也与n互质^[1]，所以\(am_1*am_2*am_3\dots *am_{\varphi(n)}\equiv m_1*m_2*m_3*\dots*m_{\varphi(n)}(mod\enspace n)\\\Longleftrightarrow a^{\varphi(n)}\equiv1(mod\enspace n)\) 证毕。
• 费马小定理（欧拉定理的特殊情况）
  特别的，当n为质数时，有\(a^{\varphi(n)}\equiv1(mod\enspace n)\Longleftrightarrow a^{n-1}\equiv1(mod\enspace n)\),因为如果n为质数那么从1到n与n互质的一共有n-1个。