降幂公式的一个证明

很早就知道了$A^{B}equiv A^{B mod varphi(C) + varphi(C)} (mod C) if B>=varphi(C)$ 然而一直不知道为什么,现在来证明一下:

首先我们来研究一下数列$a^0 a^1 a^2 cdots a^n (mod m)$有什么规律。

当a和m互质的时候：

1.根据欧拉定理$a^{varphi(m)}equiv 1 (mod m)$ 可以知道这个数列肯定是周期的。且最小周期$T<=varphi(m)$.

2.最小周期$T$一定是$varphi(m)$的约数. 证明：

假设$x<y$ 且 $a^x equiv 1 a^y equiv 1 (mod m)$

那么必定有$a^{y-x} equiv 1 (mod m)$

像欧几里得算法一样迭代下去可以得到$a^{gcd(x,y)} equiv 1 (mod m)$.

$a^T equiv 1 a^{varphi(m)} equiv 1 (mod m) ightarrow a^{gcd(T,varphi(m))} equiv 1 (mod m)$

T是最小周期,所以$T<=gcd(T,varphi(m))$,所以$T=gcd(T,varphi(m))$,所以$T$是$varphi(m)$的约数。证毕。

这种情况下$A^{B}equiv A^{B mod varphi(C) + varphi(C)} (mod C) if B>=varphi(C)$ 显然成立。

当a和m不互质的时候：

1.我们可以证明该数列除掉前面有限的几项之后,就开始周期重复了.

证明：

只要证明当x足够大时,$a^{x+T} equiv a^{x} (mod m)$ <--> $a^{'}*a^{x-1+T} equiv a^{'}*a^{x-1} (mod m^{'})$。

其中$a^{'}=frac{a}{gcd(a,m)} m^{'}=frac{m}{gcd(a,m)}$

即可以不断拿出一个a,来和m约分,直到$a^{'}$和$m^{'}$互质, 于是两边的$a^{'}$可以约去最后得到$a^{T} equiv 1 (mod m^{'})$

取$T = varphi(m')$显然成立。由于$varphi(m)$ 是$varphi(m')$的倍数，那么取$T = varphi(m)$也成立。

因此当x足够大的时候有$a^{x+varphi(m)} equiv a^{x} (mod m)$ 也就是说该数列除掉前面有限的几项之后,就开始周期重复了。

那么,x需要多大才满足这个性质呢？假设x至少要大于等于k才满足这个性质,显然k 取决于a和m能约分多少次。由于每次约分至少除以2,所以k是非常小的。

容易证明$k<varphi(m)$ 所以我们的降幂公式就是正确的。