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

1渊迁、同余方程

剩余類可以看做是一個新的數(shù)系慰照，它對加減乘運(yùn)算是封閉的，所以同余方程對多項式是有意義的琉朽。這里我們就來討論下一元多項式方程（1）的解毒租，當(dāng)然它的解是一個剩余類集合，最多有 m 個解箱叁。
$f(x)=\sum_{k=0}^{n}{a_kx^k}=a^nx^n+\cdots+a_1x+a_0\equiv 0\pmod{m}\tag{1}$

在正式解一個同余方程前墅垮，可以先進(jìn)行一些簡單的變形，最簡單的就是將系數(shù)取模耕漱。對于兩個多項式 $f(x), g(x)$ 算色，如果它們的系數(shù)是模m同余的，則稱 $f(x),g(x)$ 是模m同余的孤个。記作 $f(x)$

image.png

。顯然模同余的多項式的解也必然是相同的沛简，一般將化簡后多項式的最高次數(shù)稱為方程的次數(shù)齐鲤。同余方程中也不是完全不能用除法，當(dāng)時椒楣，多項式乘上就可以變成首 1 多項式给郊。

進(jìn)一步，如果 $f(x)\equiv g(x)\pmod {m}$ 恒成立捧灰，則稱 $f(x), g(x)$ 是模 m 等價的淆九。比如根據(jù)費(fèi)馬小定理， $f(x)=x^p$ 和 $g(x)=x$ 就是等價的毛俏。顯然同余的多項式必定是等價的炭庙，但等價的多項式卻不一定是同余的。例如上面的例子 $f(x)=x^p$ 和 $g(x)=x$ 就是等價的煌寇，但很明顯能看出來其對應(yīng)的冪次數(shù)簽的系數(shù)并不同余焕蹄，故兩個式子不同余。使用等價多項式可以對方程進(jìn)行降次阀溶，比如模為p的多項式 f(x) 一定可以通過多項式除法 $f(x)=g(x)(x^p-x)+r(x)$ 降為次數(shù)小于p的多項式 r(x)腻脏。對于一般的合數(shù) m鸦泳，其實容易有 $a^m\equiv a^{m-\varphi(m)}\pmod{m}$ ，則有恒等式 $x^m-x^{m-\varphi(m)}\equiv 0\pmod{m}$ 永品，故任何多項式都等價于某個次數(shù)小于 m 的多項式做鹰。

在這里我們先從一般的類似（1）式的最復(fù)雜的情況的一般同余方程開始討論，接下來自然是要對模數(shù)進(jìn)行分解鼎姐，記方程（1）的解的個數(shù)為 $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}$

將模數(shù)進(jìn)行素數(shù)分解，則我們可以把問題集中在解方程 $f(x)\equiv 0\pmod{p^e}$ 谋作，在這里我們可以看出我們的思路其實還是比較清晰的芋肠，針對任意的模數(shù) m，我們有算術(shù)基本定理將其分解成各個素數(shù)之積遵蚜，于是我們把問題歸結(jié)到模數(shù)為 $p^e$ ,而我們想要得到的一個好的結(jié)果就是可以找到模數(shù)為 $p^e$ 與 $p$ 單個素數(shù)之間的關(guān)系帖池，或者遞推關(guān)系最好，因為單素數(shù)這種情況最為簡單吭净。于是我們先來考慮對乃冢“降次”拨脉。首先顯然該方程的解也必然是 $f(x)\equiv 0\pmod{p^{e-1}}$ 的解矾睦，設(shè)c為后者的解缤灵，則前者的解必定在 $c+p^{e-1}y,(0\leqslant y\leqslant p-1)$ 中牲芋。將其帶入原方程落竹，經(jīng)過整理后有式子 $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)$ 的導(dǎo)函數(shù)為 $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}$ 村怪，進(jìn)而有式子（3）秽浇。于是我們來考察較為簡單的一次同余方程式（3），易得當(dāng) $p\nmid f'(c)$ 時甚负，y 有唯一解柬焕。否則當(dāng) $p\mid f'(c)$ ，同時 $p\mid f(c)p^{1-r}$ （等價 $f(c)\equiv 0\pmod{p^e}$ ）時恒成立,這時候（3）式子的解數(shù)為 p,即 $y\equiv 0,1,···,p-1 \pmod{p}$ ,這個時候再帶入 $c+p^{e-1}y$ 即可得到 $f(x)\equiv 0\pmod{p^2}$ 的解梭域，依次迭代上去即可得到模 $p^e$ 的解斑举，否則當(dāng) $p\mid f'(c)$ ，同時 $p\nmid f(c)p^{1-r}$ (等價 $f(c)\not\equiv 0\pmod{p^e}$ ) 時無解病涨。這樣就有了如公式（4）的方程的解的網(wǎng)狀關(guān)系圖,分別對應(yīng)了上面三種情況懂昂，特別地當(dāng) $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}$

