欧拉降幂公式的证明

欧拉降幂公式与证明

转载自D-Tesla

欧拉降幂公式

证明

今天在牛客多校的群里看一个数学大佬写的证明，不过是拍照，我决定动手自己写一下

证明如下
1 若 (A,m)=1 $(A,m)=1$，根据欧拉定理 Aϕ(m)≡1(mod m) $A^{\varphi \left(m\right)}\equiv 1\left(modm\right)$,即可轻易得证
2 若 (A,m)≠1 $(A,m)\ne 1$,证明如下
设 K=a∗ϕ(m)+c $K=a\ast \varphi \left(m\right)+c$ a≥1,0≤c<ϕ(m) $a\ge 1,0\le c<\varphi \left(m\right)$
那么欧拉降幂公式就是

若有

移项即得 m(m,Aϕ(m))|(Aϕ(m)−1) $\frac{m}{(m,A^{\varphi \left(m\right)})}|(A^{\varphi \left(m\right)}-1)$
同时乘 (m,Aϕ(m)) $(m,A^{\varphi \left(m\right)})$
即 m|(m,Aϕ(m))∗(Aϕ(m)−1) $m|(m,A^{\varphi \left(m\right)})\ast (A^{\varphi \left(m\right)}-1)$
即 m|Aϕ(m)(Aϕ(m)−1) $m|A^{\varphi \left(m\right)}(A^{\varphi \left(m\right)}-1)$
就是 式 3

所以证明 式子 4

进行素因子分解

ai∗ϕ(m)≥ai∗pci−1i∗(pi−1)≥pci−1i∗(pi−1)≥pci−1i $a_i\ast \varphi \left(m\right)\ge a_i\ast p_i^{c_i-1}\ast (p_i-1)\ge p_i^{c_i-1}\ast (p_i-1)\ge p_i^{c_i-1}$

证明

若 ci=1 $c_i=1$ ,成立

令 f(x)=ln(x)x−1 $f\left(x\right)=\frac{ln\left(x\right)}{x-1}$
在 [3,∞] $[3,\infty ]$ 单调减\
又有