欧拉函数|欧拉函数及其性质|欧拉函数及其性质证明一文说明白-526互联

欧拉函数

在数论，对正整数n，欧拉函数是小于等于n的正整数中与n互质的数的数目。读作 phi 。$\LaTeX$ 大写：\phi $\phi$ ，小写：\varphi $\varphi$

部分选自百度百科

欧拉函数的性质

以下所有 $p$ 表示质数

性质1

\[\varphi(p)=p-1 \]

性质1的证明

根据质数的定义，比 p 小的数都是与 p 互质的，所以1到n-1都与n互质。这一点很容易得出。

性质2

欧拉函数是积性函数，但不是完全积性函数。

什么意思呢？若 $\gcd(a,b)=1$ 则有 $\varphi(a\times b)=\varphi(a)\times\varphi(b)$ 。

性质2的证明之理性证明

\[\begin{aligned} \varphi(m)* \varphi(n) &= m*n * \prod_{i=1}^{a_m}{(1-\frac{1}{p_i})}*\prod_{i=1}^{a_n}{(1-\frac{1}{p_i})} \\ &= m*n * \prod_{i=1}^{a_m+a_n}{(1-\frac{1}{p_i})} \\ &= \varphi(m*n) \end{aligned} \]

性质2的证明之感性证明

因为 ab互质，所以与a互质的数乘上与b互质的数也会与ab互质

性质3

\[\varphi(p^k)=p^k-p^{k-1} \]

性质3的证明

因为 $p$ 是质数，与 $p^k$ 互质的有 $p,2p,3p...p\times p^{k-2},p\times p^{k-1}$ ，共 $p^{k-1}$ 个，故用全部个数减去互质个数得 $\varphi(p^k)=p^k-p^{k-1}$ 。

性质4

\[\varphi(n) = n \times \prod_{i = 1}^s{(1-\frac{1}{p_i})} \]

性质4的证明

这里的n没有质不质数的限制，根据唯一分解定理，一个大于1的正整数，分解后一定是这样的形式：

\[n = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times ... \times p_s^{a_s} = \prod_{i = 1}^s{p_i^{a_i}} \]

根据性质2（ $\varphi(a\times b)=\varphi(a)\times\varphi(b)$ ）得：

\[\varphi(n) = \varphi(p_1^{a_1}) \times ... \times \varphi(p_s^{a_s}) \]

再根据性质3（ $\varphi(p^k)=p^k-p^{k-1}$ ）得：

\[\varphi(n) = (p_1^{a_1}-p_1^{a_1-1}) \times ... \times (p_s^{a_s}-p_s^{a_s-1}) \]

整理一下，疯狂化简：

\[\begin{eqnarray} \varphi(n)&=&\prod_{i = 1}^s{p_i^{a_i}-p_i^{a_i-1}} \nonumber \\ ~&=&\prod_{i = 1}^s{p_i^{a_i}(1-\frac{1}{p_i})} \nonumber \\ ~& &\text{根据唯一分解定理 } n = \prod_{i = 1}^s{p_i^{a_i}} &\text{ 得到} \nonumber \\ ~&=&n \times \prod_{i = 1}^s{(1-\frac{1}{p_i})} \nonumber \end{eqnarray} \]

性质5

\[\sum_{i = 1}^n{i[gcd(i,n)=1]}=n\frac{\varphi(n)}{2} \]

此处 [] 表示条件，若 [] 内条件为真则为 1，反之为 0 。

性质5的证明

由 $\gcd(n,i)=1$ 可证出 $\gcd(n,n-i)=1$

证明当 $\gcd(n,i)=1$ 时 $\gcd(n,n-i)=1$

设 $\gcd(n,n-i)=D\neq 1$ ，则有 $D|n$ 、 $D|n-i$ 。

所以 $D|i$ （因为n是D的倍数，n-i是D的倍数，所以i是D的倍数）

