欧拉函数基础

欧拉函数基础

定义

​ $\varphi(n)$ 即考虑 $[~1~,~n-1~]$ 中与 $x$ 互质的个数。

几个简单的引理

​ 当 $n$ 为质数时，那么由质数的定义可知 $[~1~,~n-1~]$ 中的整数均与 $n$ 互质，即 $\varphi(n)=n-1$。

​ 当 $n=p^k$ 且 $p$ 为质数时，那么与 $n$ 互质的数即为不含 $p$ 素因子的数，容斥一下，易知：

$\varphi(n)=n-\frac{n}{p}=p^{k-1}(p-1)=p^{k-1}\varphi(p)$

欧拉函数积性证明

一直在找有关严谨的证明，但是初等数论的剩余系内容晦涩难懂

​ 对于任意互质的正整数 $n,m$ 都有 $\varphi(nm)=\varphi(n)\varphi(m)$。

​ 我们考虑到满足 $k \in [~0~,~m-1~]$ 的闭区间 $[~kn+1~,~(k+1)n~]$ 都是一个模 $n$ 意义下的完全剩余系；且对于满足 $k \in [~0~,~n-1~]$ 的闭区间 $[~km+1~,~(k+1)m~]$ 都是一个模 $m$ 意义下的完全剩余系。（剩余系即对于任意两个同属于其中的元素在模意义下都不同余，且每种余数都恰好出现一次）

​ 那么每一个模 $n$ 意义下的完全剩余系中都存在 $\varphi(n)$ 个数满足 $\gcd(x,n)=1$，且每一个模 $m$ 意义下的完全剩余系中都存在 $\varphi(m)$ 个数满足 $\gcd(x,m)=1$。

​ 由于 $\gcd(n,m)=1$，考虑到满足 $\gcd(x,nm)=1$ 的数需要同时满足 $\gcd(x,n)=1$ 且 $\gcd(x,m)=1$，那么显而易见的，$\varphi(nm)=\varphi(n)\varphi(m)$。

这个证明貌似并不严谨

​ 然而我们手玩几组数据后发现 $\varphi(x)$ 并不是一个完全积性函数，必须要满足 $\gcd(n,m)=1$。

​ 因为对于模 $n$ 意义下的完全剩余系和模 $m$ 意义下的完全剩余系中，我们选取出了两个数 $a,b$ 作为 $x$ 分别对 $n,m$ 取模后的余数。如果不满足 $\gcd(n,m)=1$，那么仅拥有 $a,b$ 两个数无法确定 $x$ 本身的值。那么也就是说，在 $\gcd(n,m)=1$ 时，$a,b$ 与 $x$ 分别一一对应；而 $\gcd(n,m)\ne 1$ 时，可能有多个 $x$ 对应同一个 $a,b$，但是因为 $n\times m=nm$，意味着可能不存在 $x$ 与 $a,b$ 对应。例如 $n=4,m=6$ 时，$5,17$ 对 $4$ 取模余 $1$，对 $6$ 取模余 $5$；同时，没有任何一个整数满足对 $4$ 取模余 $0$，对 $6$ 取模余 $1$。这个和裴蜀定理有相通之处。

欧拉函数的构造

​ 考虑到对于每个数进行质因数分解，根据算术基本定理，则有：

$x=\prod_{i=1}^{k} p_i^{\alpha_i} \\ \varphi(x)=\prod_{i=1}^{k}\varphi(p_i^{\alpha_i})$

​ 此时根据 $\varphi(p^k)$ 的引理易知：

$\varphi(x)=\prod_{i=1}^{k}{p_i}^{\alpha_i-1} \varphi(p_i)$

​ 且根据算术基本定理易知：

$\varphi(x)=x\prod_{i=1}^{k}\frac{p_i-1}{p_i}=x\prod_{i=1}^{k}(1-\frac{1}{p_i})$

​ 放一份代码，线性求欧拉函数其实大体参照欧拉筛：

（原理是对于每一个合数只被其最小质因数判掉，减少多余的判断次数）

for(int i=2;i<=n;i++)
{
	if(!vis[i])
	{
		pri[++cnt]=i;
		phi[i]=i-1;
	}
	for(int j=1;j<=cnt;j++)
	{
		if((lint)i*pri[j]>n) break;
		vis[i*pri[j]]=true;
		if(!(i%pri[j]))
		{
			phi[i*pri[j]]=phi[i]*pri[j];
			break;
		}
		else phi[i*pri[j]]=phi[i]*(pri[j]-1);
	}
}

一些好玩的定理

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

​ 由算术基本定理易知：

$n=\prod_{i=1}^{k} {p_i}^{\alpha_i} \\ \sum_{d|n}\varphi(d)=\prod_{i=1}^{k}\sum_{j=0}^{\alpha_i}\varphi({p_i}^{j}) \\ \prod_{i=1}^{k}\sum_{j=0}^{\alpha_i}\varphi({p_i}^{j})=\prod_{i=1}^{k} \sum_{j=0}^{\alpha_i}{p_i}^{j}-{p_i}^{j-1}=\prod_{i=1}^{k}{p_i}^{\alpha_i}=n$

这好像就是著名的欧拉反演公式？

欧拉定理

​ 著名的欧拉定理，同时也是费马小定理更深刻的理解：

​ 考虑对于任意的整数 $n$ 都有与其互质的整数 $a$ 满足：

$a^{\varphi(n)}\equiv1\pmod{n}$

​ 考虑对 $n$ 的既约剩余系累积，令 $r_i$ 表示其一种既约剩余系。

$\prod_{i=1}^{\varphi(n)}r_i$

​ 且知同余的性质满足：

$ab \equiv ac \pmod{m}$

​ 等价于：

$b \equiv c \pmod{\frac{m}{\gcd(m,a)} }$

​ 且因为 $\gcd(a,n)=1$，那么易知：

$\prod_{i=1}^{\varphi(n)}r_i \equiv \prod_{i=1}^{\varphi(n)} a r_i \equiv a^{\varphi(n)} \prod_{i=1}^{\varphi(n)} r_i \pmod{n}$

​ 且因为 $r_i$ 为 $n$ 的既约剩余系，即 $\gcd(r_i,n)=1$，那么就有：

$a^{\varphi(n)} \equiv 1 \pmod{n}$

​ 而当 $n$ 为质数 $p$ 时，$\varphi(p)=p-1$：

$a^{p-1} \equiv 1 \pmod{p}$

​ 这就是费马小定理。

为扩展欧拉定理留个坑位吧