数论三角和与高斯和
贡献者： int256
预备知识 1 同余与剩余类，指数函数（复数）
，数论求和记号
1. 数论三角和
由于 $e^{\pi \mathrm{i} } = -1$，利用 $e^{2\pi \mathrm{i} } = 1$ 可以构造出诸多三角和。在数论中我们记
\begin{equation}
e(t) := e^{2\pi \mathrm{i} t} ~,
\end{equation}
则对于 $t$ 的有理值，当 $x \equiv y \pmod m$ 时，将有
\begin{equation}
e\left(\frac{x}{m}\right) = e\left(\frac{y}{m}\right) ~.
\end{equation}
这是数论三角和的重要性质。
2. Gauss 和
定义 1 Gauss 数论三角和
定义 $S(m, n)$ 为高斯（数论三角）和，1
\begin{equation}
S(m, n) := \sum_{h = 0}^{n-1} e\left(\frac{h^2m}{n}\right) ~.
\end{equation}
Gauss 和在二次剩余中应用较多。
考虑对于任意 $r$，
\begin{equation}
e\left(\frac{(h + rn)^2m}{n}\right) = e\left(\frac{h^2m}{n}\right) ~,
\end{equation}
故我们可以不将 $h$ 限定在从 $0$ 到 $(n-1)$ 取遍，而只要 $h$ 取遍一个完全剩余系即可。此时用记号 $h(n)$ 表示取遍一个 $n$ 的完全剩余系。
推论 1
\begin{equation}
S(m, n) := \sum_{h(n)} e\left(\frac{h^2 m}{n}\right) ~.
\end{equation}
下面引出由线性同余中的定理 3 的一个推论。
推论 2
若 $(n, n') = 1$，则
\begin{equation}
S(m, nn') = S(mn', n) \times S(mn, n') ~.
\end{equation}
证明：考虑 $h$ 取遍 $n$ 的一个完全剩余系而 $h'$ 取遍 $n'$ 的一个完全剩余系，则由定理 3 将立刻得到 $h_0 = hn' +h'n$ 取遍 $nn'$ 的完全剩余系。而
\begin{equation}
mh_0^2 = m(h'n + hn')^2 \equiv mh^2n'^2 + mh'^2n^2 \pmod{nn'} ~,
\end{equation}
故
\begin{equation}
\begin{aligned}
S(mn', n) \times S(mn, n') &= \left[ \sum_{h(n)} e\left(\frac{h^2mb'}{n}\right) \right] \times \left[\sum_{h'(n')} e\left(\frac{h'^2mn}{n'}\right)\right] \\
&= \sum_{h(n), h'(n')} \left[ e\left(\frac{h^2 mn'}{n} + \frac{h'^2 mn}{n'}\right)\right] \\
&= \sum_{h(n), h'(n')} \left[ e\left( \frac{m(h^2 n'^2 + h'^2 n^2)}{nn'} \right)\right]\\
&= \sum_{h_0(nn')} e\left( \frac{m h_0^2}{nn'} \right) = S(m, nn')~.
\end{aligned}
\end{equation}
证毕！
定理 1 Gauss 和的等价定义
利用 Legendre 符号，对素数 $n$ 的 Gauss 和 $S(1, n)$ 给出了一个等价定义：
\begin{equation}
S(1, n) = \sum_{h=0}^{n-1} \left(\frac hp\right) e\left(\frac{h}{n}\right) ~.
\end{equation}
1. ^ 在数论中，求和取遍剩余系时，一般都用字母 $h$ 而非其他字母。