Applications of unique factorization

一些算术函数

定义 如果整数 $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)$

0 Shares:
发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注