欧拉降幂公式与证明

转载自D-Tesla

欧拉降幂公式

A K ≡ A K % ϕ ( m ) + ϕ ( m ) ( <mtext>   </mtext> m o d <mtext>   </mtext> m ) K > ϕ ( m )

证明

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

A K ≡ A K % ϕ ( m ) + ϕ ( m ) ( <mtext>   </mtext> m o d <mtext>   </mtext> m ) <mtext>   </mtext> K > ϕ ( m ) ( 1 )

证明如下
1 若 ( A , m ) = 1 ，根据欧拉定理 A ϕ ( m ) ≡ 1 ( m o d <mtext>   </mtext> m ) ,即可轻易得证
2 若 ( A , m ) ≠ 1 ,证明如下
设 K = a ∗ ϕ ( m ) + c a ≥ 1 , 0 ≤ c < ϕ ( m )
那么欧拉降幂公式就是

A K ≡ A a ∗ ϕ ( m ) + c ≡ A ϕ ( m ) + c ( <mtext>   </mtext> m o d <mtext>   </mtext> m ) ( 2 )

即 证
A a ∗ ϕ ( m ) ≡ A ϕ ( m ) ( m o d <mtext>   </mtext> m )

即 证
A 2 ∗ ϕ ( m ) ≡ A ϕ ( m ) ( m o d <mtext>   </mtext> m )

移项
A ϕ ( m ) ( A ϕ ( m ) − 1 ) ≡ 0 ( m o d <mtext>   </mtext> m )

即证
m | A ϕ ( m ) ( A ϕ ( m ) − 1 ) ( 3 )

若有

( m ( m , A ϕ ( m ) ) , A ) = 1 ( 4 )

根据欧拉定理
A ϕ ( m ) ≡ A k ∗ ϕ ( m ( m , A ϕ ( m ) ) ) ≡ ( A ϕ ( m ( m , A ϕ ( m ) ) ) ) k ≡ 1 ( m o d <mtext>   </mtext> ( m ( m , A ϕ ( m ) ) )
其中 k ≥ 1

移项即得 m ( m , A ϕ ( m ) ) | ( A ϕ ( m ) − 1 )
同时乘 ( m , A ϕ ( m ) )
即 m | ( m , A ϕ ( m ) ) ∗ ( A ϕ ( m ) − 1 )
即 m | A ϕ ( m ) ( A ϕ ( m ) − 1 )
就是 式 3

所以证明 式子 4

( m ( m , A ϕ ( m ) ) , A ) = 1
就好了

进行素因子分解

A = p 1 a 1 ∗ p 2 a 2 ∗ . . . . ∗ p t 1 a t 1 ∗ q 1 b 1 ∗ q 2 b 2 ∗ . . . ∗ q t 2 b t 2

m = p 1 c 1 ∗ p 2 c 2 ∗ . . . . ∗ p t 1 c t 1 ∗ r 1 d 1 ∗ r 2 d 2 ∗ . . . ∗ r t 3 d t 3

( A , m ) = p 1 m i n ( a 1 , c 1 ) ∗ p 2 m i n ( a 2 , c 2 ) ∗ . . . . ∗ p t 1 m i n ( a t 1 , c t 1 )

( A ϕ ( m ) , m ) = p 1 m i n ( a 1 ∗ ϕ ( m ) , c 1 ) ∗ p 2 m i n ( a 2 ∗ ϕ ( m ) , c 2 ) ∗ . . . . ∗ p t 1 m i n ( a t 1 ∗ ϕ ( m ) , c t 1 )

欧拉函数 ϕ ( m ) = p 1 c 1 − 1 ∗ p 2 c 2 − 1 ∗ . . . . ∗ p t 1 c t 1 − 1 ( p 1 − 1 ) ∗ ( p 2 − 1 ) ∗ . . . . ∗ ( p t 1 − 1 )

a i ∗ ϕ ( m ) ≥ a i ∗ p i c i − 1 ∗ ( p i − 1 ) ≥ p i c i − 1 ∗ ( p i − 1 ) ≥ p i c i − 1

证明

p i c i − 1 ≥ c i ( 6 )

若 c i = 1 ,成立

令 f ( x ) = l n ( x ) x − 1
在 [ 3 , ∞ ] 单调减\
又有

f ( 2 ) = l n 2 < 2 ≤ p i

f ( 3 ) = l n 3 / 2 < 2 ≤ p i

于是有 式子6 成立
于是有
( A ϕ ( m ) , m ) = p 1 m i n ( a 1 ∗ ϕ ( m ) , c 1 ) ∗ p 2 m i n ( a 2 ∗ ϕ ( m ) , c 2 ) ∗ . . . . ∗ p t 1 m i n ( a t 1 ∗ ϕ ( m ) , c t 1 ) = p 1 c 1 ∗ p 2 c 2 ∗ . . . . ∗ p t 1 c t 1

m ( A ϕ ( m ) , m ) = q 1 b 1 ∗ q 2 b 2 ∗ . . . ∗ q t 2 b t 2

式子 4
( m ( m , A ϕ ( m ) ) , A ) = 1

得证
式子 3
m | A ϕ ( m ) ( A ϕ ( m ) − 1 ) ( 3 )

得证
式子 2
A K ≡ A a ∗ ϕ ( m ) + c ≡ A ϕ ( m ) + c ( <mtext>   </mtext> m o d <mtext>   </mtext> m ) ( 2 )

得证
欧拉降幂公式得证
A K ≡ A K % ϕ ( m ) + ϕ ( m ) ( <mtext>   </mtext> m o d <mtext>   </mtext> m ) K > ϕ ( m ) ( 1 )