根据 $D|n$ 、 $D|i$ 得到 $\gcd(n,i)\geq D$ 。根据条件 $\gcd(n,i)=1$ 得 $D=1$ ，与 $D\neq 1$ 矛盾。故当 $\gcd(n,i)=1$ 时 $\gcd(n,n-i)=1$ 。

继续证性质5

因为 $\gcd(n,i)=1$ 可证出 $\gcd(n,n-i)=1$ 。

所以与 $n$ 互质的数的组数是 $\frac{\varphi(n)}{2}$ （总共 $\varphi(n)$ 个数，两个数凑成一组），而每组之和又是 $n$ ，可以得到这些数的和就是 $n\frac{\varphi(n)}{2}$ 。

如当 $n=12$ 时符合条件的i有 1 5 7 11 ，1和11可以凑成一组与 5和7可以凑成一组，总共是两组，故总共是 $2\times \frac{4}{2} = 4$ 。

性质6

\[n=\sum_{d|n}{\varphi(d)} \]

在这里 d|n 表示d是n的因数（包括1和它自己）

性质6的证明

设 $F(n)=\sum_{d|n}{\varphi(d)}$

如果n=1，$\varphi(n)=1=n$ ，满足 $F(n)=n$ 。
如果n是质数， $\varphi(n)=n−1$，所以 $\varphi(n)+\varphi(1)=1$ ，满足 $F(n)=n$ 。
如果n是一个质数p的幂，即 $n=p^k$ ，因为 $p^k$ 的因数只 1,p,p2,p3,⋯,pk，根据性质3（ $\varphi(p^k)=p^k-p^{k-1}$ ），代入计算$F(p^k)=\varphi(1)+\varphi(p)+\varphi(p^2)+...+\varphi(p^k)=1+(p-1)+(p^2-p)+...+(p^k-p^{k-1})=p^k$ ，满足 $F(n)=n$ 。
如果n有多个质因子，即 $n=p_1^{k_1}p_2^{k_2}...p_n^{k_n}$ 。

首先证明 $F(n)$ 是个积性函数：设m,n互质，则要证 $F(m\times n)=F(m)\times F(n)$ 。

\[\begin{aligned} F(m)∗F(n) &= \sum_{i|m}{\varphi(i)}\times\sum_{j|n}{\varphi(j)} \\ &= (\varphi(i_1) + \varphi(i_2) + ... + \varphi(i_{pm})) \times (\varphi(i_1) + \varphi(i_2) + ... + \varphi(i_{qn})) \\ &= \varphi(i_1)\times\varphi(j_1)+\varphi(i_1)\times\varphi(j_2)+...+\varphi(i_1)\times\varphi(j_{qn}) &(\text{这里可以想到乘法分配律})\\ &\quad +\varphi(i_2)\times\varphi(j_1)+\varphi(i_2)\times\varphi(j_2)+...+\varphi(i_2)\times\varphi(j_{qn}) \\ &\quad +...\\ &\quad +\varphi(i_{pm})\times\varphi(j_1)+\varphi(i_{pm})\times\varphi(j_2)+...+\varphi(i_{pm})\times\varphi(j_{qn}) \end{aligned} \]

其中 $i_1,i_2,... ,i_{pm}$ 为m的所有因数， $j_1,j_2,\cdots,j_{qn}$ 为n的所有因数。

因为m与n互质，所以它们的因数也必然全都两两互质，而欧拉函数又是个积性函数，即 $\varphi(a\times b)=\varphi(a)\times\varphi(b)$ ，那么上式又可以等价于 $\varphi(i_1\times j_1)+\varphi(i_1\times j_2)+...+\varphi(i_{pm}\times j_{qn})$ 。可以发现，这些数构成了 $m\times n$ 的所有因数。那么这些数的欧拉函数之和就等于 $F(m\times n)$ ，所以 $F(m\times n)=F(m)\times F(n)$ ，证得F是一个积性函数。

根据唯一分解定理，$ n = p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times ... \times p_s^{a_s} $

