二次同余式
二次同余式是关于未知数的二次多项式的同余方程。即:
\(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\) 意义下的。
\[ \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} \]
接下来我们研究一下上面这个数的性质。对于 \(a\not\equiv 0\bmod p\),我们有:当 \(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}} \]