什么是欧拉函数？

引用百科上的原话，在数论中，对任意正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（一般认为 φ(1) = 1）。此函数以其首名研究者欧拉命名(Euler‘s totient function)，它又称为Euler‘s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
下面是30以内数字的欧拉函数的值：

重要定理

p和q是素数, n=p*q, φ(n)= φ(p)φ(q)=(p-1)(q-1)

证明：

考虑余数集合{0, 1, …, (pq-1)}中不与n互素的余数集合是{p, 2p, …, (q-1)p}, {q, 2q, …, (p-1)q}和0, 所以 φ(n)= pq-[(q-1)+(p-1)+1]=pq-(p+q)+1= (p-1)(q-1)=φ(p)φ(q)

函数通式

其中p1, p2,…,pn为x的所有质因数，x是正整数。

证明：

首先，若n是质数p的k次幂，$$\phi(n)=p^k-p^(k-1)=(p-1)p^(k-1)$$，因为除了p的倍数外，其他数都跟n互质。

欧拉函数（Euler’s Totient Function）的通式与分析

原文：https://www.cnblogs.com/Higgerw/p/14082957.html