現(xiàn)在我們的問題被轉(zhuǎn)化成了方程 $f(x)\equiv 0\pmod{p}$ 凌彬，研究的方向和一般多項式方程類似沸柔，是關(guān)于方程解的個數(shù)和多項式格式。先假設(shè)方程已經(jīng)做了同余簡化铲敛，但還未做等價簡化褐澎，使用多項式除法和歸納法可以有以下拉格朗日定理：若方程有 m 個不同的解 $x_1,x_2,\cdots,x_m$ ，則必定有唯一表達(dá)式（5）伐蒋，其中g(shù)(x)的首項為 $a_nx^{n-m}$ 工三， $r(x)$ 的次數(shù)低于 m。該定理說明了 n 次同余方程的解的個數(shù)不可能大于 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}$

拉格朗日定理給出了多項式同余方程與根有關(guān)的格式焙畔，值得注意的是掸读，該格式與原多項式是同余，也就是它的本來面貌宏多，這點(diǎn)很重要儿惫。該定理還有其它有趣的應(yīng)用，比如由歐拉定理知 $x^{p-1}-1\equiv 0\pmod{p}$ 有 p?1 個非零解伸但，則有公式（6）肾请，令 $x=0$ 即可得到威爾遜定理！如果再比較 $x$ 和 $xp?2$ 項的系數(shù)更胖，就會有公式（7）（8）铛铁。這里需要注意的是（7）中的 $i$ 與 $j$ 是關(guān)于[p-1/2]對稱的，分別對應(yīng) $x$ 和 $xp?2$ 前面的系數(shù)却妨。還有值得一提的是饵逐，同余方程同可以有“重根”的概念，有興趣朋友可以自己研究一下管呵。
$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 為素數(shù)哺窄，我們以 5 來作為示意展示捐下，證明任意素數(shù) p 時，只需將如下證明思路的模式從 5 推廣到任意 p 即可萌业。觀察（8）并將 $(p-1)!$ 乘到和式里面坷襟，上式左邊便變?yōu)榱? $\sum M_k, 1 \leq k \leq p-1$ 其中 $M_i$ 的定義同以前文章中的定義及 $p-1$ 的階乘除以 $i$ , 于是問題就歸結(jié)到了證明如下式子：
$\sum_{k=1}^{p-1}{M_k}\equiv 0\pmod{p}$ 當(dāng) p = 5時，易知 $4\times3\times2=(5-1)(5-2)(5-3) \equiv -1\times2\times3 \pmod{p}$ 生年，同理其他式子也是一樣婴程，于是我們可觀察得到，當(dāng) 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}$
并且此方法可以推廣到任意的素數(shù) p抱婉，于是（8）式得證档叔。

接下來我們假定方程做了等價簡化桌粉，即 $f(x)$ 的次數(shù)小于p且首項系數(shù)為 1，看看會有什么性質(zhì)衙四。首先若有 $f(x)\equiv g(x)\pmod{p}$ 铃肯，則 $f(x)-g(x)$ 有p個根，從而 $f(x)=g(x)$ 传蹈，換句話說押逼，次數(shù)小于p的首1多項式如果等價則必唯一，即等價和同余是一致的惦界。還有一個問題就是方程的根的個數(shù)問題了挑格，當(dāng) $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個解的充要條件是存在唯一表達(dá)式（9）显歧。
$x^p-x=f(x)g(x)+pr(x)\tag{9}$

