二次同余式

二次同余式是关于未知数的二次多项式的同余方程。即：
$ax^2+bx+c\equiv0\bmod\ m$ 是一个二次同余方程。
此外，称 $x^2\equiv a\bmod\ m$ 为最简二次同余式，或称最简二次同余方程。
一般的，通过配方，可以把一个一般的二次同余方程转化为一个最简二次同余式
接下来只需要讨论最简二次同余式。

二次剩余

前置概念、定理即证明：

有正整数 $n$，奇质数 $p$，且 $p\nmid n$，若存在一个正整数 $x$，使得 $x^2\equiv n\bmod\ p$，则称 $n$ 为 $p$ 的二次剩余。
勒让德符号 $\begin{pmatrix}\dfrac{n}{p}\end{pmatrix}$，若 $n$ 为 $p$ 的二次剩余，则该值为 $1$，若不是则该值为 $-1$，若 $p\mid n$，则该值为 $0$。

定理 $1$：

$$
\begin{pmatrix}\dfrac{n}{p}\end{pmatrix}\equiv n^{\frac{p-1}{2}}\bmod p
$$

证明：设 $g$ 为 $p$ 的原根，易证当 $k=1,2,\cdots p-1$ 时，$g^k$ 两两不同，所以存在唯一的 $k$，满足 $n=p^k$,有以下引理：存在一个 $x$，满足：
$$
x^2\equiv n\bmod\ p\Leftrightarrow 2|k
$$
现在证明上面的引理：
- 充分性：设 $g^l=x$，则 $g^{2l}\equiv n\bmod p$，那么有 $k\equiv 2l \bmod p-1$，而 $p-1$ 是偶数，所以 $k$ 是偶数。
- 必要性：令 $x=g^{\frac{k}{2}}$ 即可。
首先如果 $p|n$，则显然 $RHS=0$。

否则，我们先证明 $g^{\frac{p-1}{2}}\equiv -1$，我们有：
$$
\begin{aligned}
&g^{p-1}\equiv 1\bmod p\
&\Rightarrow g^{p-1}-1\equiv 0\bmod p\
&\Rightarrow (g^{\frac{p-1}{2}}-1)(g^{\frac{p-1}{2}}+1)\equiv 0 \bmod p
\end{aligned}
$$
而因为 $g^{\frac{p-1}{2}}\not\equiv 1\bmod p$，得证。

若 $n$ 为 $p$ 的二次剩余，则：

$$
\begin{aligned}
a^{\frac{p-1}{2}}&\equiv (g^k)^{\frac{p-1}{2}}\bmod p\
&\equiv (g^{p-1})^{\frac{k}{2}}\equiv 1\bmod p
\end{aligned}
$$

否则，我们有：

$$
\begin{aligned}
a^{\frac{p-1}{2}}&\equiv (g^k)^{\frac{p-1}{2}}\bmod p\
&\equiv (g^{\frac{p-1}{2}})^{k}\equiv (-1)^k\equiv -1\bmod p
\end{aligned}
$$
$\text{Q.E.D}$

同时，经过上面的推导，我们可以看出若方程最简二次同余式有解的充要条件是 $n^{\frac{p-1}{2}}\equiv 1(\bmod\ p)$，并且勒让德符号是完全积性的。

定理 $2$：

$[1,p-1]$ 中有 $\frac{p-1}{2}$ 个二次剩余。
证明：
设 $x,y\in [1,p-1],x\neq y,x^2\equiv y^2$，则 $(x-y)(x+y)\equiv 0$ 由于有 $0<|x-y|<p$，所以必定是 $x+y\equiv 0$，即 $x+y\equiv 0\Leftrightarrow x^2=y^2$ 这说明如果 $n$ 为 $p$ 的二次剩余，并且一个解是 $x$，则另一个解一定是 $p-x$。而 $x\not=y,x+y\not\equiv 0\Rightarrow x^2\not\equiv y^2$，所以一共只有 $\frac{p-1}{2}$ 个二次剩余。

求解最简二次同余式

算法：在 $[0,p-1]$ 中随机生成一个数 $a$，另 $w=a^2-n$，若 $\begin{pmatrix}\dfrac{w}{p}\end{pmatrix}=-1$ ，那么 $(a+\sqrt{w})^{\frac{p-1}{2}}$ 是 $x$ 的一个解。
证明：显然有 $[x\not=1\And x\not=p]\Rightarrow\tbinom{p}{x}\equiv 0 \bmod p$，因此，$(a+\sqrt{w})^p=\sum_{i=0}^p \tbinom{p}{i}a^i(\sqrt{w})^{p-i}\equiv a^p+(\sqrt{w})^p$（注明：以上是二项式定理），根据费马小定理，有 $a^{p-1}\equiv 1(\bmod p)$ 所以有 $a^p\equiv a (\bmod p)$ 根据定理 $1$，$(\sqrt{w})^p=\sqrt{w}\times w^{\frac{p-1}{2}}=-\sqrt{w}$ ，因此有 $(a+\sqrt{w})^{p-1}=(a+\sqrt{w})\times(a+\sqrt{w})^p\equiv (a+\sqrt{w})(a^p+(\sqrt{w})^p)$。而 $(a+\sqrt{w})(a^p+(\sqrt{w})^p)\equiv (a+\sqrt{w})(a-\sqrt{w})=a^2-w=n$。故有 $(a+\sqrt{w})^{p-1}\equiv n$，所以 $(a+\sqrt{w})^{\frac{p-1}{2}}$ 为原方程的一个解。可以证明答案不会出现 $\sqrt w$。
这里严谨的证明需要证明代数系统是一个环，留坑待填。

