欧拉定理

1、定义：若a于n互质，则\(a^{\varphi(n)}\equiv1 (mod\quad n)\)，这里的\(\varphi()\)为欧拉函数。

2、欧拉函数的证明
  我们假设在1~n中和n互质的数是\(a_1,a_2 ,a_3,...,a_{\varphi(n)}\)
  那么\(a*a_1,a*a_2 ,a*a_3,...,a*a_{\varphi(n)}\)也跟n互质。
  并且这\(\varphi(n)\)个数互不相同及两两不同。
  这里又出现了一个问题，那就是为什么两两不同呢？
  我们这里可以用反证法。
  假设有一个\(a*a_i =a* a_j\),那么我们就可以得到\(a*a_i\equiv a*a_j (mod\quad n)\),
  然后移项得到\(a*a_i - a*a_j\equiv 0 (mod\quad n)\)。
  提出一个a就是\(a*(a_i - a_j)\equiv 0 (mod\quad n)\),又因为a和n互质，所以我们可以约掉a得到\(a_i \equiv a_j (mod\quad n)\) ，显然和我们得到的条件不同，因此这\(\varphi(n)\)个数是两两不同的。
  因为是1~n之间的数，所以\(a_1,a_2 ,a_3,...,a_{\varphi(n)}\)和\(a*a_1,a*a_2 ,a*a_3,...,a*a_{\varphi(n)}\)的剩余系是相同的，及模上n之后的集合是相同的。
所以我们可以得到\(a*a_1+a*a_2 +a*a_3+...+a*a_{\varphi(n)}\equiv a_1+a_2 +a_3+...+a_{\varphi(n)}\)此时我们提出一a来就能得到\(a^{\varphi(n)}*(a_1+a_2 +a_3+...+a_{\varphi(n)})\equiv a_1+a_2 +a_3+...+a_{\varphi(n)}\)最后我们约去左右相同的部分我们就能得到\(a^{\varphi(n)}\equiv1 (mod\quad n)\)

费马小定理

1、定义：如果p是质数的话那么就有\(a^{p-1}\equiv1 (mod\quad p)\)
2、我们知道对于一个质数p的欧拉函数就等于p-1，那么根据欧拉定理即可得到$$a^{p-1}\equiv1 (mod\quad p)$$