数学笔记19960208
今日阅读R.Courant与H.Robbins的数学名著《数学是什么》.在欧拉函数$\varphi(n)$一节中,给出了一个公式:如果
\[n = p_1^{\alpha_1}\cdots p_r^{\alpha_r},\]
则
\[\varphi(n) = n(1 – \frac{1}{p_1}) \cdots(1 – \frac{1}{p_r}).\]
书中未给出证明,一般的数论教材(例如维诺格拉多夫的《数论基础》)中均可找到证明.
注意到$\varphi(n)$的定义:在1到$n$中与$n$互素的整数个数.
我们一般都是从简单的入手,从特殊到一般.
(1)$n$为素数$p$时,显然有$\varphi(p)=p-1$,这无疑是最简单的.
(2)$n=p^{\alpha}$,
$\alpha=2$时,与$n$有大于1的公因子的数有$pk$,$k=1,2,\cdots,p$,于是$\varphi(p^2)=p^2-p$.
$\alpha=3$时,与$n$有大于1的公因子的数有$pk$,$k=1,2,\cdots,p^2$,于是$\varphi(p^3)=p^3-p^2$.
我们有理由做这样的猜测:令
\[S(n) = \{m | (n,m=d), d > 1, 1 \le m \le n\},\]
并且用$|S|$表示集$S$中的元素个数,则
\[|S(p^{\alpha})|=p^{\alpha-1}.\]
关于自然数的命题,常采用的一个方法是数学归纳法:
(i)当$\alpha=1$时成立;
(ii)假设对于$\alpha$时成立,则对于$\alpha+1$的情形,
$p \cdot p^{\alpha}$,对于$p$有
\[pi:i=1,2 \cdots p-1,2p-1,\cdots, p^{\alpha}-1,\]
一共$(p-1)p^{\alpha-1}=p^{\alpha}-p^{\alpha-1}$个.
\[p^ki:i=1,2 \cdots p-1,2p-1,\cdots, p^{\alpha+1-k}-1,\]
一共$(p-1)p^{\alpha-k}$个,故
\[\begin{aligned}|S(p^{\alpha+1})|&=\sum_{k=1}^{\alpha}{(p-1)p^{\alpha-k}}+1 \\&=(p-1)\sum_{k=1}^{\alpha}{p^{\alpha-k}}+1 = (p-1)(p^{\alpha-1} + p^{\alpha-2} + \cdots + 1)+1 \\&=(p-1)(\frac{1-p^{\alpha}}{1-p}) + 1 = p^{\alpha}-1+1=p^{\alpha}.\end{aligned}\]
这里对于$\alpha$到$\alpha+1$之间没有用归纳假设,不能算是归纳法,下面直接计算.$n=p^{\alpha}$
\[pi:i=1,2 \cdots p-1,2p-1,\cdots, p^{\alpha-1}-1,\]
一共$(p-1)p^{\alpha-2}$个.
\[p^ki:i=1,2 \cdots p-1,2p-1,\cdots, p^{\alpha-k}-1,\]
一共$(p-1)p^{\alpha-k-1}$个,一共有
\[1 + \sum_{k=1}^{\alpha-1}{(p-1)p^{\alpha-k-1}}=p^{\alpha-1}\]
个.也就是
\[|S(p^{\alpha})|=p^{\alpha-1}.\]
从而$\varphi(p^{\alpha}) = p^{\alpha}-p^{\alpha-1}$.
(3)$n=p_1^{\alpha_1}p_2^{\alpha2}$,$\varphi(n)=\varphi(p_1^{\alpha_1})\varphi(p_2^{\alpha_2})$.即证明$\varphi(n)$是积性函数.也就是要证明:若$n=n_1n_2$,$(n_1,n_2)=1$,则$\varphi(n)=\varphi(n_1)\varphi(n_2)$.
对于$n_1$一共有$\varphi(n_1)$个与$n_1$互素,如果再用(2)的方法,无疑比较麻烦,必须寻找其他方法了.
备注:上面部分是以前的笔记,这里补充如下.
首先是计算$\varphi(p^{\alpha})$,注意到如果$(m, p^{\alpha})>1$,必有$p|m$,于是$m=pK$,显然$K=1,2,\cdots,p^{\alpha-1}$都是满足条件的,于是剩下的部分都是和$p^{\alpha}$互素的,于是
\[\varphi(p^{\alpha}) = p^{\alpha}-p^{\alpha-1}.\]
其次是关于$\varphi(n)$是积性函数这个结论,在韦伊的《数论入门》的第六节的习题7中给出了.
书中的思路是:对于和$nm$互素的整数$l$,必然与$m$,$n$都是互素的,于是$l(\mod{m})$和$l(\mod{n})$建了一个对应关系,只要证明这个关系是一一对应即可.
维诺格拉多夫的《数论基础》关于这个欧拉公式的证明也是使用了积性函数的概念,只不过他不是直接证明$\varphi(n)$是积性函数,而是利用了麦比乌斯函数的一些性质.所谓麦比乌斯函数$\mu(a)$定义如下:$\mu(a)=0$,如果$a$被1以外的平方数除尽;$\mu(a)=(-1)^k$,如果$a$不能被1以外的平方数除尽,这是$k$表示数$a$的素因子的个数.关于$\mu(a)$有这样一个很有用的性质:
\[\sum_{d|a}{\mu(d)} = \begin{cases}0, &\text{如果}a > 1\\1, &\text{如果}a=1\end{cases}\]
如果把这个性质和线性空间的$\delta_{ij}$,正交相关的一些概念比较,会发现一点类似的地方,他就像投影一样,筛选出我们需要的部分,而过滤掉不需要的部分.详细的证明过程见课本.