所以 $F(n)=F(p_1^{k_1})\times F(p_2^{k_2})\times ...\times F(p_n^{k_n})=p_1^{k_1}p_2^{k_2}... p_n^{k_n}=n$

综上， $F(n)=n$ 对所有的正整数n成立。

故 $n=\sum_{d|n}{\varphi(d)}$

性质7

当 $n>2$ 时， $\varphi(n)$ 是偶数

性质7的证明

当n为质数时，根据性质1可得 $\varphi(n)=n-1$ ，大于2的质数均为奇数，故当 $n>2$ 且为质数时 $\varphi(n)=n-1$ 是偶数。
当n为和数且 $n=2^k$ 时，k一定大于1（如果k=1，则n就是2了）。$\varphi(2^k)=2^k-2^{k-1}=(2^k-1)\times (2^{k-1})$ ， $2^{k-1}$ 一定是一个偶数（注意前面的前提——k大于1），偶数乘任意整数依旧是偶数，则 $\varphi(2^k)=(2^k-1)\times (2^{k-1})$ 是偶数。
当n为和数且 $n\neq 2^k$ 时，根据性质4可得 $\varphi(n) = \prod_{i = 1}^s{p_i^{a_i}-p_i^{a_i-1}} = \prod_{i = 1}^s{(p_i-1)\times p_i^{a_i-1}}$ 。
此时对于每一个 $p_i$ 不为2的 $(p_i-i)\times p_i^{a_i-1}$ （这一个 $p_i$ 一定存在，不然n就是2的k次幂，是情况2了）， $p_i-1$ 一定为偶数（因为p是大于2的质数），故 $(p_i-i)\times p_i^{a_i-1}$ 一定也是偶数。所以 $\prod_{i = 1}^s{(p_i-1)\times p_i^{a_i-1}}$ 至少存在着一个偶数，偶数乘任意整数还为偶数，故 $\varphi(n) = \prod_{i = 1}^s{(p_i-1)\times p_i^{a_i-1}}$ 是偶数。

综上 $\varphi(n)$ 是偶数对所有大于2的正整数n成立。得证。

欧拉函数计算代码

lazy_phi

根据欧拉算法的定义，我们可以写出这么一个代码：

template<typename T> 
T gcd(T a,T b){
	if(b==0) return a;
	return gcd(b,a%b); 
}
template<typename T> 
T lazy_phi(T n){	// lazy_phi的名字是我自己起的 
	T res=0;
	for(T i=1;i<=n;i++){
		if(gcd(i,n)==1){
			res++;
		}
	}
	return res;
}

的确挺 lazy 的。复杂度……反正很大。

但是，我们可以优化一下：

good_phi

我们先假设 $\varphi(n)=n$ ，每遇到一个n的因数k就将它与它的倍数的个数减去。我们可以求出n以内因数k的出现次数为： $\lfloor\frac{phi[n]}{k}\rfloor$ ，即更新为 $phi[n]-=\lfloor\frac{phi[n]}{k} \rfloor$ （即先求出在n范围内k的倍数出现了多少次，再减去所有k的倍数）

template<typename T> 
T good_phi(T n){
	T res=n;
	for(T i=2;i*i<=n;i++){
		if(n%i==0){
			res-=res/i;
		}
		while(n%i==0) n/=i;		// 刚刚算过了 
	}
	if(n>1) res-=res/n;	                // 最后的n也是因数
	return res; 
}

erat_phi

我们既然前面得出了 $phi[n]-=\lfloor\frac{phi[n]}{k} \rfloor$ ，为何不一次性把所有phi求出来呢？我们在这里使用埃拉托斯特尼筛：

int phi[N+10];					// phi值  
template<typename T> 
void erat_phi(T n){
    for(T i=1;i<=n;i++) phi[i]=i;
    for(T i=2;i<=n;i++){
        if(phi[i]==i){
            for(int j=i;j<=n;j+=i){	// 更新倍数 
                phi[j]-=phi[j]/i;
            }
        }
    }
}

