欧拉函数

欧拉函数记作 $\varphi(n)$ 表示在 $n$ 一下的正整数中，有多少个数与 $n$ 互质。

欧拉函数满足以下性质：

1. $\varphi(p)=p-1$，其中 $p$ 为质数。
2. 欧拉函数是积性函数，也就是对于 $a\perp b$ 满足 $\varphi(ab)=\varphi(a)\cdot \varphi(n)$。
3. $\sum_{d\mid n}\varphi(d)=n$。

狄利克雷卷积

对于两个函数 $f$ 和 $g$，他们的狄利克雷卷积的定义如下：

$f(x)*g(x)=\sum\limits_{d\mid n} f(d)\cdot g(\dfrac{n}{d})=\sum\limits_{ab=n}f(a)\cdot g(b)$

狄利克雷卷积满足以下性质：

1. 交换律：$f*g=g*f$
2. 结合律：$f*g*h=f*(g*h)$
3. 分配律：$f*(g+h)=f*g+f*h$

函数 $\varepsilon(n)=[n=1]$，它是狄利克雷卷积的单位函数，任意函数都满足 $f(x)*\varepsilon(x)=f(x)$。

对于函数 $f(x)\ne 0$ 的，如果 $g*f=\varepsilon$，那么称 $g$ 为 $f$ 的逆元。

重要性质：

1. 两个积性函数的狄利克雷卷积还是积性函数。
2. 积性函数的逆元还是积性函数。

莫比乌斯函数

莫比乌斯函数 $\mu(n)$ 为莫比乌斯函数，其定义如下：

$\mu(n)= \left\{\begin{matrix} 1 & n=1\\ 0 & n\text{ 含有平方因子}\\ (-1)^k & k\text{ 为 }n\text{ 本质不同的因子个数} \end{matrix}\right.$

莫比乌斯函数有以下性质：

$\sum\limits_{d\mid n}\mu(d)=[n=1]$

可以转化成：

$\sum\limits_{d\mid n}\mu(n)=\varepsilon (n),\mu*1=\varepsilon$

设 $f(n)$ 和 $g(n)$ 为两个数论函数，那么：

$g(n)=\sum_{d\mid n}\mu(d)\cdot f(\frac{n}{d})$

还有：

$g(n)=\sum_{n|d}\mu(\frac{d}{n})\cdot f(d)$

阶

由欧拉定理可知，对 $a\in \mathbf{Z}$，$m\in\mathbf{N}^{*}$，若 $\gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv 1\pmod m$.

因此满足同余式 $a^n \equiv 1 \pmod m$ 的最小正整数 $n$ 存在，这个 $n$ 称作 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$ 或 $\operatorname{ord}_m(a)$.

阶有以下性质：

1. $a,a^2,\cdots,a^{\delta_m(a)}$ 模 $m$ 两两不同余。
2. 若 $a^n \equiv 1 \pmod m$，则 $\delta_m(a)\mid n$.
3. 设 $m\in\mathbf{N}^{*}$，$a,b\in\mathbf{Z}$，$(a,m)=(b,m)=1$，则 $\delta_m(ab)=\delta_m(a)\delta_m(b),\left(\delta_m(a), \delta_m(b)\right)=1$。
4. 设 $k \in \mathbf{N}$，$m\in \mathbf{N}^{*}$，$a\in\mathbf{Z}$，$(a,m)=1$，则 $\delta_m(a^k)=\dfrac{\delta_m(a)}{\left(\delta_m(a),k\right)}$。

原根

设 $m \in \mathbf{N}^{*}$，$g\in \mathbf{Z}$. 若 $(g,m)=1$，且 $\delta_m(g)=\varphi(m)$，则称 $g$ 为模 $m$ 的原根。

即 $g$ 满足 $\delta_m(g) = \left| \mathbf{Z}_m^* \right| = \varphi(m)$. 当 $m$ 是质数时，我们有 $g^i \bmod m,\,0 \lt i \lt m$ 的结果互不相同。

设 $m \geqslant 3, \gcd(g,m)=1$，则 $g$ 是模 $m$ 的原根的充要条件是，对于 $\varphi(m)$ 的每个素因数 $p$，都有 $g^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m$.

若一个数 $m$ 有原根，则它原根的个数为 $\varphi(\varphi(m))$.

一个数 $m$ 存在原根当且仅当 $m=2,4,p^{\alpha},2p^{\alpha}$，其中 $p$ 为奇素数，$\alpha\in \mathbf{N}^{*}$.