關(guān)于高次方程更進(jìn)一步的結(jié)論比較少，這里也不作深究确镊，而二項同余方程 $x^n\equiv a\pmod{p}$ 放到后面的不定方程討論會更簡單士骤，所以這里也不討論了。對一些低次方程蕾域，可以直接對其研究拷肌，我們先從最簡單的一次剩余方程 $ax\equiv b\pmod{m}$ 看起，顯然它是否有解與不定方程 $ax+my=b$ 是否有解是等價的旨巷，故有解的充要條件是 $(a,m)\mid b$ 巨缘。由同余的性質(zhì)，原方程等價于方程（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仰冠{(a,m)}\pmod{\dfrac{m}{(a,m)}}\tag{10}$

直接求逆是復(fù)雜的，一次方程一般用輾轉(zhuǎn)相除法蝶糯，對于一些特殊格式洋只，還可以動用一切同余的性質(zhì)簡化算法。你可以試解決下面這幾個問題：
　 ? 證明 $2^ex\equiv b\pmod{m}$ 的解為 $(\dfrac{m+1}{2})^eb$ ，其中 $(2,m)=1$ 识虚。并由此給出系數(shù)為 $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、二次剩余

現(xiàn)在來研究模為素數(shù)的二次同余方程 $ax^2+bx+c\equiv\pmod{p}$ 妻献，通過配方可以有 $(2ax+b)^2\equiv b^2-4ac\pmod{p}$ 蛛株，從而方程其實等價于二次二項方程 $x^2\equiv d\pmod{p}$ ，當(dāng)然這里不去考慮 $p=2$ 和 $p|d$ 這樣的平凡場景育拨。如果方程有解谨履， $d$ 稱為 $p$ 的二次剩余，否則叫二次非剩余熬丧。為方便描述笋粟，這里先引進(jìn)勒讓德（Legendre）符號 $\left(\dfracokqkmos{p}\right)$ ，并且勒讓德符號或函數(shù)有三個取值析蝴，當(dāng) $d$ 為 $p$ 的二次剩余時其值為1害捕，否則為 ?1，當(dāng) $p|d$ 時值為 0闷畸。

考慮將 $p$ 的既約剩余系分為對稱的兩部分 $-\dfrac{p-1}{2},\cdots,-2,-1$ 和 $1,2,\cdots,\dfrac{p-1}{2}$ 尝盼，顯然 $(-x)^2=x^2$ ，而當(dāng) $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 個數(shù)，所以另外的（p-1）/2 個都是模p的二次非剩余绞幌，共有 $\dfrac{p-1}{2}$ 個二次非剩余蕾哟，每個二次剩余有兩個互為相反數(shù)的根。

我們自然要問：哪些數(shù)是二次剩余莲蜘？如何判斷它是二次剩余谭确？根據(jù)歐拉定理有 $d^{p-1}\equiv 1\pmod{p}$ ，通過移項平方差構(gòu)造容易證明 $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}$ 對，根據(jù)威爾遜定理有 $d^{\frac{p-1}{2}}\equiv -1\pmod{p}$ 。綜合這兩個結(jié)論就是二次剩余的歐拉判別法（公式（11））择诈，當(dāng)然對于大模數(shù)這個方法的計算量還是太大械蹋，它僅有理論價值。
$\left(\dfrac4kgcque{p}\right)=\pm 1\equiv d^{\frac{p-1}{2}}\pmod{p}\tag{11}$

對于一些特殊值羞芍，可以單獨(dú)討論哗戈，得出的結(jié)論也是可以直接使用的。首先容易證明 $?1$ 只有在 $p=4k+1$ 時才是二次剩余荷科，并且由威爾遜定理知 $(\dfrac{p-1}{2})!$ 是它的解唯咬。而且當(dāng) $p=4k+1$ 時，顯然 $x,?x$ 同時是或不是二次剩余畏浆，呈對稱分布胆胰。當(dāng) $p=4k+3$ 時，顯然x,?x有且僅有一個二次剩余刻获，從上面的歐拉判別式即可得到此結(jié)論蜀涨。這些結(jié)構(gòu)都是很有用的。接下來我們可以來看看如下幾個小練習(xí)：

? 討論 $x^2+ay^2\equiv 0\pmod{p},(x,y)=1$ 有解的充要條件蝎毡，并給出求解的方法厚柳；
　　? 求模 $p$ 下所有二次剩余的積與和，再求模 p 下所有二次非剩余的積與和沐兵。

使用勒讓德符號能更清晰地表述二次剩余的性質(zhì)别垮，如下列的這些性質(zhì)（可自行驗證）：
　　（1） $\left(\dfrac{d+kp}{p}\right)=\left(\dfrac4ymiey8{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}}$

