欧拉定理 & 费马小定理

@Pelom  October 11, 2021

欧拉定理 & 费马小定理

一、欧拉(Euler)定理

1.定理

若 $(a,m)=1$ ,则
$$a^{\varphi(m)} \equiv 1 \ (\bmod \ m)$$
其中 $\varphi(m)$ 为欧拉函数,定义为小于或等于 $m$ 的正整数中与 $m$ 互质的数的数目

2.证明:

记模 $m$ 意义下的缩系(小于 $m$ 且与 $m$ 互素的正整数集合)
$$R=\{x_1,x_2,\dots,x_{\varphi(m)}\}$$

$$S=\{ax_1\%m,ax_2\%m,\dots,ax_{\varphi(m)}\%m\}$$
$\forall \ i\in[1,\varphi(m)]$
因为$$(a,m)=1,(x_i,m)=1$$
所以$$(ax_i,m)=1$$
由最大公约数的性质$$(ax_i\%m,m)=1$$
所以 $S$ 中所有元素都与 $m$ 互素且都小于 $m$
下证 $S$ 中无重
若 $$\exist \ i \neq j,ax_i\%m=ax_j\%m$$ 即 $$ax_i \equiv ax_j \ (\bmod \ m)$$
因为 $$(a,m)=1$$
所以 $$x_i \equiv x_j \ (\bmod \ m)$$ 矛盾!
所以 $$S=R$$
所以 $$\prod\limits_{i=1}^{\varphi(m)} ax_i\%m = \prod\limits_{i=1}^{\varphi(m)} x_i$$
所以 $$\prod\limits_{i=1}^{\varphi(m)} ax_i \equiv \prod\limits_{i=1}^{\varphi(m)} x_i \ (\bmod \ m) \Rightarrow a^{\varphi(m)} \prod\limits_{i=1}^{\varphi(m)} x_i \equiv \prod\limits_{i=1}^{\varphi(m)} x_i \ (\bmod \ m)$$
因为 $$(\prod\limits_{i=1}^{\varphi(m)} x_i,m)=1$$
所以 $$a^{\varphi(m)} \equiv 1 \ (\bmod \ m)$$

二、费马(Fermat)小定理

考虑欧拉定理中 $m$ 为素数 $p$ 的情况,此时 $\varphi(p)=p-1$,则
$$a^{p-1} \equiv 1 \ (\bmod \ p)$$

三、扩展欧拉定理

推广至不要求 $(a,m)=1$

1.定理

$$ a^c \equiv \left\{ \begin{aligned} & a^{c \ \bmod \ \varphi(m)}, && (a,m)=1 \\ & a^c, && (a,m) \neq 1,c < \varphi(m) \\ & a^{c \ \bmod \ \varphi(m) + \varphi(m)}, && (a,m) \neq 1,c \ge \varphi(m) \\ \end{aligned} \right. \ (\bmod \ m) $$

2.证明:

对于 $$(a,m)=1$$ 显然
对于 $$(a,m) \neq 1,c < \varphi(m)$$ 显然
对于 $$(a,m) \neq 1,c \ge \varphi(m)$$
取 $a$ 的一个素因子 $p$ ,令 $m=s \cdot p^r$ ,且 $(s,p)=1$
那么有 $$p^{\varphi(s)} \equiv 1 \ (\bmod \ s)$$
因为 $$(s,p)=1$$
所以 $$\varphi(s) \mid \varphi(m)$$
所以

$$ \begin{aligned} & p^{\varphi(m)} &\equiv& &1& \ &(\bmod \ s) \\ \Rightarrow & p^{\varphi(m)+r} &\equiv& &p^r& \ &(\bmod \ s) \\ \Rightarrow & p^{k\varphi(m)+r} &\equiv& &p^r& \ &(\bmod \ s) \end{aligned} $$

$a$ 中含有因子 $p^k$
$$(p^k)^c=p^{kc} \equiv p^{k\varphi(m)+kc}=(p^k)^{\varphi(m)+c} \equiv (p^k)^{c \ \bmod \varphi(m)+\varphi(m)} \ (\bmod \ m)$$
由算术基本定理 $$a=\prod p_i^{k_i}$$ 显然对于每个 $p_i$ 皆满足上式,于是将所有同余式相乘便有 $$a^c \equiv a^{c \ \bmod \varphi(m)+\varphi(m)} \ (\bmod \ m)$$


添加新评论