歐拉定理：對于互質的兩個正整數$a, n$，滿足$a^{φ(n)} ≡ 1\? (mod\ n)$

證明：

　　設集合$S$包含所有$n$以內與$n$互質的數，共有$φ(n)$個：$$S = \{ x_1, x_2, ..., x_{φ(n)} \} $$

　　再設集合$T$：$$T = \{ a * x_1 \% n, a * x_2?\% n, ..., a *?x_{φ(n)} \% n \} $$

　　由于$ x_i, n $互質，$ a, n $互質，故$a, x_i$一定不包含任何$n$的因數。所以$a * x_i, n$互質

　　所以顯而易見? ? $gcd(a * x_i \% n, n) = 1$

　　顯然$S$集合中的元素互不相同，下面證明$T$中集合的元素互不相同：

　　證明：

　　　　要證明$T$中集合的元素互不相同，可以證明集合 $?\{ a * x_1, a * x_2, ..., a *?x_{φ(n)} \} $ 中任意兩個數對于$n$都不同余。

　　　　可以利用反證法：

　　　　令$m_i = a * x_i$，則集合可表示為?$?\{ m_1, m_2, ...,?m_{φ(n)} \}?$?

　　　　設$ m_s ≡ m_r\? (mod\ n) $，則可得$ m_s - m_r = q * n $，?$ a * (x_s - x_r) = q * n $

　　　　即$ n | (a * (x_s - x_r)) $

　　　　由于$a ,n$互質，所以$a, n$沒有除1外相同的因子，所以$x_s - x_r$含有所有n的因子。而由于$x_s, x_r$都是$n$以內的，所以$x_s - x_r < n$。

　　　　所以$ n | (a * (x_s - x_r)) $不成立，故$T$中集合的元素互不相同。

　　由于$T$中元素互不相同，而又由于$S$中的元素包含了$n$以內所有與$n$互質的數，$T$也包含了$n$以內所有與$n$互質的數。且$S, T$內的元素都是互不相同的.

　　所以$S = T$

　　乘起來：

　　$$ x_1 *? x_2 *? ... *? x_{φ(n)}? ≡ ?a * x_1 *? a * x_2 * ... * a *?x_{φ(n)} \ (mod\ n)$$

　　$$?x_1 *? x_2 *? ... *? x_{φ(n)}?≡? a^{φ(n)} * x_1 * x_2 * ... * x_{φ(n)}\ (mod\ n)$$

　　$$?a^{φ(n)} ≡? 1\ (mod\ n)$$

?

費馬小定理：其實就是歐拉定理。只不過當$n$是質數時，$φ(n) = n-1$。

　　　　$$a^{n-1} ≡ 1\? (mod\ n) ? \ (n為質數)$$

轉載于:https://www.cnblogs.com/qixingzhi/p/9328108.html

總結

以上是生活随笔為你收集整理的「欧拉定理」学习笔记（费马小定理）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。