the basic concept of number-theoretic functions (also called arithmetic functions):
- Definition: A function \(y = f(n)\) whose domain is a set of integers is defined as a number-theoretic (or arithmetic) function.
- Common Examples: Familiar functions like Euler’s totient function \(\varphi(n)\), the divisor-counting function \(d(n)\) (often denoted \(\tau(n)\)), and the divisor-sum function \(\sigma(n)\) are all number-theoretic functions, which are essential tools in number theory research.
For any positive integer n, let its prime factorization be \(n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}\), where \(p_1, p_2, \dots, p_k\) are distinct prime numbers and \(\alpha_1, \alpha_2, \dots, \alpha_k\) are their corresponding positive exponents. The three functions can be computed using the following formulas derived from this factorization:
- Euler’s totient function \(\varphi(n)\): Counts the number of positive integers ≤ n that are coprime with n.Formula: \(\varphi(n) = n \cdot \left(1 – \frac{1}{p_1}\right)\left(1 – \frac{1}{p_2}\right) \dots \left(1 – \frac{1}{p_k}\right)\)
- Divisor-counting function \(d(n)\): Gives the total number of positive divisors of n.Formula: \(d(n) = (\alpha_1 + 1)(\alpha_2 + 1) \dots (\alpha_k + 1)\)
- Divisor-sum function \(\sigma(n)\): Calculates the sum of all positive divisors of n.Formula: \(\sigma(n) = \frac{p_1^{\alpha_1 + 1} – 1}{p_1 – 1} \cdot \frac{p_2^{\alpha_2 + 1} – 1}{p_2 – 1} \cdot \dots \cdot \frac{p_k^{\alpha_k + 1} – 1}{p_k – 1}\)
1. Preliminary: Integer Set D
Let D be a set of integers closed under multiplication: for any \(m, n \in D\), their product mn is also in D.
2. Multiplicative Function
A number-theoretic function \(f(n)\) defined on D is called multiplicative if for all coprime integers \(m, n \in D\) (i.e., \(\gcd(m, n) = 1\)), the following holds:
\(f(mn) = f(m)f(n)\)
3. Completely Multiplicative Function
A number-theoretic function \(f(n)\) defined on D is called completely multiplicative if for all integers \(m, n \in D\) (regardless of whether they are coprime), the following holds:
\(f(mn) = f(m)f(n)\)
Let \(f(n)\) be a non-zero number-theoretic function. For any positive integer n, let its prime factorization be:
\(n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}\)
where \(p_1, p_2, \dots, p_k\) are distinct primes, and \(a_1, a_2, \dots, a_k\) are positive integer exponents.
1. Necessary and Sufficient Condition for Multiplicative Functions
A function \(f(n)\) is multiplicative if and only if:
- \(f(1) = 1\);
- For any positive integer n, \(f(n)\) equals the product of its values at the prime power components of n:\(f(n) = f(p_1^{a_1}) \cdot f(p_2^{a_2}) \cdot \dots \cdot f(p_k^{a_k})\)
2. Necessary and Sufficient Condition for Completely Multiplicative Functions
A function \(f(n)\) is completely multiplicative if and only if:
- \(f(1) = 1\);
- For any positive integer n, \(f(n)\) equals the product of its values at the prime components of n, each raised to the corresponding exponent:\(f(n) = \left[f(p_1)\right]^{a_1} \cdot \left[f(p_2)\right]^{a_2} \cdot \dots \cdot \left[f(p_k)\right]^{a_k}\)
Key Difference & Examples
The core distinction lies in the scope of the multiplicative property:
- A multiplicative function satisfies \(f(mn) = f(m)f(n)\) only for coprime integers \(m,n\). To compute \(f(n)\), you need \(f(p^a)\) for each prime power \(p^a\).
- A completely multiplicative function satisfies \(f(mn) = f(m)f(n)\) for all integers \(m,n\). To compute \(f(n)\), you only need \(f(p)\) for each prime p, raised to its exponent.
As noted, \(\varphi(n)\), \(d(n)\), and \(\sigma(n)\) are multiplicative but not completely multiplicative:
- \(\varphi(4)=2 \neq [\varphi(2)]^2=1\)
- \(d(4)=3 \neq [d(2)]^2=4\)
- \(\sigma(4)=7 \neq [\sigma(2)]^2=9\)
数论函数（算术函数）** 的基础概念，核心内容包括：
- 定义：若函数 \(y = f(n)\) 的定义域为某个整数集合，则称其为数论函数（或算术函数）。
- 常见示例：欧拉函数 \(\varphi(n)\)、约数个数函数 \(d(n)\)（也常记为 \(\tau(n)\)）、约数和函数 \(\sigma(n)\) 都是典型的数论函数，这类函数是研究数论问题的核心工具。
数论函数的核心特征是定义域为整数（通常是正整数集 \(\mathbb{N}^*\)），值域多为实数 / 整数，用来刻画正整数的算术性质。
- 与普通函数的区别：它不研究 “连续变量” 的变化，而是聚焦 “整数的数论特性”（比如约数、互质性、素因子分布等）。
| 函数符号 | 名称 | 定义 | 例子 | 核心性质 |
|---|---|---|---|---|
| φ(n) | 欧拉函数(Euler’s Totient Function) | 小于等于 n 且与 n 互质的正整数个数 | φ(6)=2（和 6 互质的数是 1、5）φ(7)=6（质数的欧拉函数值为 p−1） | 积性函数：若 gcd(a,b)=1，则 φ(ab)=φ(a)φ(b)对素数幂 pk：φ(pk)=pk−pk−1 |
| d(n)（或 τ(n)） | 约数个数函数(Divisor-counting Function) | n 的所有正约数的个数 | d(6)=4（约数：1,2,3,6）d(4)=3（约数：1,2,4） | 积性函数：若 n=p1k1p2k2…prkr，则 d(n)=(k1+1)(k2+1)…(kr+1)（指数 + 1 相乘） |
| σ(n) | 约数和函数(Divisor-sum Function) | n 的所有正约数的和 | σ(6)=1+2+3+6=12σ(4)=1+2+4=7 | 积性函数：若 n=p1k1p2k2…prkr，则 σ(n)=∏i=1r(1+pi+pi2+⋯+piki)（素因子等比数列和相乘） |
1. 前提：整数集合 D
设整数集合 D 满足乘法封闭性：若 \(m,n \in D\)，则它们的乘积 \(mn \in D\)。
2. 积性函数的定义
定义在集合 D 上的数论函数 \(f(n)\)，若满足：
对任意 \(m,n \in D\)，当 m 与 n互质（即 \(\gcd(m,n)=1\)，记作 \((m,n)=1\)）时，均有
\(f(mn) = f(m)f(n)\)
则称 \(f(n)\) 为积性函数。
3. 完全积性函数的定义
定义在集合 D 上的数论函数 \(f(n)\)，若满足：
对任意 \(m,n \in D\)（无论 \(m,n\) 是否互质），均有
\(f(mn) = f(m)f(n)\)
则称 \(f(n)\) 为完全积性函数。
| 类型 | 乘法性质的适用条件 | 例子 |
|---|---|---|
| 积性函数 | 仅对互质的 m,n 成立 | φ(n),d(n),σ(n) |
| 完全积性函数 | 对所有 m,n 都成立 | 恒等函数 f(n)=n、常数函数 f(n)=1 |
比如欧拉函数 \(\varphi(n)\) 是积性函数，但不是完全积性的：
- 互质时：\(\varphi(6)=\varphi(2\times3)=\varphi(2)\varphi(3)=1\times2=2\)，符合性质；
- 不互质时：\(\varphi(4)=2\)，但 \(\varphi(2)\times\varphi(2)=1\times1=1\neq2\)，不满足。
核心前提
设 \(f(n)\) 是不恒为 0 的数论函数，对任意正整数 n，其素因数分解为：
\(n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}\)
其中 \(p_1,p_2,\dots,p_k\) 是互不相同的素数，\(a_1,a_2,\dots,a_k\) 是正整数指数。
1. 积性函数的充要条件
\(f(n)\) 是积性函数的充要条件为：
- \(f(1) = 1\)（不恒为 0 的数论函数若为积性，在 1 处的取值必为 1）；
- 对任意正整数 n，\(f(n)\) 可分解为其素数幂处函数值的乘积：\(f(n) = f(p_1^{a_1}) \cdot f(p_2^{a_2}) \cdot \dots \cdot f(p_k^{a_k})\)
2. 完全积性函数的充要条件
\(f(n)\) 是完全积性函数的充要条件为：
- \(f(1) = 1\)；
- 对任意正整数 n，\(f(n)\) 可分解为其素数处函数值的指数次幂的乘积：\(f(n) = \left[f(p_1)\right]^{a_1} \cdot \left[f(p_2)\right]^{a_2} \cdot \dots \cdot \left[f(p_k)\right]^{a_k}\)
关键区别与例子验证
- 核心差异：积性函数仅对互质整数满足 \(f(mn)=f(m)f(n)\)，计算 \(f(n)\) 时需用到每个素数幂 \(p^a\) 对应的函数值\(f(p^a)\)；完全积性函数对所有整数都满足 \(f(mn)=f(m)f(n)\)，计算 \(f(n)\) 时仅需用到每个素数 p 对应的函数值\(f(p)\)，再取指数次幂即可。
- 讲义结论验证：\(\varphi(n),d(n),\sigma(n)\) 是积性函数，但不是完全积性函数
- 欧拉函数 \(\varphi(n)\)：\(\varphi(4)=2\)，但 \([\varphi(2)]^2=1^2=1\neq2\)，不满足完全积性条件；
- 约数个数函数 \(d(n)\)：\(d(4)=3\)，但 \([d(2)]^2=2^2=4\neq3\)，不满足；
- 约数和函数 \(\sigma(n)\)：\(\sigma(4)=7\)，但 \([\sigma(2)]^2=3^2=9\neq7\)，不满足。
题目： 已知正整数 m,n 满足 gcd(m,n)=2（即 m 和 n 的最大公约数为 2），求证：
φ(mn)=2φ(m)φ(n)
其中 φ(⋅) 为欧拉函数。
二、证明过程拆解（结合关键知识点）
步骤 1：利用条件分解 m,n
由 gcd(m,n)=2，可知：
- m,n 都含因子 2，且它们的公共因子只有 2；
- m,n 去掉因子 2 后，剩余的奇数部分互质。
因此可设：
m=2a⋅b,n=2⋅c
其中：
- a∈N∗（因 m 含因子 2，故 a≥1）；
- b,c 为奇数（不含因子 2），且 gcd(b,c)=1（否则 m,n 会有额外的公共奇因子，与 gcd(m,n)=2 矛盾）。
（注：此处 “不妨设 n=2⋅c” 是为了简化证明，因交换 m,n 位置后过程对称，不影响结果。）
步骤 2：计算 φ(mn)
先化简 mn：
mn=(2a⋅b)⋅(2⋅c)=2a+1⋅b⋅c
由于 2a+1、b、c 两两互质（b,c 为奇数且互质），根据欧拉函数的积性（若 x,y 互质，则 φ(xy)=φ(x)φ(y)）：
φ(mn)=φ(2a+1)⋅φ(b)⋅φ(c)
再用素数幂的欧拉函数公式（对素数 p，φ(pk)=pk−pk−1），对 p=2：
φ(2a+1)=2a+1−2a=2a
因此：
φ(mn)=2a⋅φ(b)⋅φ(c)
步骤 3：计算 φ(m)φ(n)
分别展开 m,n 的欧拉函数：
- m=2a⋅b，且 2a 与 b 互质，故：φ(m)=φ(2a)⋅φ(b)
- n=2⋅c，且 2 与 c 互质，故：φ(n)=φ(2)⋅φ(c)
因此乘积为：
φ(m)φ(n)=φ(2a)⋅φ(b)⋅φ(2)⋅φ(c)
再代入素数幂公式：
- φ(2a)=2a−2a−1=2a−1（a≥1）；
- φ(2)=1（因小于等于 2 且与 2 互质的数只有 1）。
因此：
φ(m)φ(n)=2a−1⋅φ(b)⋅1⋅φ(c)=2a−1⋅φ(b)⋅φ(c)
步骤 4：对比得证
由步骤 2 和步骤 3 的结果：
φ(mn)=2a⋅φ(b)φ(c)=2⋅(2a−1⋅φ(b)φ(c))=2φ(m)φ(n)
即证 φ(mn)=2φ(m)φ(n)。
三、关键知识点回顾
- 欧拉函数的积性：若 gcd(x,y)=1，则 φ(xy)=φ(x)φ(y)。
- 素数幂的欧拉函数：对素数 p，φ(pk)=pk−pk−1，特别地：
- p=2 时，φ(2k)=2k−1（k≥1）；
- 当 k=1 时，φ(p)=p−1（如 φ(2)=1，φ(3)=2）。
- 条件分解的合理性：gcd(m,n)=2 时，m,n 的公共因子仅为 2，因此奇部分互质，这是后续使用积性的基础。
四、例子验证（直观理解）
取 m=4（22），n=6（2×3），此时 gcd(4,6)=2：
- 计算 φ(4×6)=φ(24)=24×(1−21)×(1−31)=8；
- 计算 2φ(4)φ(6)=2×2×2=8；两者相等，验证结论成立。
狄利克雷卷积
两个数论函数 \(f(n)\) 和 \(g(n)\)，它们的狄利克雷卷积记作：
\(\boldsymbol{(f * g)(n)}\)
⚠️ 重点：这里的星号 \(\boldsymbol{*}\)不是普通乘法，是「狄利克雷卷积运算」的专属符号！
(f∗g)(n)=d∣n∑f(d)⋅g(dn)
拆开翻译每一部分：
- 固定一个正整数 n（比如我们取 \(n=6\)）；
- 找出 n 所有的正因数 d；
- 对每一个因数 d，算出两组值：\(f(d)\) 和 \(g\left(\dfrac{n}{d}\right)\)，再把它们相乘；
- 把所有乘积全部加起来，最后的总和，就是卷积在 n 处的结果。
：手把手算例题（看懂例子就彻底会了）
我们用最简单的函数来算，保证零难度：
设 \(f(n)=1,\ g(n)=1\)（两个都是常数函数，永远等于 1）
例 1：计算 \((f*g)(6)\)，也就是 n=6 时的卷积结果
- 找出 6 的所有因数：\(d=1,2,3,6\)
- 逐个套公式计算：
- \(d=1\)：\(f(1)\cdot g(\frac{6}{1}) = f(1)\cdot g(6) = 1\times1 = 1\)
- \(d=2\)：\(f(2)\cdot g(\frac{6}{2}) = f(2)\cdot g(3) = 1\times1 = 1\)
- \(d=3\)：\(f(3)\cdot g(\frac{6}{3}) = f(3)\cdot g(2) = 1\times1 = 1\)
- \(d=6\)：\(f(6)\cdot g(\frac{6}{6}) = f(6)\cdot g(1) = 1\times1 = 1\)
- 全部相加：\(1+1+1+1 = \boldsymbol{4}\)
所以：\(\boldsymbol{(f*g)(6) = 4}\)
例 2：算质数 n=5（因数更少，更简单）
5 的因数只有：\(d=1,5\)
- \(d=1\)：\(1 \times g(5) = 1\)
- \(d=5\)：\(1 \times g(1) = 1\)总和：\(1+1=\boldsymbol{2}\)
例 3：最小的正整数 n=1
1 的因数只有自己：\(d=1\)
结果：\(f(1)\cdot g(1) = 1\times1=\boldsymbol{1}\)
第四步：直观理解「配对关系」
观察上面的计算能发现一个规律：
对于 n 和它的因数 d，\(\dfrac{n}{d}\) 也一定是 n 的因数。
相当于把 n 的因数两两配对：\((d,\ \dfrac{n}{d})\)
比如 \(n=6\)：
\((1,6),\ (2,3)\)
卷积本质就是：每一对因数，分别代入两个函数相乘，最后全部求和。
第五步：简单性质（类比普通乘法，好记）
狄利克雷卷积的运算规则，和普通数字乘法非常像，不用证明，记住结论就行：
- 交换律：\(f*g = g*f\)交换两个函数的顺序，卷积结果不变（和 \(a\times b = b\times a\) 一样）。
- 结合律：\((f*g)*h = f*(g*h)\)多个函数连续卷积，先算哪两个都无所谓。
- 存在 “单位元”普通乘法里有个数 1：\(a\times1=a\)；狄利克雷卷积里也有一个单位函数 \(\varepsilon(n)\)：\(\varepsilon(n)= \begin{cases} 1 & n=1\\ 0 & n>1 \end{cases}\)任何函数和它卷积都等于自身：\(f * \varepsilon = f\)。
第六步：最重要的问题 —— 学它有啥用？
这是数论（尤其是莫比乌斯反演、积性函数）的核心工具，作用一句话：
把复杂的数论求和公式，简化成简单的 “函数卷积表达式”
举一个数论里最经典、最常用的结论：
我们知道一个定理：
对任意正整数 n，n 的所有因数的欧拉函数之和，恰好等于 n 本身
\(\sum_{d\mid n} \varphi(d) = n\)
如果用狄利克雷卷积来写，短短几个符号就搞定：
\(\boldsymbol{\varphi * 1 = id}\)
翻译：欧拉函数 \(\varphi\) 和常数函数 1 做狄利克雷卷积，结果就是恒等函数 \(id(n)=n\)。
再补充：大名鼎鼎的莫比乌斯反演，本质就是狄利克雷卷积的 “逆运算”。
很多数论难题、竞赛题、算法题（比如筛法），最后都会转化成狄利克雷卷积来求解。
Leave a Reply
You must be logged in to post a comment.