使用素數(shù)分解并結(jié)合以上性質(zhì)，可將求一般 $\left(\dfrac6gkqu8y{p}\right)$ 的問題轉(zhuǎn)化為求解 $\left(\dfrac{2}{p}\right)$ 和 $\left(\dfrac{q}{p}\right)$ 上±铣洌現(xiàn)在從另一方面討論 $d^{\frac{p-1}{2}}$ 葡盗，在剩余系 $1,2,\cdots,p-1$ 中考察 $\dfrac{p-1}{2}$ 個數(shù) $d,2d,\cdots,\dfrac{p-1}{2}d$ 的分布，即在既約剩余系中的前 (p-1)/2 個數(shù)乘以二次剩余 d啡浊，然后觀察那些落在了 0到 p/2 內(nèi)觅够，那些落在了 p/2 到 p 內(nèi)。容易證明它們互不相同且互不相反巷嚣，所以它們是以 $\dfrac{p}{2}$ 為對稱軸的兩個數(shù)之一喘先，右半邊的數(shù)（設(shè)個數(shù)為n）需要取相反數(shù)才能回到左邊⊥⒘＃考慮它們的積則容易有 $d^{\frac{p-1}{2}}\equiv (-1)^n\pmod{p}$ 窘拯，這樣就有了二次剩余新的判定方法（公式（12）左）红且，特別地時可以推得 $d=2$ 是二次剩余的條件是 $p=8k±1$ （可寫成公式（12）右）。
$\left(\dfracoo42qgu{p}\right)=(-1)^n,\quad \left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}\tag{12}$

對一般的 $d$ 繼續(xù)上面的結(jié)論涤姊，注意到 $dk=p[\dfrac{dk}{p}]+r_k$ （[x]是取整操作）暇番，對它們求和并在模2 下討論，可以得到式子（13）思喊。而后者有顯著的幾何意義壁酬，它是一個直角三角形區(qū)域內(nèi)的整點(diǎn)個數(shù)『蘅危考慮 $\left(\dfrac{q}{p}\right)$ 對應(yīng)的 $\triangle{OAB}$ 和 $\left(\dfrac{p}{q}\right)$ 對應(yīng)的 $\triangle{OAC}$ 舆乔，它們正好組成了一個長方形區(qū)域，這樣就得到了著名的高斯二次互反律（公式（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}$

二次互反率示意圖

有了這個公式蜕煌，就可以將不斷轉(zhuǎn)化為更小模數(shù)的判定式，從而最終解決了任意的求解诬留。如果上述證明過程斜纪，你感覺還有些不太清楚的話，你還可以參考這里：如何簡潔地證明二次互反律文兑？

在經(jīng)過上述的論述之后盒刚，你還可以嘗試思考下下面這幾個問題：
? 求以3為二次剩余的充要條件，并由此對 $100^2-3$ 進(jìn)行因式分解绿贞；
　　? 求證 $x^4+1$ 的奇素因子都有格式 $8k+1$ 因块；并由此證明格式為 $8k+1$ 的素數(shù)有無窮多個；
　　? $p=4k+3$ 籍铁，求證 $2p+1$ 為素數(shù)的充要條件是 $2^p\equiv 1\pmod{2p+1}$ 涡上；
　　? $p\nmid a$ ，求 $\sum\limits_{x=1}^{p}{\left(\dfrac{x^2+ax}{p}\right)}$ （提示：剩余系的遍歷）拒名。
　　在使用勒讓德符號時要保證模數(shù)是素數(shù)吩愧，這一點(diǎn)很不方便，我們希望這種記法能更通用一點(diǎn)增显。擴(kuò)展后的符號稱為雅克比（Jacobi）符號： $\left(\dfrac2mq8aku{P}\right)=\prod\limits_{k=1}^n{\left(\dfrac6awaw2g{p_k}\right)}$ 雁佳，其中 $P=p_1p_2\cdots p_n$ 。雅克比符號雖然只是一個記法同云，但形式上卻同樣有著漂亮的性質(zhì)糖权，首先有下面幾個簡單的性質(zhì)：
　　
（1） $\left(\dfrac{d+kP}{P}\right)=\left(\dfrackqugcqs{P}\right)$ ；

