欧拉函数的基本性质与应用

欧拉函数的基本性质与应用

一．基本原理

1.定义：欧拉函数是一个定义在正整数集上的函数,的值等于中与互素的数的个数.

2.计算公式：

（1）若为素数，则

（2）若为素数，且，形成了一个等比数列.

证明：即证.由的定义知等于从减去中与不互质的数的个数；亦即等于从减去中与不互质的数的个数.由于是质数，故等于从减去中被整除的数的个数.由于中被整除的数的个数是，故.

（3）已知正整数的素因数分解式其中素数

,证明：

下载地址