欧拉函数

定义
欧拉函数是 小于等于 x的数中与x 互质的数的数目
符号(varphi(x))
互质两个互质的数的最大公因数等于1,1与任何数互质
通式
(varphi(x)=xprod_{i=1}^n(1-frac{1}{p_i}))
其中(p_i)为(x)的质因子,(n)为(x)的质因子个数

欧拉函数常用性质

若(n)为质数，显然(varphi(n)=n-1)
(egin{aligned}end{aligned})
欧拉函数是积性函数
积性函数: 对于任意互质的整数(a)和(b)有性质(f(ab)=f(a)·f(b))的数论函数。
若(m,n)互质，(varphi(mn)=varphi(m)·varphi(n))
(egin{aligned}end{aligned})
如果(x=2n)((n)为奇数)，(varphi(x)=varphi(n)) 即(varphi(2n)=varphi(n))((n)为奇数)
n为奇数时,n与2互质，(varphi(2)=1)
(egin{aligned}end{aligned})
若(p)为质数,则(varphi(p^k)=p^k-p^{k-1})
因为与(p^k)不互质的只有(p)的倍数，而(p^k)中(p)的倍数有(p^{k-1})个
(egin{aligned}end{aligned})
当(x>2)时，(varphi(x))为偶数
这一点需要了解更相减损术即(gcd(n,x)=gcd(n,n-x))
由该公式我们可以知道，所有与(n)互质的数都是成对出现的
(egin{aligned}end{aligned})
小于n的数中，与n互质的数的总和为(varphi(n)*n/2 (n>1))
由上面的证明(更相减损术)我们知道，每一对与(n)互质的数的和为(n)，共有(varphi(n)/2)对
(egin{aligned}end{aligned})
(n=sum_{d|n}varphi(d))即(n)的因数(()包括(1)和它自己())的欧拉函数之和等于(n)
这条性质的运用又叫 欧拉反演
定义函数
(egin{aligned}f(n)=sum_{d|n}varphi(d)end{aligned})
- (f(n))为积性函数
  (egin{aligned}f(n)·f(m)=sum_{i|n}varphi(i)sum_{j|m}varphi(j)=sum_{i|n}sum_{j|m}varphi(i)·varphi(j)=sum_{i|n}sum_{j|m}varphi(i·j)=sum_{d|nm}varphi(d)=f(nm)end{aligned})
(f(p^k)=varphi(1)+varphi(p)+varphi(p^2)+cdots+varphi(p^k)=1+(p-1)+(p^2-p)+cdots+(p^k-p^{k-1})=p^k)

(n=p_1^{k_1} ·p_2^{k_2}· cdots·p_m^{k_m})

(f(n)=f(p_1^{k_1})·f(p_2^{k_2})·cdots·f(p_m^{k_m})=p_1^{k_1} ·p_2^{k_2}· cdots·p_m^{k_m}=n)
(egin{aligned}end{aligned})

欧拉定理

若(a,m)互质，(a^{varphi(m)}≡1(mod m))

证明
- 剩余系 指对于某一个特定的正整数(n)，一个整数集中的数(mod n)所得的余数域。
  - 完全剩余系 设(min Z+)，若(r_0,r_1,...r_{m−1})为(m)个整数，并且两两模(m)不同余，则(r_0,r_1,...r_{m−1})叫作模(m)的一个完全剩余系。
  - 缩系设(A)是(mod n)的剩余系，若任意(A)中两个元素相乘(mod n)后仍为(A)中的元素,则称(A)为(mod n)的缩系
  - 若(a,m)互质，则(m)的一个缩系为
    ({x_1,x_2,x_3...x_{varphi(m)}})
    ({ax_1\%m,ax_2\%m,ax_3\%m...ax_{varphi(m)}\%m})也是(mod m)的缩系
    于是可以得到
    (sum_{i=1}^{varphi(m)}ax_iequiv sum_{i=1}^{varphi(m)}x_i (mod m))
    (a^{varphi(m)}sum_{i=1}^{varphi(m)}x_iequiv sum_{i=1}^{varphi(m)}x_i (mod m))
    (a^{varphi(m)}equiv 1 (mod m))
    - 而当(m)为质数时，(varphi(m)=m-1)
      (a^{(m-1)}≡1(mod m))
      这就是我们熟知的 费马小定理
变式 (a,m)互质(a^b≡a^{b\%varphi(m)}(mod m))

扩展欧拉定理

若(b>varphi(m)) 即使(a,m)不互质，(a^b≡a^{b \%varphi(m)+varphi(m)}left(mod m ight))

证明
从(m)中提一个质因子(p)出来令(m=p^k·s)
有(gcd(p^k,s)=1)，即(p^k,s)互质
根据欧拉定理，我们知道(p^{varphi(s)}≡1(mod s))
根据欧拉函数是积性函数，我们知道(varphi(s)|varphi(m))所以有(p^{varphi(m)}≡p^{varphi(s)}(mod s))
设(p^{varphi(s)}=xs+1)
那么(p^{varphi(s)+k}=xm+p^k)
所以(p^{varphi(s)+k}≡p^k (mod m))，也有(p^{varphi(m)+k}≡p^k (mod m))
当(b>=k)时，(p^b≡p^{b-k}·p^k≡p^{b-k}·p^{varphi(s)+k}≡p^{b+varphi(m)}(mod m))
又因为(k<=varphi(p^k)<=varphi(m))，所以当(b>=2varphi(m))时，满足(p^b≡p^{b-varphi(m)}(mod m))
注意是(2varphi(m))!
所以可以得到(p^b≡p^{b\%varphi(m)+varphi(m)}(mod m))
因此我们可以得到对任意质数(p)都有(b>=2varphi(m),p^b≡p^{b\%varphi(m)+varphi(m)}(mod m))
非(m)质因子的(p)，有欧拉定理
将(a)因式分解，可以得到
(a^b≡a^{b\%varphi(m)+varphi(m)}(mod m))
- 注意 (b<varphi(m))时，公式不一定成立

线性筛法

类似与筛素数，我们在这里利用欧拉函数是积性函数这个性质来筛(varphi)
(mathcal{Code})

int cnt;
int prime[maxn],phi[maxn];
bool vis[maxn];
void Euler_sieve (int n)
{
	phi[1]=1;
	for (int i=2;i<=n;++i){
		if (!vis[i])	prime[++cnt]=i,phi[i]=i-1;
		for (int j=1;j<=cnt&&i*prime[j]<=n;++j){
			vis[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]];
		}
	}
}

欧拉反演

利用欧拉函数的一条性质
(egin{aligned}n=sum_{d|n}varphi(d)end{aligned})
(上面有证明)
我们试着把(n)换成其他东西试试
(egin{aligned}gcd(i,j)=sum_{d|gcd(i,j)}varphi(d)=sum_{d|i}sum_{d|j}varphi(d)end{aligned})
让我们求个东西试试
(egin{aligned}sum_{i=1}^ngcd(i,n)=sum_{i=1}^nsum_{d|i}sum_{d|n}varphi(d)=sum_{d|n}sum_{i=1}^nsum_{d|i}varphi(d)=sum_{d|n}frac{n}{d}varphi(d)end{aligned})
把它重写一遍作为结论
(egin{aligned}sum_{i=1}^ngcd(i,n)=sum_{d|n}frac{n}{d}varphi(d)end{aligned})

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
如能得到推荐博主就更开心了
您的鼓励是博主的动力