同余方程、二次剩余、二次互反律

1、同余方程

剩余类可以看做是一个新的数系，它对加减乘运算是封闭的，所以同余方程对多项式是有意义的。这里我们就来讨论下一元多项式方程（1）的解，当然它的解是一个剩余类集合，最多有 m 个解。
$f(x)=\sum_{k=0}^{n}{a_kx^k}=a^nx^n+\cdots+a_1x+a_0\equiv 0\pmod{m}\tag{1}$

在正式解一个同余方程前，可以先进行一些简单的变形，最简单的就是将系数取模。对于两个多项式 $f(x), g(x)$ ，如果它们的系数是模m同余的，则称 $f(x),g(x)$ 是模m同余的。记作 $f(x)$

image.png

。显然模同余的多项式的解也必然是相同的，一般将化简后多项式的最高次数称为方程的次数。同余方程中也不是完全不能用除法，当时，多项式乘上就可以变成首 1 多项式。

进一步，如果 $f(x)\equiv g(x)\pmod {m}$ 恒成立，则称 $f(x), g(x)$ 是模 m 等价的。比如根据费马小定理， $f(x)=x^p$ 和 $g(x)=x$ 就是等价的。显然同余的多项式必定是等价的，但等价的多项式却不一定是同余的。例如上面的例子 $f(x)=x^p$ 和 $g(x)=x$ 就是等价的，但很明显能看出来其对应的幂次数签的系数并不同余，故两个式子不同余。使用等价多项式可以对方程进行降次，比如模为p的多项式 f(x) 一定可以通过多项式除法 $f(x)=g(x)(x^p-x)+r(x)$ 降为次数小于p的多项式 r(x)。对于一般的合数 m，其实容易有 $a^m\equiv a^{m-\varphi(m)}\pmod{m}$ ，则有恒等式 $x^m-x^{m-\varphi(m)}\equiv 0\pmod{m}$ ，故任何多项式都等价于某个次数小于 m 的多项式。

在这里我们先从一般的类似（1）式的最复杂的情况的一般同余方程开始讨论，接下来自然是要对模数进行分解，记方程（1）的解的个数为 $T(m,f)$ ，且 $m=m_1m_2\cdots m_n$ 中 $m_k$ 两两互素。容易证明解方程（1）的问题可以等价为解方程组（2）的问题，且有 $T(m,f)=T(m_1,f)T(m_2,f)\cdots T(m_n,f)$ 。
$f(x)\equiv 0\pmod{m}\Leftrightarrow\begin{cases}\:f(x)\equiv 0\pmod{m_1}\\\:\cdots\:\cdots\\\:f(x)\equiv 0\pmod{m_n}\end{cases}\tag{2}$

将模数进行素数分解，则我们可以把问题集中在解方程 $f(x)\equiv 0\pmod{p^e}$ ，在这里我们可以看出我们的思路其实还是比较清晰的，针对任意的模数 m，我们有算术基本定理将其分解成各个素数之积，于是我们把问题归结到模数为 $p^e$ ,而我们想要得到的一个好的结果就是可以找到模数为 $p^e$ 与 $p$ 单个素数之间的关系，或者递推关系最好，因为单素数这种情况最为简单。于是我们先来考虑对模“降次”。首先显然该方程的解也必然是 $f(x)\equiv 0\pmod{p^{e-1}}$ 的解，设c为后者的解，则前者的解必定在 $c+p^{e-1}y,(0\leqslant y\leqslant p-1)$ 中。将其带入原方程，经过整理后有式子 $f(c) + p^{e-1}f'(c)y+A_2p^{2(e-1)}y^2 + ··· + A_np^{n(e-1)}y^n\equiv 0\pmod{p^e}$ ，其中 $f'(x)$ 即为 $f(x)$ 的导函数为 $f'(x)=na_nx^{n-1}+(n-1)a_{n-1}x^{n-2}+···+2a_2x+a_1$ 。注意去除含有 $(p^{e-1}y)^k,(k\geqslant 2)$ 的项（被 $p^e$ 整除），整理后得到 $f(c)+f'(c)p^{e-1}y\equiv 0\pmod{p^e}$ ，进而有式子（3）。于是我们来考察较为简单的一次同余方程式（3），易得当 $p\nmid f'(c)$ 时，y 有唯一解。否则当 $p\mid f'(c)$ ，同时 $p\mid f(c)p^{1-r}$ （等价 $f(c)\equiv 0\pmod{p^e}$ ）时恒成立,这时候（3）式子的解数为 p,即 $y\equiv 0,1,···,p-1 \pmod{p}$ ,这个时候再带入 $c+p^{e-1}y$ 即可得到 $f(x)\equiv 0\pmod{p^2}$ 的解，依次迭代上去即可得到模 $p^e$ 的解，否则当 $p\mid f'(c)$ ，同时 $p\nmid f(c)p^{1-r}$ (等价 $f(c)\not\equiv 0\pmod{p^e}$ ) 时无解。这样就有了如公式（4）的方程的解的网状关系图,分别对应了上面三种情况，特别地当 $f'(x)\equiv 0\pmod{p}$ 无解时，所有 $f(x)\equiv 0\pmod{p^e}$ 的解相同。
$f'(c)y\equiv -f(c)p^{1-e}\pmod{p}\tag{3}$
$f(c)\equiv 0\pmod{p}\begin{cases}\:p\nmid f'(c)\,\Rightarrow f(c)\equiv 0\pmod{p^e}\\\:p^2\mid f(c)\Rightarrow f(x)\equiv 0\pmod{p^2},x=c+py\Rightarrow\cdots\\\:p^2\nmid f(c)\Rightarrow f(c)\not\equiv 0\pmod{p^e}\end{cases}\tag{4}$

