![](https://csdnimg.cn/release/download_crawler_static/86328467/bg4.jpg)
为了彻底了解积性函数的运算,本节以欧拉函数为例进行讲解,这是一个经典的积性
函数。
并用这个例子引导出为什么要使用杜教筛。
2.1 欧拉函数的定义和性质
定义
①
:设 n 是一个正整数,欧拉函数
定义为不超过 n 且与 n 互质的正整数的个数。
定义用公式表示:
例如:
n = 4 时,1、3 这 2 个数与 4 互质,
;
n = 9 时,1、2、4、5、7、8 这 6 个数与 9 互质,
。
【定理 2.1】
②
:设 p 和 q 是互质的正整数,那么
。
这个定理说明欧拉函数是一个积性函数。有以下推理:
若
,其中 p
1
、p
2
、...、p
s
互质,a
1
、a
2
、...、a
s
是它们的幂,则
)(...)()()(
21
21
s
a
s
aa
pppn
。
如果
p
1
、p
2
、...、p
s
互质,那么 p
1
a1
、p
2
a2
、...、p
s
as
也是互质的。
以 n = 84 为例:
)7()3()2()732()84(
73284
22
2
【定理 2.2】设 n 为正整数,那么:
其中 d|n 表示 d 整除 n,上式对 n 的正因子求和。 例如 n=12,那么 d 是 1、2、3、4、6、
12,有:
)12()6()4()3()2()1(12
这个定理说明了 n 与
的关系:n 的正因子(包括 1 和自身)的欧拉函数之和等于 n。
有很多方法可以证明。这里给出一种直接易懂的证明。
证明:分数
,共有 n 个,且互不相等。化简这些分数,得到新的 n 个分数,它
们的分母和分子互质,形如
,
且 a 与 d 互质。在所有 n 个分数中,分母为 d 的分数,
数量是
。所有不同分母的分数,其总数是
,所以
,得证。
定理 2.2 是欧拉函数特别重要的一个性质,这一性质被用到了杜教筛中。
2.2 求欧拉函数的通解公式
欧拉函数有什么用呢?利用它可以推出欧拉定理
③
,欧拉定理可用于:求大数的模、
求解线性同余方程等,在密码学中有重要应用。所以求
是一个常见的计算。
从定理 2.1 可以推出定理 2.3,
定理 2.3 是计算
的通解公式。
【定理 2.3】设:
为正整数 n 的质幂因子分解,那么:
k
i
ik
p
n
ppp
nn
1
21
)
1
1()
1
1)...(
1
1)(
1
1()(
上述公式,有两个特殊情况:
(1)若 n 是质数,
。这一点很容易理解,请读者思考。
(2)若
,p 是质数,有:
①
《初等数论及其应用》172 页,欧拉定理。
②
有关欧拉函数的所有证明,见《初等数论及其应用》176-180 页。
③
欧拉定理:设 m 是一个正整数,a 是一个整数且(a, m)=1,那么
。