（2） $\left(\dfrac{d_1d_2}{P}\right)=\left(\dfrac{d_1}{P}\right)\left(\dfrac{d_1}{P}\right)$ 炸站； $\left(\dfracawsg2qq{P_1P_2}\right)=\left(\dfrac6e2o2i8{P_1}\right)\left(\dfracykyuyue{P_2}\right)$ 星澳；

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

在得到更多結(jié)論之前旱易，需要一個引理：如果 $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}$

利用這個結(jié)論就很容易得到雅克比符號的以下性質(zhì)，這些性質(zhì)可以使得雅克比公式的使用更加自由届垫，中間無需關(guān)心操作數(shù)是否為素數(shù)，比如 $\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装处、特殊二次方程的快速解法

上面我們探討一般性的同余方程，然后又探討了較為簡潔的二次同余方程的一般形式浸船，在這里我們繼續(xù)介紹一些特殊的二次同余方程的快速解法妄迁。這在利用計算機(jī)進(jìn)行運(yùn)算時時常會被用到。眾所周知李命，一個素數(shù) $mod \ 8$ 只可能是 $1,3,5,7$ 登淘。在這之中，對于 $mod \ 8$ 為 $3, 5, 7$ 的素數(shù) 封字，我們都能夠快速地解出二次方程 $x^2 \equiv n \pmod{p}$ 黔州。

快速解法的要義實質(zhì)上就是湊！但是如何優(yōu)雅地湊阔籽、在湊的過程中碰到困難如何處理等等還是很有意思的流妻。

首先，我們拿到一個二次方程后自然地會用Legendre符號 $\left(\dfrac{n}{p}\right)$ 判斷其是否有解笆制。在這里我們自然要討論 $\left(\dfracseioseo{p}\right) = 1$ 的二次方程绅这。那么利用 Euler 判別法， $n^{\frac{p-1}{2}}\equiv 1\pmod{p}$ 在辆。這就是我們湊方程解的起點(diǎn)所在证薇。

自然地，我們有 $n^{\frac{p+1}{2}}\equiv n\pmod{p}$ 匆篓，下面把左側(cè)湊成平方形式： $(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$ 的素數(shù)有效俺泣！

對于剩余類型的素數(shù)，我們可以換一個思路：先對于 $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$ 的素數(shù)都能保證 $\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}$ 指厌。但是我們遇到了問題：我們該如何湊出一個數(shù)，使得其平方在 $mod p$ 意義下為 -1 呢踊跟？Wilson 定理給了我們答案踩验！對于素數(shù) 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定理不僅僅為我們提供了一個數(shù)為素數(shù)的充要條件袭异，其也幫助我們計算出了域 $Z_p$ 上的 $\sqrt{-1}$ ！

由于上述討論中我們一直假定p 為奇素數(shù)炬藤，故我們一直沒討論模為 $2^a$ 時的方程解法御铃。下面我們討論方程 $x^2 \equiv n \pmod{2^a}$ ，其中假定 n 為奇數(shù)沈矿。

當(dāng)模為 2 或 4 時我們分類討論容易得到結(jié)論畅买。模為2 時的解存在唯一，而模為4 時要么無解要么有唯一解细睡，解存在的充要條件為 $n \equiv 1\pmod{4}$ 谷羞。（這很自然，因為所有奇數(shù)的平方都是模 4 余 1 的）

在模為 $2^a \ (a\geq 3)$ 時溜徙，我們先討論其解的存在性與解的結(jié)構(gòu)湃缎。

方程的解存在當(dāng)且僅當(dāng) $n \equiv 1 \pmod{8}$ （這很好理解，因為所有奇數(shù)的平方都是模8 余 1 的）蠢壹，且給定方程特解 $x_0$ 后嗓违，可以確定其所有四個解 $\pm x_0,\pm x_0+2^{a-1}$ 。你可以自己驗證下图贸。

具體求解的情形中我們效仿高次同余方程的做法蹂季，利用 $x^2 \equiv n\pmod{2^{a-1}}$ 的解構(gòu)造 $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$ 宾肺。那么由這類方程解的結(jié)構(gòu)溯饵，其全部四個解 $\pm x_0,\pm x_0+2^{a-1}$ 我們就都知道了！

【初等數(shù)論】同余方程、與二次剩余互反律

【初等數(shù)論】同余方程退盯、與二次剩余互反律

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

1渊迁、同余方程

2、二次剩余

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