数论基础

求和符号的定义

为了简化形如 \(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\) 等。