二次互反律

设 $p,q$ 是两个奇素数，我们有：

$$
\begin{pmatrix}\dfrac{q}{p}\end{pmatrix}\begin{pmatrix}\dfrac{p}{q}\end{pmatrix}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}
$$

证明：
这里引用 $\text{2019}$ 年的最新证明，被称作历代以来最短的证明。
这里引用 Jacobi 和，定义：
$$
S_n(t)=\sum\limits_{x_1+x_2+\cdots x_n=t}\begin{pmatrix}\dfrac{x_1x_2\cdots x_n}{p}\end{pmatrix}
$$
也就是把 $t$ 进行 $n$ 元拆分，注意这里认为 $x_1,x_2,\cdots x_n$ 互不相同。而且这 $n$ 项及其它们的加法都是 $\bmod p$ 意义下的。
接下来我们研究一下上面这个数的性质。对于 $a\not\equiv 0\bmod p$，我们有：
$$
\begin{aligned}
S_n(t)&=\sum\limits_{x_1+x_2+\cdots x_n=t}\begin{pmatrix}\dfrac{x_1x_2\cdots x_n}{p}\end{pmatrix}\
&=\sum\limits_{\frac{x_1}{a}+\frac{x_2}{a}+\cdots+\frac{x_n}{a}=\frac{t}{a}}\begin{pmatrix}\dfrac{\frac{x_1}{a}\frac{x_2}{a}\cdots \frac{x_n}{a}}{p}\end{pmatrix}\begin{pmatrix}\dfrac{a}{p}\end{pmatrix}^n\
&=\begin{pmatrix}\dfrac{a}{p}\end{pmatrix}^nS_n(\frac{t}{a})
\end{aligned}
$$
当 $n$ 是奇数的时候，我们代入 $t=0,t=a$ 可以得到：
$$
\begin{aligned}
S_n(0)&=0\
S_n(a)&=\begin{pmatrix}\dfrac{a}{p}\end{pmatrix}^nS_n(1)\
&=\begin{pmatrix}\dfrac{a}{p}\end{pmatrix}S_n(1)(a\not\equiv 0 \bmod p)
\end{aligned}
$$
注：这里第三行是因为 $n$ 是一个奇数。

当 $n=2$ 时，代入上边的式子可以得到 $S_2(a)=S_n(1)$，这是因为 $\begin{pmatrix}\frac{1}{p}\end{pmatrix}=1$ 恒成立，由于 $1^2\equiv 1\bmod p$。

接下来我们从定理出发得到：
$$
S_2(0)=\sum\limits_{i=1}^{p-1}\begin{pmatrix}\dfrac{i(-i)}{p}\end{pmatrix}=\sum\limits_{i=1}^{p-1}\begin{pmatrix}\dfrac{i^2}{p}\end{pmatrix}\begin{pmatrix}\dfrac{-1}{p}\end{pmatrix}
$$
注：$i=0$ 时的项为 $\begin{pmatrix}\frac{0*0}{p}\end{pmatrix}$ 恒为 $0$。

注意到 $i^2$ 一定是 $p$ 的二次剩余，所以我们有：$\begin{pmatrix}\frac{i^2}{p}\end{pmatrix}=1$，所以我们又可以得到：

$$
S_2(0)=(p-1)\begin{pmatrix}\dfrac{-1}{p}\end{pmatrix}
$$

又因为 $1,2,\cdots p-1$ 有一半是 $p$ 的二次剩余，所以有：

$$
\sum\limits_{i=1}^{p-1} \begin{pmatrix}\dfrac{i}{p}\end{pmatrix}=0
$$

于是：

