数论三角和与高斯和
贡献者： 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$ 而非其他字母。
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。