euler_phi

注意到在欧拉筛中，每一个合数都是被最小的质因子筛掉。我们可以利用这个性质来实现求phi。

case 1 对于每一个质数，都有 $\varphi(p)=p-1$ 。

case 2 若 a 不是是质数 p 的倍数，因为 $\varphi$ 是积性函数，故有 $\varphi(a\times p)=\varphi(a)\times \varphi(p)$

case 3 若 a 是质数 p 的倍数，则有 $\varphi(a\times p) = \varphi(i) \times p$ 。

证明 $\varphi(a\times p) = \varphi(a) \times p$

我们用矩阵的方式想：有一个a列p行的矩阵，由于a是p的倍数，那么我们就只用考虑与a互质的数即可。因为与a互质的数就是与 $a\times p$ 互质的数，即当 $k\not\mid a$ 时， $k\times i\not\mid a\times p$ 。

\[\begin{array}{} 1 & 2 & \cdots & a\\ a+1 & a+2 & \cdots & 2a\\ \vdots & \vdots & \ddots & \vdots\\ a(p-1)+1 & a(p-1)+2 & \cdots & ap \end{array} \]

那么每一行与a互质的数有 $\varphi(a)$ 个，共p行，则 $\varphi(a\times p) = \varphi(a) \times p$ 。

非常感谢Hongse_Fox大佬的思路

实现：

int phi[N+10];					                  // phi值 
int prime[N+10];				                  // 质数表 
bool flag[N+10];				                  // 是否是质数 
int cnt=0;						          // 质数个数 
template<typename T> 
void euler_phi(T n){
	phi[1]=1;					          // 1需特判 
	for(T i=2;i<=n;i++){
		if(flag[i]==false){		                  // 是质数 
			prime[++cnt]=i;
			phi[i]=i-1;			          // case 1
		}
		for(T j=1;j<=cnt && prime[j]*i<=n;j++){
			flag[i*prime[j]]=true;
			if (i%prime[j]==0){	                  // 是倍数，以后一定还会再遇到，就退出 
				phi[i*prime[j]]=phi[i]*prime[j];  // case 3
				break;
			}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];	  // case 2
		}
	}
	 
}

例题#1

poj2407 或 vjudge

题目大意

每行输入一个正整数 $n \leq 1,000,000,000$ ，输出它的欧拉函数值。当 $n=0$ 时，程序结束。

因为n过大，故我们算一个求一个，使用 good_phi ：

#include<cstdio>
#define ll long long
ll n;
ll phi(ll n){
	ll res=n;
	for(ll i=2;i*i<=n;i++){
		if(n%i==0){
			res-=(res/i);
		}
		while(n%i==0) n/=i;
	}
	if(n!=1) res-=(res/n);
	return res;
}
int main(){
	while(true){
		scanf("%lld",&n);
		if(n==0) break;
		printf("%lld\n",phi(n));
	}
	return 0; 
}

例题#2

hdu1286 或 vjudge

题目大意

第一行给出数据组数 $t\leq 10,000$ ，接下来每行输入一个正整数 $n \leq 32,768$ ，输出它的欧拉函数值。

询问量较大，且n的大小较小，故可以用欧拉筛法求欧拉函数：

#include<cstdio>
#define N 32768
int t,n;
int prime[N+10];
bool flag[N+10];
int phi[N+10];
int cnt;
void euler_phi(){
	phi[1]=1;
	for(int i=2;i<=N;i++){
		if(flag[i]==false){
			phi[i]=i-1;
			prime[++cnt]=i;
		}
		for(int j=1;j<=cnt && i*prime[j]<=N;j++){
			flag[i*prime[j]]=true;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
}
int main(){
	scanf("%d",&t);
	euler_phi();
	for(int i=1;i<=t;i++){
		scanf("%d",&n);
		printf("%d\n",phi[n]);
	}
	return 0; 
}