$$
\begin{aligned}
S_2(1)&=\sum\limits_{i=1}^{p-1}\begin{pmatrix}\dfrac{i(1-i)}{p}\end{pmatrix}=\sum\limits_{i=1,j=i^{-1}}\begin{pmatrix}\dfrac{i^2j(1-i)}{p}\end{pmatrix}\
&=\sum\limits_{i=1,j=i^{-1}}^{p-1}\begin{pmatrix}\dfrac{i^2}{p}\end{pmatrix}\begin{pmatrix}\dfrac{j(1-i)}{p}\end{pmatrix}=\sum\limits_{j=1}^{p-1}\begin{pmatrix}\dfrac{j(1-i)}{p}\end{pmatrix}\
&=\sum\limits_{j=1}^{p-1}\begin{pmatrix}\dfrac{j-1}{p}\end{pmatrix}=\sum\limits_{j=0}^{p-2}\begin{pmatrix}\dfrac{j}{p}\end{pmatrix}=-\begin{pmatrix}\dfrac{-1}{p}\end{pmatrix}
\end{aligned}
$$

所以我们可以得到：

$$
S_n(a)=S_2(1)=-\begin{pmatrix}\dfrac{-1}{p}\end{pmatrix}(a\not\equiv 0\bmod p)
$$

整个证明的关键在于写出 $n$ 为奇数时的表达式，首先，对于 $n$ 为奇数，我们有以下恒等式：

$$
S_{n+2}(1)=\sum\limits_{i=0}^{p-1}S_n(i)S_2(1-i)
$$

证明这个式子只需要回归定义，对于所有的 $x_1,x_2,\cdots,x_{n+2}$，我们按照前 $n$ 项的和划分成若干集合，设前 $n$ 项和为 $t$ 的集合为 $S_t$，而 $S_n(t)S_2(1-t)$ 相当于是枚举了 $S_t$ 里面的每一个元素。

注：不要忘记勒让德符号具有完全积性。

所以我们有：

$$
\begin{aligned}
S_{n+2}(1)&=\sum\limits_{i=0}^{p-1}S_n(i)S_2(1-i)\
&=S_n(0)S_2(1)+S_n(1)S_2(0)+\sum\limits_{i=2}^{p-1}S_n(i)S_2(1-i)\
&=S_n(1)(p-1)\begin{pmatrix}\dfrac{-1}{p}\end{pmatrix}-\sum\limits_{i=2}^{p-1}\begin{pmatrix}\dfrac{i}{p}\end{pmatrix}S_n(1)\begin{pmatrix}\dfrac{-1}{p}\end{pmatrix}\
&=S_n(1)p\begin{pmatrix}\dfrac{-1}{p}\end{pmatrix}
\end{aligned}
$$

于是我们可以从 $n$ 递推 $\frac{n-1}{2}$，可以得到：

$$
S_n(1)=p^{\frac{n-1}{2}}\begin{pmatrix}\dfrac{-1}{p}\end{pmatrix}^{\frac{n-1}{2}}=p^{\frac{n-1}{2}}(-1)^{\frac{n-1}{2}\frac{p-1}{2}}
$$

令 $n$ 等于奇素数 $q$，运用欧拉准则我们又可以得到：

$$
S_q(1)\equiv \begin{pmatrix}\dfrac{p}{q}\end{pmatrix}(-1)^{\frac{q-1}{2}\frac{p-1}{2}} \bmod q
$$

接下来考虑 $1$ 的 $q$ 元拆分右循环 $1,2,\cdots q$ 位的结果，因为 $q$ 是一个质数，所以循环节要么是 $q$ 要么是 $1$。所以要么这些数都一样，要么这 $q$ 个右循环结果互不相同。

对于互不相同的情况，对 $S_q(1)$ 的贡献应该是 $q\begin{pmatrix}\frac{x_1x_2\cdots x_q}{p}\end{pmatrix}\equiv 0 \bmod q$，所以我们可以得到：

$$
S_q(1)\equiv \sum\limits_{qx=1}\begin{pmatrix}\dfrac{x^q}{p}\end{pmatrix}\equiv \begin{pmatrix}\dfrac{q^{-1}}{p}\end{pmatrix}^q\equiv \begin{pmatrix}\dfrac{q^{-1}}{p}\end{pmatrix}\equiv \begin{pmatrix}\dfrac{q}{p}\end{pmatrix}\bmod q
$$

注：满足 $qx=1$ 的 $x$ 在 $\bmod\ p$ 意义下只有一个。
最后一步的推导好像不是很显然，实际上若 $q^{-1}$ 是 $p$ 的二次剩余，设 $x^2\equiv q^{-1}\bmod p$，那么我们有 $x^{-2}\equiv q\bmod p$，而由于 $p$ 是素数，对于 $x\not\equiv 0$，$x^{-1}$ 一定存在。故两个勒让德符号是相等的。

于是我们整理一下可以得到：

$$
S_q(1)\equiv \begin{pmatrix}\dfrac{p}{q}\end{pmatrix}(-1)^{\frac{q-1}{2}\frac{p-1}{2}}\equiv \begin{pmatrix}\dfrac{q}{p}\end{pmatrix}
$$

而两边只有符号的区别，所以同余号就无关紧要了，我们就可以得到：

$$
\begin{pmatrix}\dfrac{p}{q}\end{pmatrix}\begin{pmatrix}\dfrac{q}{p}\end{pmatrix}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}
$$