现在我们的问题被转化成了方程 $f(x)\equiv 0\pmod{p}$ ，研究的方向和一般多项式方程类似，是关于方程解的个数和多项式格式。先假设方程已经做了同余简化，但还未做等价简化，使用多项式除法和归纳法可以有以下拉格朗日定理：若方程有 m 个不同的解 $x_1,x_2,\cdots,x_m$ ，则必定有唯一表达式（5），其中g(x)的首项为 $a_nx^{n-m}$ ， $r(x)$ 的次数低于 m。该定理说明了 n 次同余方程的解的个数不可能大于 n，反之若大于 n，则必恒为 0。
$f(x)=g(x)(x-x_1)(x-x_2)\cdots(x-x_m)+pr(x)\equiv g(x)(x-x_1)(x-x_2)\cdots(x-x_m)\pmod{p}\tag{5}$

拉格朗日定理给出了多项式同余方程与根有关的格式，值得注意的是，该格式与原多项式是同余，也就是它的本来面貌，这点很重要。该定理还有其它有趣的应用，比如由欧拉定理知 $x^{p-1}-1\equiv 0\pmod{p}$ 有 p−1 个非零解，则有公式（6），令 $x=0$ 即可得到威尔逊定理！如果再比较 $x$ 和 $xp−2$ 项的系数，就会有公式（7）（8）。这里需要注意的是（7）中的 $i$ 与 $j$ 是关于[p-1/2]对称的，分别对应 $x$ 和 $xp−2$ 前面的系数。还有值得一提的是，同余方程同可以有“重根”的概念，有兴趣朋友可以自己研究一下。
$x^{p-1}-1\equiv (x-1)(x-2)\cdots (x-p+1)\pmod{p}\tag{6}$
$\sum_{1\leqslant i\leqslant j\leqslant p-1}ij\equiv 0\pmod{p}\tag{7}$
$\quad (p-1)!\sum_{k=1}^{p-1}{\dfrac{1}{k}}\equiv 0\pmod{p}\tag{8}$

这里给出一个（8）式的简单的示意证明，首先因为 p 为素数，我们以 5 来作为示意展示，证明任意素数 p 时，只需将如下证明思路的模式从 5 推广到任意 p 即可。观察（8）并将 $(p-1)!$ 乘到和式里面，上式左边便变为了 $\sum M_k, 1 \leq k \leq p-1$ 其中 $M_i$ 的定义同以前文章中的定义及 $p-1$ 的阶乘除以 $i$ , 于是问题就归结到了证明如下式子：
$\sum_{k=1}^{p-1}{M_k}\equiv 0\pmod{p}$ 当 p = 5时，易知 $4\times3\times2=(5-1)(5-2)(5-3) \equiv -1\times2\times3 \pmod{p}$ ，同理其他式子也是一样，于是我们可观察得到，当 p = 5 时
$\sum M_k = 4\times3\times2 + 4\times3\times1 + 4\times2\times1 + 3\times2\times1 \\ \equiv -3\times2\times1 + -4\times2\times1 + 4\times2\times1 + 3\times2\times1 \equiv 0\pmod{p}$
并且此方法可以推广到任意的素数 p，于是（8）式得证。

