一些算术函数
定义 如果整数 $a$ 不能被一个整数的平方整除, 则称 $a$ 为 square-free.
命题2.2.1 任一整数 $n\in\mathbb{Z}$ 可以写成 $ab^2$, 其中 $a$ 是 square-free 的, $b\in \mathbb{Z}$.
证明: 利用唯一因子分解定理, 即得.
下面这些函数都是定义在正整数上的.
| 符号 | 描述 | 计算(设 $n=p_1^{\alpha_1}…p_l^{\alpha_l}$) |
| $\nu(n)$ | $n$ 的正因子的个数 | $\nu(n) = (a_1+1)(a_2+1)…(a_l+1)$ |
| $\sigma(n)$ | $n$ 的正因子的和 | $\sigma(n) = (p_1^{\alpha_1}-1)/(p_1-1)…(p_l^{\alpha_l})$ |
| $\mu(n)$ | M\”{o}bius $\mu$ function | $\mu(1)=1,\mu(p_1p_2…p_l)= (-1)^l,\mu(\text{其它})=0$ |
| $\mathbb{I}(n)$ | $1$ 的示性函数 | $\mathbb{I}(1)=1,\mathbb{I}(n)=0,n>1$ |
| $I(n)$ | $n$ 为正整数, 则为$1$, 可以认为是常数 $1$ | $I(n) = 1,n\in \mathbb{Z}^+$ |
| $\phi(n)$ | $1$ 到 $n$ 中与 $n$ 互素的整数的个数 | $\phi(n) = n(1-(1/p_1))…(1-(1/p_l))$ |
定义 Dirichlet multiplication $f \circ g(n) = \sum f(d_1)g(d_2)$, 其中 $d_1 d_2 =n$
这些算术函数的性质.
命题2.2.3 当 $n>1$, $\sum_{d\mid n} \mu(d) =0$
证明: $\sum_{d | n} \mu(d) = \binom{l}{0}+\binom{l}{1} (-1)+…+\binom{l}{l}(-1)^l = (1-1)^l=0$
引理 $I\circ \mu = \mu \circ I = \mathbb{I}$
证明: $I\circ \mu (n)= \mu \circ I (n)= \sum_{d|n} \mu(d) $. 当 $n=1$ 时, $\sum_{d|n} \mu(d) =1$.当 $n>1$ 时, $\sum_{d|n} \mu(d) =0$.
定理2 M$\ddot{\text{o}}$bius Inversion Theorem 设 $F(n) = \sum_{d|n} f(d)$, 则 $f(n)= \sum_{d|n}\mu(d) F(n/d)$
证明: $F=f\circ I$. $F\circ \mu = f\circ I \circ \mu = f\circ \mathbb{I}$. $$\sum_{d|n}\mu(d) F(n/d)=F\circ \mu(n)=f\circ \mathbb{I}(n) = f(n)$$
这个定理还有一般的 Abel 群的版本.
如果是乘法 Abel 群 $F(n) =\prod_{d|n} f(d)$, 则 $f(n) = \prod_{d|n} F(n/d)^{\mu(d)}$
命题2.2.4 $\sum_{d|n} \phi(d) = n$
证明: 考察 $n$ 个分数 $1/n,2/n,…,(n-1)/n,n/n$. 把这 $n$ 个分数化简成两个互素的整数的差,即知.
命题2.2.5 若 $n= p_1^{\alpha_1}…p_l^{\alpha_l}$, 则 $$\phi(n) = n (1-(1/p_1))…(1-(1/p_l))$$
证明: 这个命题的证明主要用到了 M$\ddot{\text{o}}$bius Inversion Theorem
$n = \sum_{d|n} \phi(d)$, 所以 \begin{array}{ll}\phi(n)&= \phi(n) = \sum_{d|n} \mu(d) n/d\\ &= n +n\sum n/p_i + n \sum n/(p_i p_j) + …\\ &= n (1-(1/p_1))…(1-(1/p_l))\end{array}
$\sum 1/p$ 发散
定理3 $\sum 1/p$ 发散, 其中 $p$ 是 $\mathbb{Z}$ 中的正素数.
证明: 设 $p_1,…,p_{l(n)}$ 是小于 $n$ 的正素数. 设 $\lambda(n) = \sum_{p_i} (1-1/p_i)^{-1}$. 下面的思路是证明 $\lambda(n) \to \infty$ as $n \to \infty$. 再对 $\lambda(n)$ 取对数, 得 $\ln(\lambda(n)) < \sum 1/p_i + \sum 1/p_i^2$. 所以若 $\sum 1/p$ 收敛, 则 $\lambda(n)$ 有界, 矛盾.
定理4 $q$元有限域上的多项式环, $\sum q^{- \deg p(x)}$ 发散, 其中 p(x) 是首一的不可约多项式.
证明: 仿照上一定理的证明.
The Growth of $\pi (x)$
