欧拉降幂公式与证明
转载⾃D-Tesla
欧拉降幂公式
证明
今天在⽜客多校的⾥看⼀个数学⼤佬写的证明，不过是拍照，我决定动⼿⾃⼰写⼀下
证明如下
1 若 ，根据欧拉定理 ，即可轻易得证
2 若 ，证明如下
设 那么欧拉降幂公式就是
即 证即 证
移项
多方会议
A ≡K A ( mod m )K >K %ϕ(m )+ϕ(m )ϕ(m )
A ≡K A ( mod m ) K >K %ϕ(m )+ϕ(m )ϕ(m )(1)
(A ,m )=1A ≡ϕ(m )1(mod m )(A ,m ) =1K =a ∗ϕ(m )+c a ≥1,0≤c <ϕ(m )
A ≡K A ≡a ∗ϕ(m )+c A ( mod m )
(2)偏二甲肼
ϕ(m )+c A ≡a ∗ϕ(m )A (mod m )
上海市轨道交通近期建设计划(2017-2025)ϕ(m )A ≡2∗ϕ(m )A (mod m ) ϕ(m )A (A −ϕ(m )ϕ(m )1)≡0(mod m )
即证
若有
根据欧拉定理
其中移项即得 同时乘 即 即 就是 式 3
所以证明 式⼦ 4就好了
进⾏素因⼦分解
欧拉函数 证明若 ，成⽴
m ∣A (A −ϕ(m )ϕ(m )1)(3)
董时进(,A )=(m ,A )ϕ(m )m
1(4)
A ≡ϕ(m )A ≡k ∗ϕ()(m ,A )ϕ(m )m
(A )≡ϕ()(m ,A )ϕ(m )m
k
牧一征
1(mod ()(m ,A )ϕ(m )m k ≥1
∣(A −(m ,A )ϕ(m )m
ϕ(m )1)(m ,A )ϕ(m )m ∣(m ,A )∗ϕ(m )(A −ϕ(m )1)m ∣A (A −ϕ(m )ϕ(m )1)(,A )=(m ,A )ϕ(m )m
1
A =p ∗1a 1p ∗∗p ∗t 1a t 1q ∗1b 1q ∗∗q t 2b t 2m =p ∗1c 1p ∗∗p ∗t 1c t 1r ∗1d 1r ∗∗r 3t 3d t 3(A ,m )=p ∗1min (a ,c )11p ∗2min (a ,c )22....∗p t 1min (a ,c )t 1t 1(A ,m )=ϕ(m )p ∗1
min (a ∗ϕ(m ),c )11p ∗2min (a ∗ϕ(m ),c )22....∗p t 1min (a ∗ϕ(m ),c )t 1t 1ϕ(m )=p ∗1c −11p ∗2c −12....∗p (p −t 1c −1t 111)∗(p −21)∗....∗(p −t 11)a ∗i ϕ(m )≥a ∗i p ∗i c −1i (p −i 1)≥p ∗i c −1i (p −i 1)≥p i c −1
i p ≥i c −1i c (6)
i c =i 1
令 在 单调减\
⼜有于是有 式⼦6 成⽴于是有魅族e3c
式⼦ 4
得证
式⼦ 3
得证
式⼦ 2
得证
欧拉降幂公式得证f (x )=
x −1ln (x )[3,∞]f (2)=ln 2<2≤p i f (3)=ln 3/2<2≤p i
(A ,m )=ϕ(m )p ∗1min (a ∗ϕ(m ),c )11p ∗2min (a ∗ϕ(m ),c )22....∗p =t 1min (a ∗ϕ(m ),c )t 1t 1p ∗1c 1p ∗∗p t 1c t 1=(A ,m )ϕ(m )m q ∗1b 1q ∗∗q t 2b t 2(,A )=(m ,A )ϕ(m )m 1m ∣A (A −ϕ(m )ϕ(m )1)(3)A ≡K A ≡a ∗ϕ(m )+c A ( mod m )(2)
ϕ(m )+c A ≡K A ( mod m )K >K %ϕ(m )+ϕ(m )ϕ(m )(1)
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议