0. 前置知识与基本定义
-
\([op]\)：值为 \(1\) 当且仅当方括号内条件为真。记为艾弗森括号
-
唯一分解定理：一个正整数 \(x\) 可以被唯一分解为 \(\prod\limits_{i=1}^m p_i^{c_i}\)，其中 \(\forall i\in[1,m],p_i\in \mathbb{P}\)。（关于\(\mathbb{P}\)，详见初等数学瞎扯Ⅰ：同余相关）。
1. 数论函数
1-1. 数论函数及其相关定义
-
数论函数：定义域为正整数的函数为数论函数，可以视作数列。
-
陪域：可能的取值范围。
-
加性函数：若对于任意 \(a,b\in \mathbb{N}_+\) 且 \(a\perp b\) 均有 \(f(ab)=f(a)+f(b)\)，则称 \(f\) 为 加性函数。
-
积性函数：若对于任意 \(a,b\in \mathbb{N}_+\) 且 \(a\perp b\) 均有 \(f(ab)=f(a)f(b)\)，则称 \(f\) 为 积性函数。
-
完全积性函数：若对于任意 \(a,b\in \mathbb{N}_+\) 均有 \(f(ab)=f(a)f(b)\)，则称 \(f\) 为 完全积性函数。完全积性函数一定是积性函数。
-
数论函数的加法：对于数论函数 \(f,g\)，若存在函数 \(h\) 满足 \(\forall x\in\mathbb{N}_+ , h(x)=f(x)+g(x)\)，则 \(h=f+g\)。
-
数论函数的数乘：对于数论函数 \(f\)，若存在函数 \(g\) 满足 \(\forall x\in\mathbb{N}_+ , g(x)=cf(x)\)，则 \(h=cf\)。
-
数论函数的点乘：对于数论函数 \(f,g\)，若存在函数 \(h\) 满足 \(\forall x\in\mathbb{N}_+ , h(x)=f(x)\cdot g(x)\)，则 \(h=f\cdot g\)。
1-2. 常见数论函数
1-2-1 单位函数
记作 \(\epsilon\)，其中 \(\epsilon(n)=[n=1]\)。
\(\epsilon\) 是完全积性函数，证明显然。
1-2-2 常数函数
记作 \(I\)，其中 \(I(n)=1\)，有时简写作 \(1\)。
\(I\) 是完全积性函数，证明显然。
1-2-2 恒定函数
记作 \(id_k\)，其中 \(id_k(n)=n^k\)。
\(id_k\) 是完全积性函数，证明显然。
特别的，当 \(k=1\) 时，我们省略 \(k\)，简记为 \(id\)。
1-2-3 本质不同质因子函数
记作 \(\omega(x)\)，即为对 \(x\) 做唯一分解后的 \(m\)。
特殊的，\(\omega\) 为加性函数，这也是介绍的唯一一个加性函数。
1-2-4 除数函数
记作 \(\sigma_k(x)\)，可表示为 \(\sum\limits_{d|n}d^k\)，对于 \(k=0\) 时原式表示约数个数，可以记作 \(d(x)\) 或 \(\tau(x)\)，简写规则与恒定函数相同，且 \(\sigma(x)\) 表示 \(x\) 的约数个数和。
除数函数是积性函数，证明如下。
除数函数有计算式如下
对于 \(k=0\)，其相当于对质数做乘法原理。
对于 \(k\neq 0\)，其相当于做完排列组合后相加，交换枚举顺序后等比数列求和即可得证。这里从略。
故其显然为积性函数。
1-2-5 欧拉函数
最神奇的函数。个人认为和莫比乌斯函数重要程度不相上下。
首先给出欧拉函数的定义，\(\varphi(x)\) 为在 \([1,x]\) 中与 \(x\) 互质的数的个数。
为了考察这个函数，我们先探寻其在质数次幂的性质。
性质 1
\(\varphi(p^k)=p^{k-1}(p-1),p\in\mathbb{P}\)。
对于 \([1,p^k]\) 次方中的数，其与 \(p^k\) 不互质当且仅当其是 \(p\) 的倍数。
故答案为 \(p^k-p^{k-1}=p^{k-1}(p-1)\)。
性质 2
标签：mathbb,函数,筛法,瞎扯,积性,数论,_+,forall,初等数学 From： https://www.cnblogs.com/-Complex-/p/17352649.html\(\varphi(x)\) 是积性函数