接下来我们假定方程做了等价简化，即 $f(x)$ 的次数小于p且首项系数为 1，看看会有什么性质。首先若有 $f(x)\equiv g(x)\pmod{p}$ ，则 $f(x)-g(x)$ 有p个根，从而 $f(x)=g(x)$ ，换句话说，次数小于p的首1多项式如果等价则必唯一，即等价和同余是一致的。还有一个问题就是方程的根的个数问题了，当 $f(x)$ 恰有n个根时，有 $f(x)\equiv (x-x_1)\cdots(x-x_n)\pmod{p}$ ，而 $x^p-x=x(x-1)\cdots(x-p+1)\pmod{p}$ ，这就有 $x^p-x\equiv f(x)g(x)\pmod{p}$ 。反之也可以推得 $f(x),g(x)$ 分别有 $n, p−n$ 个根。这就是说 $f(x)$ 有n个解的充要条件是存在唯一表达式（9）。
$x^p-x=f(x)g(x)+pr(x)\tag{9}$

关于高次方程更进一步的结论比较少，这里也不作深究，而二项同余方程 $x^n\equiv a\pmod{p}$ 放到后面的不定方程讨论会更简单，所以这里也不讨论了。对一些低次方程，可以直接对其研究，我们先从最简单的一次剩余方程 $ax\equiv b\pmod{m}$ 看起，显然它是否有解与不定方程 $ax+my=b$ 是否有解是等价的，故有解的充要条件是 $(a,m)\mid b$ 。由同余的性质，原方程等价于方程（10）。故原方程共有 $(a,m)$ 个解，分别为 $x_0+\dfrac{m}{(a,m)}k,(k=0,\cdots,(a,m)-1)$ ，其中 $x_0$ 为任一解，也称为特解。如果将（10）简记为 $a_0x\equiv b_0\pmod{m_0}$ ，则 $a_0^{-1}b_0$ 即为原方程的一个特解。
$\dfrac{a}{(a,m)}x\equiv \dfrac{b}{(a,m)}\pmod{\dfrac{m}{(a,m)}}\tag{10}$

直接求逆是复杂的，一次方程一般用辗转相除法，对于一些特殊格式，还可以动用一切同余的性质简化算法。你可以试解决下面这几个问题：
　 • 证明 $2^ex\equiv b\pmod{m}$ 的解为 $(\dfrac{m+1}{2})^eb$ ，其中 $(2,m)=1$ 。并由此给出系数为 $2^i3^j$ 的方程的解法；
　　• $(a,m)=1$ ，若 $ax\equiv 1\pmod{m}$ 解为 $x_0$ ，则 $\dfrac{1-(1-ax_0)^e}{a}$ 是 $ax\equiv 1\pmod{m^e}$ 的解。

2、二次剩余

现在来研究模为素数的二次同余方程 $ax^2+bx+c\equiv\pmod{p}$ ，通过配方可以有 $(2ax+b)^2\equiv b^2-4ac\pmod{p}$ ，从而方程其实等价于二次二项方程 $x^2\equiv d\pmod{p}$ ，当然这里不去考虑 $p=2$ 和 $p|d$ 这样的平凡场景。如果方程有解， $d$ 称为 $p$ 的二次剩余，否则叫二次非剩余。为方便描述，这里先引进勒让德（Legendre）符号 $\left(\dfrac{d}{p}\right)$ ，并且勒让德符号或函数有三个取值，当 $d$ 为 $p$ 的二次剩余时其值为1，否则为 −1，当 $p|d$ 时值为 0。

考虑将 $p$ 的既约剩余系分为对称的两部分 $-\dfrac{p-1}{2},\cdots,-2,-1$ 和 $1,2,\cdots,\dfrac{p-1}{2}$ ，显然 $(-x)^2=x^2$ ，而当 $1\leqslant i<j\leqslant\dfrac{p-1}{2}$ 时， $i^2-j^2=(i+j)(i-j)\not\equiv 0\pmod{p}$ ，所以 $i^2\not\equiv j^2\pmod{p}$ 。从而上面的式子给出了模 p 的全部二次剩余，故 $p$ 共有 $\dfrac{p-1}{2}$ 个二次剩余，又因为模 p 的既约剩余系共有 p-1 个数，所以另外的（p-1）/2 个都是模p的二次非剩余，共有 $\dfrac{p-1}{2}$ 个二次非剩余，每个二次剩余有两个互为相反数的根。

