给定任意正整数n，那么在小于等于n的所有正整数之中，有多少个与n构成互质关系？
计算这个值的方法就叫做欧拉函数\phi(n)表示：在1到n之中，与n构成互质关系的数的数量。
分析
情况一
如果n=1，则\phi(1)=1。因为1与任何数（包括自身）都构成互质关系
情况二
如果n是质数，则\phi(n)=n-1。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
情况三
如果n是质数的某一个次方，即n=p^k（p为质数，k为大于等于1的整数），则\phi(p^k)=p^k-p^{k-1}
比如\phi(8)=\phi(2^3)=2^3-2^2=8-4=4
这是因为只有当一个数不包含质数p，才有可能与n互质。而包含质数p的数一共有p^{k-1}个。
即1\times p、2\times p、3\times p、... 、p^{k-1}\times p，把他们去除，剩下的就是与n互质的数。
上面的式子还可以写成下面的形式：
\phi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})
可以看出，上面的第二种情况是k=1时的特例
情况四
如果n可以分解成两个互质的整数之积：n=p_1\times p_2{
则：\phi(n)=\phi(p_1p_2)=\phi(p_1)\phi(p_2)
即积的欧拉函数等于各个因子的欧拉函数之积。比如\phi(56)=\phi(8\times 7)=\phi(8)\phi(7)=4\times 6=24
对于素数p，\phi(p)=p-1，对于两个素数p,q，\phi(pq)=pq-1
欧拉函数是积性函数，但不是完全积性函数
欧拉函数的积性
若m,n互质，则\phi(mn)=\phi(m)\phi(n)。
由“m,n互质”可知m,n无公因数，所以：
\phi(m)\phi(n)=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})...(1-\frac{1}{p_n})\cdot n(1-\frac{1}{p_1'})(1-\frac{1}{p_2'})(1-\frac{1}{p_3'})...(1-\frac{1}{p_n'})
其中p_1、p_2、p_3...p_n为m的质因数，p_1'、p_2'、p_3'...p_n'为n的质因数，而m,n无公因数。
所以p_1、p_2、p_3...p_n、p_1'、p_2'、p_3'...p_n互不相同，所以p_1、p_2、p_3...p_n、p_1'、p_2'、p_3'...p_n均为mn的质因数且为mn的质因数的全集。
所以\phi(mn)=mn(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})...(1-\frac{1}{p_n})\cdot (1-\frac{1}{p_1'})(1-\frac{1}{p_2'})(1-\frac{1}{p_3'})...(1-\frac{1}{p_n'})
所以\phi(mn)=\phi(m)\phi(n)。
以上部分涉及到“中国剩余定理”
情况五
因为任意一个大于1的正整数，都可以写成一系列质数的积。（分解质因数）
n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}
根据结论四，得到
\phi(n)=\phi(p_1^{k_1})\phi(p_2^{k_2})...\phi(p_r^{k_r})
再根据结论三，得到
\phi(n)=p_1^{k_1}p_2^{k_2}...p_r^{k_r}(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r})
也就等于
\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r})
结论
比如\phi(1323)=(3^3\times 7^2)=1323(1-\frac{1}{3})(1-\frac{1}{7})=756
即\phi(mn)=\phi(n)\phi(m)只在(m,n)=1时成立。
对于一个正整数N的素数幂分解N=p_1^{q_1}p_2^{q_2}...p_n^{q_n}
\phi(N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})
除了N=2, \phi(N)都是偶数
设N为正整数，\sum{\phi(d)}=N(d|N)
欧拉函数
根据性质二，我们可以在O(\sqrt{n})的时间复杂度内求出一个数的欧拉函数值。
//直接求解欧拉函数
int euler(int n) { //返回euler(n)
int res = n, a = n;
for (int i = 2; i * i <= a; i++) {
if (a % i == 0) {
res = res / i * (i - 1);//先进行除法是为了防止中间数据的溢出
while (a % i == 0) a /= i;
}
}
if (a > 1) res = res / a * (a - 1);
return res;
}欧拉函数线性筛
如果要求N以内的所有数的欧拉函数 O(n)
const int MAXN = 1e6;
//欧拉线性筛：在线性时间内筛素数的同时求出所有数的欧拉函数
int tot;
int phi[MAXN]; //保存各个数字的欧拉函数
int prime[MAXN]; //按顺序保存素数
bool mark[MAXN]; //判断是否是素数
void get_phi(int N){
phi[1] = 1;
for(int i = 2; i <= MAXN; i++){ //相当于分解质因数的逆过程
if(!mark[i]){
prime[++tot] = i;
phi[i] = i-1;
}
for(int j = 1; j <= tot; j++){
if(i * prime[j] > N) break;
mark[i * prime[j]] = 1; //确定i*prime[j]不是素数
if(i % prime[j] == 0){ //判断prime[j] 是否为 i的约数
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else{ //prime[j] - 1 就是 phi[prime[j]],利用了欧拉函数的积性
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
}