968
歐拉函數性質
先來介紹幾個與歐拉函數有關的定理：
定理一：設m與n是互素的正整數，那麼
定理二：當n為奇數時，有
。
因為2n是偶數，偶數與偶數一定不互素，所以隻考慮2n與小於它的奇數互素的情況，則恰好就等於n的歐拉函數值。
定理三：設p是素數，a是一個正整數，那麼
關於這個定理的證明用到容斥：
由於
表示小於
與
互素數的正整數個數，所以用
減去與它不互素的數的個數就行了。
那麼小於
與
不互素數的個數就是p的倍數個數，有
個。所以定理得證。
定理四：設
為正整數n的素數冪分解，那麼
這個定理可以根據定理一和定理三證明，其實用到的就是容斥。
定理五：設n是一個正整數，那麼
這個其實可以看莫比烏斯反演就明白了。
定理六：設m是正整數，(a,m)=1，則：
是同於方程
的解。
定理七：如果n大於2，那麼n的歐拉函數值是偶數。
來自苟神ACdreamer
·
https://blog.csdn.net/acdreamers/article/details/8007991
最後更新：2017-04-03 16:48:50