我们自然要问：哪些数是二次剩余？如何判断它是二次剩余？根据欧拉定理有 $d^{p-1}\equiv 1\pmod{p}$ ，通过移项平方差构造容易证明 $d^{\frac{p-1}{2}}\equiv\pm 1\pmod{p}$ 。若 $d$ 为二次剩余，则有 $d^{\frac{p-1}{2}}\equiv(x)^{p-1}\equiv 1\pmod{p}$ 。若不为二次剩余，我们可以将 $1,2,\cdots,p-1$ 按照乘积为 $d$ 配成 $\dfrac{p-1}{2}$ 对，根据威尔逊定理有 $d^{\frac{p-1}{2}}\equiv -1\pmod{p}$ 。综合这两个结论就是二次剩余的欧拉判别法（公式（11）），当然对于大模数这个方法的计算量还是太大，它仅有理论价值。
$\left(\dfrac{d}{p}\right)=\pm 1\equiv d^{\frac{p-1}{2}}\pmod{p}\tag{11}$

对于一些特殊值，可以单独讨论，得出的结论也是可以直接使用的。首先容易证明 $−1$ 只有在 $p=4k+1$ 时才是二次剩余，并且由威尔逊定理知 $(\dfrac{p-1}{2})!$ 是它的解。而且当 $p=4k+1$ 时，显然 $x,−x$ 同时是或不是二次剩余，呈对称分布。当 $p=4k+3$ 时，显然x,−x有且仅有一个二次剩余，从上面的欧拉判别式即可得到此结论。这些结构都是很有用的。接下来我们可以来看看如下几个小练习：

• 讨论 $x^2+ay^2\equiv 0\pmod{p},(x,y)=1$ 有解的充要条件，并给出求解的方法；
　　• 求模 $p$ 下所有二次剩余的积与和，再求模 p 下所有二次非剩余的积与和。

使用勒让德符号能更清晰地表述二次剩余的性质，如下列的这些性质（可自行验证）：
　　（1） $\left(\dfrac{d+kp}{p}\right)=\left(\dfrac{d}{p}\right)$
　　
　　（2） $\left(\dfrac{d_1d_2}{p}\right)=\left(\dfrac{d_1}{p}\right)\left(\dfrac{d_1}{p}\right)$ ；
　　
　　（3） $\left(\dfrac{d^2}{p}\right)=1$ ； $\left(\dfrac{1}{p}\right)=1$ ； $\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$

使用素数分解并结合以上性质，可将求一般 $\left(\dfrac{d}{p}\right)$ 的问题转化为求解 $\left(\dfrac{2}{p}\right)$ 和 $\left(\dfrac{q}{p}\right)$ 上。现在从另一方面讨论 $d^{\frac{p-1}{2}}$ ，在剩余系 $1,2,\cdots,p-1$ 中考察 $\dfrac{p-1}{2}$ 个数 $d,2d,\cdots,\dfrac{p-1}{2}d$ 的分布，即在既约剩余系中的前 (p-1)/2 个数乘以二次剩余 d，然后观察那些落在了 0到 p/2 内，那些落在了 p/2 到 p 内。容易证明它们互不相同且互不相反，所以它们是以 $\dfrac{p}{2}$ 为对称轴的两个数之一，右半边的数（设个数为n）需要取相反数才能回到左边。考虑它们的积则容易有 $d^{\frac{p-1}{2}}\equiv (-1)^n\pmod{p}$ ，这样就有了二次剩余新的判定方法（公式（12）左），特别地时可以推得 $d=2$ 是二次剩余的条件是 $p=8k±1$ （可写成公式（12）右）。
$\left(\dfrac{d}{p}\right)=(-1)^n,\quad \left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}\tag{12}$

