【数论】欧拉定理与扩展欧拉定理证明

欧拉定理与扩展欧拉定理证明

之前一直想填这个坑来着。。

欧拉定理证明

欧拉定理:若 \((a, m) = 1\)​,\(a^{\phi(m)} \equiv 1 \pmod m\)​.

证明

引理:设 \(r_1,\dots,r_{\phi(m)}\)​ 为模 \(m\)​ 的缩系,那么 \(ar_1,\dots,a_{\phi(m)}\) 也是模 \(m\)​ 的缩系。

证明:

首先,\(\forall k \in [1, \phi(m)]\),\(ar_k \equiv 1 \pmod m\)​

下只需证明 \(\forall i,j\in[1, \phi(m)], i\ne j\),有 \(ar_i \not \equiv ar_j \pmod m\)​​:

因为 \(ar_i-ar_j = a(r_i-r_j)\)

而我们有 $(m \nmid a) $​ 且 $ m\nmid(r_i-r_j)$​,得证。​

因此 \(\prod r_i \equiv \prod ar_i \pmod m\),而 \((r_i, m) = 1\),故 \(a^{\phi(m)} \equiv 1 \pmod m\)。

扩展欧拉定理证明

扩展欧拉定理:若 \(b\geq \phi(m)\),那么 \(a^b \equiv a^{b\% \phi(m) + \phi(m)} \pmod m\)。

证明

由唯一分解定理,\(a = \prod p_i^{\alpha_i}\)​​​,我们只需要证明对于 \(a\)​​​ 的任意一个质因数 \(p\)​​​,都有:若 \(b\geq \phi(m)\)​​​,那么 \(p^b \equiv p^{b\% \phi(m) + \phi(m)} \pmod m\)​​​​。

而对于质数的幂次方可以用下面的方法类似证明,因此下面考虑证明:对于任意质数 \(p\)​​,上述结论成立。

记 \(m = sp^k\),其中 \((s, p) = 1\)。

由欧拉定理,\(p^{\phi(s)}\equiv 1 \pmod s\)。

因为欧拉函数为积性函数,故 \(\phi(s) \mid \phi(m)\),进而有 \(p^{\phi(m)}\equiv 1 \pmod s\)。

上式两边同乘 \(p^k\)​​,有 \(p^{\phi(m) + k}\equiv p^k \pmod m\)​​。

进而 $$p^{\phi(m) + k}\equiv p^k \equiv p^{k%\phi(m) + \phi(m)} \pmod m$$。

因此,对于 \(b\geq \phi(m)\)​,\(p^b\equiv p^{b \% phi(m) + b}\)​。

上一篇:连接到一个Office 365组 - 编程方式 (一)


下一篇:清华数据院院长韩亦舜:大数据时代的数据伦理问题探究