欧拉函数公式以及证明

欧拉函数：欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n)。完全余数集合：定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。显然|Zn|＝φ(n)。有关性质：对于素数p，φ(p)=p-1。对于两个不同素数p，q，它们的乘积n=p*q满足φ(n)=(p-1)*(q-1)。这是因为Zn={1,2,3,...,n-1}-{p,2p,...,(q-1)*p}-{q,2q,...,(p-1)*q}，则