对一般的 $d$ 继续上面的结论，注意到 $dk=p[\dfrac{dk}{p}]+r_k$ （[x]是取整操作），对它们求和并在模2 下讨论，可以得到式子（13）。而后者有显著的几何意义，它是一个直角三角形区域内的整点个数。考虑 $\left(\dfrac{q}{p}\right)$ 对应的 $\triangle{OAB}$ 和 $\left(\dfrac{p}{q}\right)$ 对应的 $\triangle{OAC}$ ，它们正好组成了一个长方形区域，这样就得到了著名的高斯二次互反律（公式（14））。
$n\equiv\sum_{k=1}^{\frac{p-1}{2}}{\left[\dfrac{dk}{p}\right]}\pmod{2}\tag{13}$
$\left(\dfrac{q}{p}\right)\left(\dfrac{p}{q}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\tag{14}$

二次互反率示意图

有了这个公式，就可以将不断转化为更小模数的判定式，从而最终解决了任意的求解。如果上述证明过程，你感觉还有些不太清楚的话，你还可以参考这里：如何简洁地证明二次互反律？

在经过上述的论述之后，你还可以尝试思考下下面这几个问题：
• 求以3为二次剩余的充要条件，并由此对 $100^2-3$ 进行因式分解；
　　• 求证 $x^4+1$ 的奇素因子都有格式 $8k+1$ ；并由此证明格式为 $8k+1$ 的素数有无穷多个；
　　• $p=4k+3$ ，求证 $2p+1$ 为素数的充要条件是 $2^p\equiv 1\pmod{2p+1}$ ；
　　• $p\nmid a$ ，求 $\sum\limits_{x=1}^{p}{\left(\dfrac{x^2+ax}{p}\right)}$ （提示：剩余系的遍历）。
　　在使用勒让德符号时要保证模数是素数，这一点很不方便，我们希望这种记法能更通用一点。扩展后的符号称为雅克比（Jacobi）符号： $\left(\dfrac{d}{P}\right)=\prod\limits_{k=1}^n{\left(\dfrac{d}{p_k}\right)}$ ，其中 $P=p_1p_2\cdots p_n$ 。雅克比符号虽然只是一个记法，但形式上却同样有着漂亮的性质，首先有下面几个简单的性质：
　　
（1） $\left(\dfrac{d+kP}{P}\right)=\left(\dfrac{d}{P}\right)$ ；

（2） $\left(\dfrac{d_1d_2}{P}\right)=\left(\dfrac{d_1}{P}\right)\left(\dfrac{d_1}{P}\right)$ ； $\left(\dfrac{d}{P_1P_2}\right)=\left(\dfrac{d}{P_1}\right)\left(\dfrac{d}{P_2}\right)$ ；

（3） $\left(\dfrac{d^2}{P}\right)=\left(\dfrac{d}{P^2}\right)=1$ 。

在得到更多结论之前，需要一个引理：如果 $a=\prod a_k,a_k\equiv 1\pmod{m},(k=1,2,\cdots,n)$ ，则用归纳法可以有公式（15）。
$\dfrac{a-1}{m}\equiv\sum_{k=1}^n{\dfrac{a_k-1}{m}}\pmod{m}\tag{15}$

利用这个结论就很容易得到雅克比符号的以下性质，这些性质可以使得雅克比公式的使用更加自由，中间无需关心操作数是否为素数，比如 $\left(\dfrac{105}{317}\right)=\left(\dfrac{2}{105}\right)=1$ 。
（4） $\left(\dfrac{-1}{P}\right)=(-1)^{\frac{P-1}{2}}$ ; $\left(\dfrac{2}{P}\right)=(-1)^{\frac{P^2-1}{8}}$
（5） $\left(\dfrac{Q}{P}\right)\left(\dfrac{P}{Q}\right)=(-1)^{\frac{(P-1)(Q-1)}{4}}$

3、特殊二次方程的快速解法

上面我们探讨一般性的同余方程，然后又探讨了较为简洁的二次同余方程的一般形式，在这里我们继续介绍一些特殊的二次同余方程的快速解法。这在利用计算机进行运算时时常会被用到。众所周知，一个素数 $mod \ 8$ 只可能是 $1,3,5,7$ 。在这之中，对于 $mod \ 8$ 为 $3, 5, 7$ 的素数 ，我们都能够快速地解出二次方程 $x^2 \equiv n \pmod{p}$ 。

快速解法的要义实质上就是凑！但是如何优雅地凑、在凑的过程中碰到困难如何处理等等还是很有意思的。

首先，我们拿到一个二次方程后自然地会用Legendre符号 $\left(\dfrac{n}{p}\right)$ 判断其是否有解。在这里我们自然要讨论 $\left(\dfrac{d}{p}\right) = 1$ 的二次方程。那么利用 Euler 判别法， $n^{\frac{p-1}{2}}\equiv 1\pmod{p}$ 。这就是我们凑方程解的起点所在。

自然地，我们有 $n^{\frac{p+1}{2}}\equiv n\pmod{p}$ ，下面把左侧凑成平方形式： $(n^{\frac{p+1}{4}})^2 \equiv n\pmod{p}$ ，从而得到方程的解为： $x \equiv \pm n^{\frac{p+1}{4}}\pmod{p}$ 。但是我们得确保 $\frac{p+1}{4} \in Z$ ，故这个方法仅仅对于 $mod \ 8$ 为 $3, 7$ 的素数有效！

对于剩余类型的素数，我们可以换一个思路：先对于 $n^{\frac{p+1}{2}}\equiv 1\pmod{p}$ 做因式分解（这是个常用的思路），得到 $p | \ (n^{\frac{p-1}{4}} +1)(n^{\frac{p-1}{4}} -1)$ 。故 $n^{\frac{p-1}{4}} \equiv 1\pmod{p}$ 或 $n^{\frac{p-1}{4}} \equiv -1\pmod{p}$ 成立。（注意到这里 $mod \ 8$ 为 $\ 1, 5$ 的素数都能保证 $\frac{p-1}{4} \in Z$ ）

若 $n^{\frac{p-1}{4}} \equiv 1\pmod{p}$ 成立，则开始凑： $n^{\frac{p+3}{4}} \equiv n \pmod{p}$ ，故 $(n^{\frac{p+3}{8}})^2 \equiv n\pmod{p}$ ，解为 $x \equiv \pm n^{\frac{p+3}{8}}$ 。这个做法要求 $\frac{p+3}{8} \in Z$ ，故仅对于 $p \equiv 5 \pmod{8}$ 有效。

反之，若 $n^{\frac{p-1}{4}} \equiv -1\pmod{p}$ 成立， $(n^{\frac{p+3}{8}})^2 \equiv -n \pmod{p}$ 。但是我们遇到了问题：我们该如何凑出一个数，使得其平方在 $mod p$ 意义下为 -1 呢？Wilson 定理给了我们答案！对于素数 p， $(p-1)! \equiv 1\times2···\times(p-1) \equiv 1\times2\times ···\times\frac{p-1}{2}\times(p-\frac{p+1}{2})\times···\times[p-(p-1)] \equiv -1 \pmod{p}$

即 $[(\frac{p-1}{2})!]^2 \equiv -1 \pmod{p}$ 。这样一来立马得到解为： $x \equiv \pm(\frac{p-1}{2})!n^{\frac{p+3}{8}} \pmod{p}$ ，这个做法同样仅对于 $p \equiv 5 \pmod{8}$ 有效。这里的Wilson定理使用得太为精妙了，这告诉我们Wilson定理不仅仅为我们提供了一个数为素数的充要条件，其也帮助我们计算出了域 $Z_p$ 上的 $\sqrt{-1}$ ！

由于上述讨论中我们一直假定p 为奇素数，故我们一直没讨论模为 $2^a$ 时的方程解法。下面我们讨论方程 $x^2 \equiv n \pmod{2^a}$ ，其中假定 n 为奇数。

当模为 2 或 4 时我们分类讨论容易得到结论。模为2 时的解存在唯一，而模为4 时要么无解要么有唯一解，解存在的充要条件为 $n \equiv 1\pmod{4}$ 。（这很自然，因为所有奇数的平方都是模 4 余 1 的）

在模为 $2^a \ (a\geq 3)$ 时，我们先讨论其解的存在性与解的结构。

方程的解存在当且仅当 $n \equiv 1 \pmod{8}$ （这很好理解，因为所有奇数的平方都是模8 余 1 的），且给定方程特解 $x_0$ 后，可以确定其所有四个解 $\pm x_0,\pm x_0+2^{a-1}$ 。你可以自己验证下。

具体求解的情形中我们效仿高次同余方程的做法，利用 $x^2 \equiv n\pmod{2^{a-1}}$ 的解构造 $x^2 \equiv n \pmod{2^a}$ 的解。若前一个方程有解 $x \equiv x_0\pmod{2^{a-1}}$ ，则 $x \equiv x_0 + \frac{n-x_0^2}{2} \pmod{2^a}$ 必定为后一个方程的解，这是极其容易验证的。

故对于形如 $x^2 \equiv n \pmod{2^a}$ 的方程，我们只需要先考虑 $x^2 \equiv n \pmod{2^3}$ ，求出其解后即可写出 $x^2 \equiv n \pmod{2^4}$ 的解，以此类推，最终写出一个 $x^2 \equiv n \pmod{2^a}$ 的解 $x_1$ 。那么由这类方程解的结构，其全部四个解 $\pm x_0,\pm x_0+2^{a-1}$ 我们就都知道了！

【初等数论】同余方程、与二次剩余互反律

【初等数论】同余方程、与二次剩余互反律

同余方程、二次剩余、二次互反律

1、同余方程

2、二次剩余

3、特殊二次方程的快速解法