数论基础

TKXZ133's Blog / 2023-06-05 / 原文

求和

求和符号的定义

为了简化形如 \(a_1+a_2+...+a_n\) 这样求 \(n\) 个数的和的表述，引入求和符号 \(\sum\)，将上式重表述为 \(\sum\limits_{i=1}^na_i\)。

其中，\(i\) 被称为指标变量，取值为从 \(1\) 到 \(n\) 的整数，\(a_i\) 为关于 \(i\) 的函数。

求和符号的性质

定理1：

\(\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^ma_i+\sum\limits_{i=m+1}^na_i\)

其中 \(1\le m<n\)，此定理由加法的结合律易证。

定理2：

\(\sum\limits_{i=1}^n(a_i+b_i)=\sum\limits_{i=1}^na_i+\sum\limits_{i=1}^nb_i\)

由加法的结合律和交换律易证，此定理可以扩展到多项的情况。

定理3：

\(\sum\limits_{i=1}^nCa_i=C\sum\limits_{i=1}^na_i\)

其中 \(C\) 为任意常数，此定理由乘法对加法的分配律易证。

多重求和

设 \(f(i,j)\) 为一个关于 \(i,j\) 的二元函数，那么可以记 \(\sum\limits_{i=1}^n(\sum\limits_{j=1}^mf(i,j))=\sum\limits_{i=1}^n\sum\limits_{j=1}^mf(i,j)\)，其中 \(\sum\limits_{i=1}\sum\limits_{j=1}^m\) 是一个整体，称为双重求和符号。

类似的，可以定义多重求和符号。

在多重求和中，求和顺序可以任意改变，例 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^mf(i,j)=\sum\limits_{j=1}^m\sum\limits_{i=1}^nf(i,j)\)。

求和符号的其他简记

我们将 \(\sum\limits_{i=1}^{\infty}[P]a_i\) 简记为 \(\sum\limits_{P}a_i\)，其中，\(P\) 是一个关于 \(i\) 的命题，\(a_i\) 是关于 \(i\) 的函数，\([]\) 表示艾佛森括号，当其中的命题为真时其值为 \(1\)，否则为 \(0\)。此简记常用于集合表示，整除表示，范围表示，方程解的表示，双求和及多求和的表示，轮换求和和对称求和等。

例：\(\sum\limits_{i\in P}i\)，\(\sum\limits_{i|n}i\)，\(\sum\limits_{1\le i\le n}i\)，\(\sum\limits_{x+y=n}1\)，\(\sum\limits_{1\le i\le j\le n}\)，\(\sum\limits_{cyc}x^2y\) 等。

函数

常用数论函数的定义

数论函数指定义域为正整数的函数。

单位函数：

\(\varepsilon(n)\) 被称为单位函数，其定义为 \(\varepsilon(n)=[n=1]\)，即当 \(n\) 为 \(1\) 时其值为 \(1\)，否则为 \(0\)。

恒等函数：

\(\text{id}(n)\) 被称为恒等函数，其定义为 \(\text{id}(n)=n\)。

除数函数：

\(\sigma_k(n)\) 被称为除数函数，其定义为 \(\sigma_k(n)=\sum\limits_{d|n}d^k\)，当 \(k=0\) 时又记作 \(d(n)\)，表示 \(n\) 的约数个数；当 \(k=1\) 时又记作 \(\sigma(n)\)，表示 \(n\) 的约数之和。

欧拉函数：

\(\varphi(n)\) 被称为欧拉函数，其定义为 \(\sum\limits_{i=1}^n[\gcd(i,n)=1]\)，即在 \(1\) 到 \(n\) 中于 \(n\) 互质的数的个数。

莫比乌斯函数：

\(\mu(n)\) 被称为莫比乌斯函数，其定义为 \(\mu(n)=\begin{cases}1 &n=1\\0 &\exists d>1,d^2|n\\(-1)^{\omega(n)} &\text{otherwise}\end{cases}\)，其中 \(\omega(n)\) 表示 \(n\) 的本质不同质因子个数。