关于欧拉定理的一些

好久没做数论题了,对于一些定理也有些生疏了。就作个复习并拓展一些结论吧。

欧拉定理

(a,m)=1 时,有

a^{\varphi(m)}\equiv 1\pmod{m}

证明

考虑 m 的缩系(缩简剩余系)中的 \varphi(m) 个数 x_1,x_2,…,x_{\varphi(m)},设 b_i=ax_i.

引理 1

b_im 互质。

显然。

引理 2

b_i 构成模 m 的缩系。

反证法。若 \exists b_i \equiv b_j,则 ax_i \equiv ax_j,x_i-x_j\equiv 0,而 0 < x_i-x_j < m,矛盾。由引理1可知 b_i \perp m,证毕。

因此我们得到

\prod b_i \equiv \prod x_i

(因为两边都是模 m 的缩系)

就有 a^{\varphi(m)} \prod x_i\equiv \prod x_i,因为 (\prod x_i, m)=1,则 a^{\varphi(m)}\equiv 1,证毕。

拓展欧拉定理

重头戏在这里!这个定理还是比较难证的。(网上也有很多错误的证明)

对于 \forall a, m \in N,且 c\ge \varphi(m),有

a^c \equiv a^{c \text{ mod } \varphi(m)+\varphi(m)}\pmod{m}

证明

考虑对于 a 的某个质因子 p,设 m=p^rt,(p,t)=1.

由欧拉定理,p^{\varphi(t)}\equiv 1\pmod{t}.

因为 \varphi(t) \mid \varphi(m),所以 p^{\varphi(m)}\equiv 1\pmod{m},可得 p ^{\varphi(m)+r} \equiv p^r \pmod{m}.

由此,p^c\equiv p^{c-r+r}\equiv p^{c-r+\varphi(m)+r}\equiv p^{c+\varphi(m)},注意前提是 c\ge r.

\varphi(m) \ge \varphi(p^r) = p^{r-1}(p-1)\ge r,故当 c\ge \varphi(m) 时,也有 p^c\equiv p^{c+\varphi(m)}. 所以当 c\ge 2\varphi(m) 时,有 p^c\equiv p^{c-\varphi(m)}. 于是我们可以推出 p^c \equiv p^{c \text{ mod } \varphi(m)+\varphi(m)}.

上面结论的前提是 p 为质数,当然它对于质数的幂同样成立:(p^k)^c \equiv p^{kc} \equiv p^{k\varphi(m)+kc} \equiv (p^k)^{\varphi(m)+c} \equiv (p^k)^{c \text{ mod } \varphi(m)+\varphi(m)}.

于是我们将 a 分解质因数,就证毕了。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注