欧拉函数

定义

对于正整数$n$，其对应的欧拉函数值即为n以内所有与n互质的正整数的个数

形式化的：

对于布尔值$b$,记符号

$$ [b]=\begin{cases} 1 & \text{if b = true} \\ 0 & \text{if b = false} \end{cases} $$

以后在布尔值外面的该符号默认为该定义

对于欧拉函数，有：

$$ \varphi (n) = \sum_{i=1}^{n} [(n,i)=1] $$

为了方便起见，当我们记$x\in\varphi(n)$时，即指$1$到$n$中与n互质的数所构成的集合。

积性函数

干啥都要用到积性，不如一证了之。
$proof:$

$先证\varphi(np)(p\in \mathbb{P})的情况:$

$1^{\circ} p|n:$

$我们把1,2,\cdots,np-1,np这些数分成p个长度都是n的部分，$
$每个数如果原来和n互质，由于np没有新的质因数，那么它也和np互质$
$而因为(a+kn,n)=(a,n)(k\in \mathbb{Z}),每个块中与n互质的数位置是一样的$
$那么显然，此时\varphi(np)=\varphi(n)\times p$

$2^{\circ} p\bot n:$

$与上面的情况不同，p不是n的因数，而是新的质因数，那么原来与n互质的数有可能和np不互质 $
$依旧把1,2,\cdots,np-1,np这些数分成p个长度都是n的部分 $
$发现，如果一个数想和np互质，那么他至少要和n互质$
$所以此时与np互质的数一定是上种情况的那些数的子集$
$观察哪些数是与n互质但和np不互质的 $
$发现原来集合\varphi(n)中的每个数乘p后都符合这个条件$
$即\forall x\in\varphi(n),x\bot n,(xp,np)=p>1$
$并且这些数一定是与n互质的，所以一定在上面那种情况的集合中$
$剩下的数，既与n互质，又不是p的倍数，也就是与p没有公因数，那必定是符合条件的$
$这些数刚好有\varphi(n)个，所以此时\varphi(np)=\varphi(n)\times p-\varphi(n)=\varphi(n)\times (p-1)$

$1^{\circ}和2^{\circ}的结论是欧拉筛线性求\varphi的有力递推工具$

$综上，计算\varphi(n)时，可以将n质因数分解为\Pi_{i}^{m}p_i^{\alpha_i}(m就是质因数个数)$
$我们根据上面的得到的对于质数的公式一个一个把质因数乘进去$
$发现，第一次乘某个质数p时会导致\varphi 的值只乘了p-1$
$那么我们换一种思路去考虑他的贡献，它还是把p乘上了，只不过第一次还要多乘\frac{p-1}{p}$
$那么答案很简单了：\varphi(n)=\Pi_{i}^{m}(p_i^{\alpha_i}\times\frac{p_i-1}{p_i})$
$=\Pi_{i}^{m}p_i^{\alpha_i}\times\Pi_{i}^{m}\frac{p_i-1}{p_i}$
$=n\cdot\Pi_{i}^{m}\frac{p_i-1}{p_i}$
$这就是欧拉函数的一个著名的公式。$
$这个公式有个很感性的理解方法：对于n的每个质因子，有1-\frac1p的概率是合法的；$
$由于质数互相独立，这些事件都是独立事件，直接把概率乘起来，再乘总个数就是答案$
$这个方法也可以通过严谨证明均匀性来的得到严谨证法$

$然后考虑命题：\forall a\bot b,\varphi(ab)=\varphi(a)\varphi(b)$
$当a,b互质的时候，显然a,b没有共同的质因子$
$那么对于我们刚推出来的公式，前部分和后部分都是符合积性的$
$积性显然得证。$

狄利克雷卷积

我们定义如下运算：
$f,g,h都是数论函数$
$当有\sum_{d|n}f(d)\cdot g(\frac{n}{d}) =h(n)时，则记作：$

$$ f * g =h $$

"$*$"是狄利克雷卷积符号，上述过程称作一次狄利克雷卷积。

性质

存在以下命题成立：

$$ \varphi * 1 = id $$

$id即为数论函数id(n)=n$
即证：

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

证明思路如下：
在数论中的奇妙相等关系，我们总是要尝试找到一一对应的关系
我们希望能把 左式$每个d的\varphi集合$ 与 右式$\{1,2,\cdots\,n\}$ 一一对应
如果集合一一对应，那么集合元素个数相等就不言而喻了

对于一组整数$a,b$，显然有与之唯一对应的$(a,b)$
我们可以定义使$(n,a)$相等的$a$为$n$的一个同约系，其中$(n,a)$定义为此时的同约数（例如$\{2,10\}$就是$12$的一个同约系，同约数为$2$）

那么$\{1,2,\cdots\,n\}$就可以不重不漏的分成若干个同约系
对于每个同约数$d$，其必定是$n$的因数，并且这些数构成了集合$\varphi(n)$，
并且根据因数总是成对出现的，发现$\frac nd$也符合这个性质。

对于同约数为$d$的同约系，对每个数除以$d$后，一定与$\frac nd$互质
于是发现这些数刚好构成了集合$\varphi(\frac nd)$

这与左边是完全等价的，可以理解为左边就是$\{1,2,\cdots\,n\}$拆分成的同约系的加和。

证毕。

存在以下命题成立：

$$ \varphi = id * \mu $$

$\mu定义如下：$

$$ \mu (n)=\begin{cases} 1 & \text{if n=1} \\ 0 & \text{if 有平方因子} \\ (-1)^k & \text{otherwise k为质因数个数} \end{cases} $$

即证：

$$ \mu * 1 = \backepsilon $$

$\backepsilon定义如下：$

$$ \backepsilon (n)=\begin{cases} 1 & \text{if n=1} \\ 0 & \text{if n>1} \end{cases} $$

即证：

$$ \sum_{d|n}\mu(d) = \begin{cases} 1 & \text{if n=1} \\ 0 & \text{if n>1} \end{cases} $$

$\text{(i) n=1时显然成立}$
$\text{(ii) n>1}$
$根据排列组合写出组合式：$

$记k为n不同质因数个数$

$$ \mu(n) = \sum_{i=0}^{k}\binom{i}{k}\times (-1)^i $$

$根据二项式定理：$

$$ (1+x)^n=\sum_{i=0}^{n}\binom{i}{n}\times x^i $$

$代入x=-1$

$$ \mu(n) = \sum_{i=0}^{k}\binom{i}{k}\times (-1)^i=(1+(-1))^k=0 $$

$证毕$

$E.N.D$