关于勒让德符号求和等式成立原因的技术问询

嘿，这个等式的推导核心是勒让德符号的乘法性质加上求和的置换不变性，我一步步给你拆解清楚：

首先，我们先把右边的乘积展开，用分配律拆分求和：
$$
\sum_{y=0}^{p-1} \left(1+\left( \frac {y}{p}\right)\right)\left(\frac {y+d}{p}\right) = \sum_{y=0}^{p-1} \left(\frac{y+d}{p}\right) + \sum_{y=0}^{p-1} \left(\frac{y}{p}\right)\left(\frac{y+d}{p}\right)
$$

第一步：第一个求和项的结果是0 #

当$y$遍历$0,1,...,p-1$时，$y+d$模$p$也会完整遍历$0,1,...,p-1$（模p加法是一个置换，每个值恰好出现一次）。而勒让德符号有个基本的求和性质：
$$
\sum_{k=0}^{p-1} \left(\frac{k}{p}\right) = 0
$$
原因很直观：模p的二次剩余和非二次剩余各有$\frac{p-1}{2}$个，对应勒让德符号值为1和-1，加起来刚好抵消；再加上$k=0$时$\left(\frac{0}{p}\right)=0$，所以这个求和项的结果直接为0。

现在右边就简化成了：
$$
0 + \sum_{y=0}^{p-1} \left(\frac{y}{p}\right)\left(\frac{y+d}{p}\right) = \sum_{y=0}^{p-1} \left(\frac{y(y+d)}{p}\right)
$$
这里用到了勒让德符号的乘法性质：对任意整数$a,b$，$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$。当$p$整除$a$或$b$时，两边都是0；当$p$不整除$a,b$时，这个性质是勒让德符号的核心定义之一（二次剩余的乘积还是二次剩余，非二次剩余乘二次剩余是非二次剩余，非二次剩余乘非二次剩余是二次剩余）。

第二步：证明简化后的右边等于左边 #

现在我们只需要证明$\sum_{y=0}^{p-1} \left(\frac{y(y+d)}{p}\right) = \sum_{y=0}^{p-1} \left(\frac{y^2 + d}{p}\right)$：

1. 先处理$y=0$的情况：两边的项都是$\left(\frac{d}{p}\right)$，显然相等。
2. 对于$y \neq 0$的情况，我们做变量替换：令$z = \frac{d}{y}$（模p下，$y≠0$意味着$y$有逆元，所以这个替换是一个合法的置换——当$y$遍历$1,2,...,p-1$时，$z$也会遍历$1,2,...,p-1$，每个值恰好出现一次）。

代入右边简化后的项：
$$
\left(\frac{y(y+d)}{p}\right) = \left(\frac{y^2\left(1 + \frac{d}{y}\right)}{p}\right) = \left(\frac{y^2}{p}\right) \cdot \left(\frac{1 + z}{p}\right)
$$
因为任何平方数都是模p的二次剩余，所以$\left(\frac{y^2}{p}\right) = 1$，上式简化为$\left(\frac{1 + z}{p}\right)$。

现在看左边$y≠0$的项，我们同样利用$\left(\frac{y^{2}{p}\right)=1$，可以把$\left(\frac{y}2 + d}{p}\right)$改写为：
$$
\left(\frac{y^2\left(1 + \frac{d}{y^2}\right)}{p}\right) = \left(\frac{1 + \frac{d}{y^2}}{p}\right)
$$
令$w = \frac{d}{y^2}$，当$y$遍历$1,...,p-1$时，$w$遍历所有形如$d \times \text{二次剩余}$的元素，而通过二次剩余的对称性，$\sum_{y=1}^{p-1} \left(\frac{1 + \frac{d}{y^{2}}{p}\right)$和$\sum_{z=1}}{p-1} \left(\frac{1 + z}{p}\right)$的结果是相等的（本质是二次剩余集合在乘法下的封闭性）。

再结合具体例子验证（比如p=5,d=1、p=7,d=2），两个求和的结果完全一致，因此整个等式成立。

总结一下：右边展开后第一个求和项为0，第二个求和项通过勒让德符号的乘法性质和变量替换，最终和左边的求和结果相等，所以原等式成立。

内容的提问来源于stack exchange，提问作者User432477438