「Note」2022-07-18 Number Theory Functions Review

大概去年也写过这样的东西。
但是很水，算是啥都没有，今天重写一遍，没有证明，整理有关数论函数的一些东西。

欧拉函数 $\large \mathcal{\varphi}$

定义 $\mathtt{Definition}$

$\varphi(n) = \sum_{i = 0}^{n - 1} [\gcd(i,n) = 1]$，有 $\varphi(1) = 1, \varphi(p) = p - 1$。 ### 性质 $\mathtt{Properties}$ $$n^{\varphi(m)} \equiv 1 (\mathrm{mod} \ m), n \bot m \tag{1}$$ $$\varphi(p^k) = p^k - p^{k - 1} \tag{2}$$ $$\varphi(m_1m_2) = \varphi(m_1) \varphi(m_2), m_1 \bot m_2 \tag{3}$$ $$\varphi(m) = \prod_{p} \varphi(p^{e_p}), m= \prod_{p}p^{e_p} \tag{3.1}$$ $$\varphi(m) = m \prod_{p \mid m} (1 - \frac{1}{p}), m= \prod_{p}p^{e_p} \tag{3.2}$$ $$ a^x\equiv \begin{cases} a^{x\bmod\varphi(m)} & (a,m)=1 \\ a^{x\bmod\varphi(m)+\varphi(m)} & (a,m)\neq1,x\ge\varphi(m) \end{cases} \pmod m \tag{4} $$

反演 $\mathtt{Inversion \ Principle}$

$$m = \sum_{d \mid m} \varphi(d)$$

尝试对这个式子做一些替换。
$$ \begin{aligned} \gcd(i, j) &= \sum_{d \mid \gcd(i, j)} \varphi(d) \\ &=\sum_{d \mid i} \sum_{d \mid j} \varphi(d) \\ \end{aligned} $$
可以试着求个东西。
$$ \begin{aligned} \sum_{i = 1}^{n} \gcd(i, n) &= \sum_{i = 1}^{n} \sum_{d \mid i} \sum_{d \mid n} \varphi(d) \\ &=\sum_{d \mid n} \sum_{i = 1}^{n} \sum_{d \mid i} \varphi(d) \\ &=\sum_{d \mid n} \lfloor \frac{n}{d} \rfloor \varphi(d) \end{aligned} $$
这个可以当作结论记下来。

莫比乌斯函数 $\large \mu$

定义 $\mathtt{Definition}$

$\mu(m) = \sum_{d \mid m} \mu(d) = [m = 1]$，有 $\mu(1) = 1$ 。 ### 性质 $\mathtt{Properties}$ $$\mu(m) = \prod_{p \mid m} \mu(p^{e_p}) = \left{\begin{matrix} \end{matrix}}, m= \prod_{p}p^{e_p} \tag{5}$$

反演 $\mathtt{Inversion \ Principle}$