初等數論學習筆記（五）

08-21

初等數論學習筆記（五）

來自專欄 sola的數學筆記

最後幾個大部分是最有趣的部分，我們可以開始觸及到深層的內容，擁有更高級的工具與手段。我們可以得到更加意想不到的結論，並且也能夠對我們過去證明過的定理再一次審視，給出更加簡潔更加本質的證明。

二次剩餘

一、基本概念與Euler判別法

定義：

本章默認 $p$ 為大於2的素數， $(a,p)=1$

考慮方程 $x^2equiv a(mod p)$

若此方程有解，稱 $a$ 為 $mod p$ 的二次剩餘，否則稱 $a$ 為 $mod p$ 的二次非剩餘。

值得提及的是，此處給出的二次方程是沒有一次項的。當我們遇到有一次項的二次同餘方程時，我們必定可以配方後進行換元化為這種形式的二次方程。

與之前同樣地，我們對一個同餘方程的研究總是從解的結構入手。

定理：（二次同餘方程解的結構）

方程 $x^2equiv a(mod p)$ 要麼有兩解要麼無解。

證明：

由（四）中對模為素數的同餘方程解的結構的定理，我們知道此方程的解的個數不超過次數2。（解兩兩 $mod p$ 不同餘）

下證明若有解，必有兩解。

若 $x$ 為解，一個自然的疑問是 $-x$ 是否為解呢？

由 $(x,p)=1$ ，若 $xequiv-x(mod p)$ ， $p|2xRightarrow p|2$ ，矛盾。

故 $-x$ 必也為解。

若有解，必定成對出現。

由此，我們還額外得到了一個推論：

推論： $mod p$ 的二次剩餘和二次非剩餘總是各有 $frac{p-1}{2}$ 個。

證明：

取 $mod p RRS$ $left { -frac{p-1}{2}, -frac{p-1}{2}+1,...,-1,1,...,frac{p-1}{2} ight }$ ，則 $a$ 為 $mod p$ 的二次剩餘的充要條件是 $aequiv (-frac{p-1}{2})^2 or aequiv (-frac{p-1}{2}+1)^2 or ... or aequiv (frac{p-1}{2})^2 (mod p)$

而由上一個定理的證明過程， $x^2equiv (-x)^2 (mod p)$ ，故每一對相反數中，總是恰產生一個二次剩餘。故 $mod p$ 的二次剩餘和二次非剩餘總是各有 $frac{p-1}{2}$ 個。

接下來，只需利用Fermat定理，我們便能很容易地得到判定 $a$ 是否為 $mod p$ 二次剩餘的充要條件：Euler判別法。

定理（Euler判別法）：

$a$ 為 $mod p$ 的二次剩餘 $Leftrightarrow a^{frac{p-1}{2}}equiv 1(mod p)$

$a$ 為 $mod p$ 的二次非剩餘 $Leftrightarrow a^{frac{p-1}{2}}equiv -1(mod p)$

證明：

首先由Fermat定理， $a^{p-1}equiv 1(mod p)$ ，由於此處 $p$ 必為奇數，可進行因式分解。

得到 $p|(a^{frac{p-1}{2}}+1)(a^{frac{p-1}{2}}-1)$

由於 $p$ 為素數， $p|(a^{frac{p-1}{2}}+1)$ 與 $p|(a^{frac{p-1}{2}}-1)$ 中至少一者成立。

又 $(a^{frac{p-1}{2}}+1)不同餘與(a^{frac{p-1}{2}}-1) (mod p)$ （否則與 $p$ 為奇素數矛盾）

故 $p|(a^{frac{p-1}{2}}+1)$ 與 $p|(a^{frac{p-1}{2}}-1)$ 中有且僅有一者成立。

故接下來只需要證明定理中的一半即可： $a$ 為 $mod p$ 的二次剩餘 $Leftrightarrow a^{frac{p-1}{2}}equiv 1(mod p)$

$Rightarrow$ ： $x^2equiv a(mod p)$ 有解，則 $x^{p-1}equiv a^{frac{p-1}{2}}(mod p)$

由 $(p,a)=1$ ，易知 $(p,x)=1$ ，故由Fermat定理， $x^{p-1}equiv 1equiv a^{frac{p-1}{2}}(mod p)$ ，得證。

$Leftarrow$ ：易知 $(p,a)=1$ ，考慮一次方程 $bxequiv a(mod p)$ 。

根據上一章中關於一次方程的理論，對於 $mod p RRS S=$ $left { -frac{p-1}{2}, -frac{p-1}{2}+1,...,-1,1,...,frac{p-1}{2} ight }$ 中的每一個 $j$ ，若 $b=j$ ，必有唯一的 $x=x_jin S, s.t.$ $bxequiv a(mod p)$ 。

反證，若 $a$ 為 $mod p$ 的二次非剩餘， $j eq x_j$ ，則 $S$ 中的 $p-1$ 個數可以按照 $j,x$ 兩兩配對分組。

故 $(p-1)!equiv a^{frac{p-1}{2}}(mod p)$ 。又由Wilson定理， $(p-1)!equiv -1(mod p)$ ，故矛盾。得證。

Euler判別法是重要的，因為它給出了作為二次剩餘或二次非剩餘的充要條件。然而，在實際應用中，Euler判別法使得計算變得繁瑣。當 $p$ 較大時尤其如此，故接下來，我們想要引進新的數論函數來簡化對於二次剩餘的判別。

二、Legendre符號

本章默認 $p$ 為大於2的素數， $(a,p)=1$

定義： $(frac{a}{p})= egin{cases} 1 if a為mod p二次剩餘\ -1 if a為mod p二次非剩餘 end{cases}$ ，稱為Legendre符號。

Legendre符號本質上來說就是二次剩餘的特徵函數，然而這樣一個不起眼的特徵化操作實際上會帶來很多好的性質，為二次剩餘的判別帶來許多方便。（如果我們學習過概率論，我們可以聯想到將概率化為特徵函數的期望，那也是一種特徵化的手段，在數學中是十分常用的）

先給出一些Legendre符號的基本性質：

1、 $(frac{1}{p})=1,(frac{a^2}{p})=1$ （顯然，二次剩餘定義）

2、 $(frac{a}{p})equiv a^{frac{p-1}{2}}(mod p)$ （Euler判別法）

3、若 $a_1equiv a_2(mod p)$ ，則 $(frac{a_1}{p})=(frac{a_2}{p})$ （證略）

4、 $(frac{a_1a_2...a_n}{p})=(frac{a_1}{p})(frac{a_2}{p})...(frac{a_n}{p})$

證明：

Legendre符號取值只能為 $pm 1$

$(frac{a_1a_2...a_n}{p})equiv (a_1a_2...a_n)^{frac{p-1}{2}}(mod p)=a_1^{frac{p-1}{2}}a_2^{frac{p-1}{2}}...a_n^{frac{p-1}{2}}equiv (frac{a_1}{p})(frac{a_2}{p})...(frac{a_n}{p})(mod p)$

故得證。（同餘關係化為等於關係）

性質4表明：Legendre符號是關於 $a$ 的完全積性函數，這是一條很重要的性質。

5、 $(frac{-1}{p})=(-1)^{frac{p-1}{2}}$ （用上述同樣技巧使同餘變為等於）

這告訴我們： $egin{cases} -1為p的二次剩餘 if pequiv 1(mod 4)\ -1為p的二次非剩餘 if pequiv 3(mod 4) end{cases}$

到目前為止，對於給定的 $p$ ，我們還不能計算出對於任意 $a$ 的Legendre符號的值。但是由算術基本定理，我們知道，如果解決了所有形如 $(frac{2}{p})$ ， $(frac{q}{p})$ （ $p,q$ 為奇素數）的值，便能徹底解決Legendre符號的求值問題。

然而求出所有形如 $(frac{q}{p})$ （ $p,q$ 為奇素數）的值是困難的。我們接下來將會先試著求出 $(frac{2}{p})$ 的值，再給出Gauss二次互反律，這將會揭示出 $(frac{q}{p})$ 與 $(frac{p}{q})$ 之間的深刻聯繫。（ $p,q$ 為奇素數）

為此，我們先給出一個證明中要用到的Gauss引理。

引理（Gauss）: $p$ 為大於2的素數， $(a,p)=1$ ，對於 $1leq j<frac{p}{2}$ ， $t_jequiv ja(mod p),0<t_j<p$ ， $n$ 為這 $frac{p-1}{2}$ 個 $t_j$ 中大於 $frac{p}{2}$ 的個數，則有 $(frac{a}{p})=(-1)^n$ 。

證明：

$forall 1leq j<i<frac{p}{2}$ ，顯然有 $t_i otequiv pm t_j(mod p)$ 成立。

設 $t_j$ 中大於 $frac{p}{2}$ 的數為 $r_1,r_2,...,r_n$ ，小於 $frac{p}{2}$ 的數為 $s_1,s_2,...,s_k$ 。

則 $1leq p-r_i<frac{p}{2}$ ，故 $s_j otequiv p-r_i(mod p)$

故 $s_1,s_2,...,s_k,p-r_1,p-r_2,...,p-r_n$ 恰好為 $1,2,...,frac{p-1}{2}$ 的排列。

故 $(frac{p-1}{2})! a^{frac{p-1}{2}}equiv s_1...s_kr_1...r_nequiv (-1)^ns_1s_2...s_k(p-r_1)(p-r_2)...(p-r_n)(mod p)$

$equiv (-1)^n(frac{p-1}{2})!(mod p)$

而 $((frac{p-1}{2})!,p)=1$

故 $a^{frac{p-1}{2}}equiv (-1)^n(mod p)$ ，得證。

Gauss引理的意義在於其將是否為二次剩餘與 $n$ 奇偶性聯繫在了一起，而 $n$ 表示了 $1,2,...,frac{p-1}{2}$ 中乘 $a$ 後所得到的 $a_j$ 的 $mod p$ 的最小正剩餘不在 $1,2,...,frac{p-1}{2}$ 中的數的個數。然而我們對於 $n$ 的性質是不清楚的，故還需要進行進一步的分析。但是作為應用，在進一步分析之前我們首先先給出 $(frac{2}{p})$ 的值的求法。

定理： $(frac{2}{p})=(-1)^{frac{p^2-1}{8}}$

證明：

利用Gauss引理，取 $a=2$

則容易算出 $n=frac{p-1}{2}-[frac{p}{4}]$ （具體計算交給讀者）

又 $frac{p-1}{2}-[frac{p}{4}]與frac{p^2-1}{8}$ 在 $p$ 為奇素數時有相同的奇偶性。（可以討論 $p$ 在 $mod 8$ 下的情況驗證）

得證。

這告訴我們： $egin{cases} 2為p的二次剩餘 if pequiv pm1(mod 8)\ 2為p的二次非剩餘 if pequiv pm 3(mod 8) end{cases}$

對於Gauss引理，進一步地分析，利用取整函數， $ja=p[frac{ja}{p}]+t_j,1leq t_j<frac{p}{2}$

同時對 $j$ 求和，得到 $asum_{j=1}^{frac{p-1}{2}}j=psum_{j=1}^{frac{p-1}{2}}[frac{ja}{p}]+sum_{j=1}^{frac{p-1}{2}}t_j$

由Gauss引理的證明， $sum_{j=1}^{frac{p-1}{2}}t_j=s_1+...+s_k+r_1+...+r_n=$

$s_1+...+s_k+(p-r_1)+...+(p-r_n)-np+2(r_1+...+r_n)=sum_{j=1}^{frac{p-1}{2}}j-np+2(r_1+...+r_n)$

注意到此處也可以直接推出 $(frac{2}{p})=(-1)^{frac{p^2-1}{8}}$ 的結論。（令 $a=2$ ）

我們發現當 $(a,2p)=1$ 時， $sum_{j=1}^{frac{p-1}{2}}[frac{ja}{p}]equiv n(mod 2)$ ，故我們得到了 $n$ 的明確表達式，表示我們的分析可以結束了。

我們得到了新的引理：

引理： $(a,2p)=1$ 時， $(frac{a}{p})=(-1)^{sum_{j=1}^{frac{p-1}{2}}[frac{ja}{p}]}$ 。

下面，很自然地，我們給出二次互反律的證明。

定理（Gauss二次互反律）： $p,q$ 均為大於2的互異的素數，則 $(frac{p}{q})(frac{q}{p})=(-1)^{frac{p-1}{2}frac{q-1}{2}}$ 。

證明：

利用以上引理， $(frac{p}{q})(frac{q}{p})=(-1)^{sum_{j=1}^{frac{p-1}{2}}[frac{jq}{p}]+{sum_{j=1}^{frac{q-1}{2}}[frac{jp}{q}]}}$ 。

接下來，回憶筆記（二）中的習題二，此處 $(p,q)=1$ ，均為奇素數

$sum_{j=1}^{frac{p-1}{2}}[frac{jq}{p}]+{sum_{j=1}^{frac{q-1}{2}}[frac{jp}{q}]}=frac{p-1}{2}frac{q-1}{2}$ ，故得證。

Gauss二次互反律結合Legendre符號的性質3，性質4，以及我們已知的 $(frac{1}{p})，(frac{-1}{p})，(frac{2}{p})$ 的值，使得對於給定的 $p$ ， $forall a, (a,p)=1$ ，都能夠計算出 $(frac{a}{p})$ 的值。（讀者可思考為什麼）

可推廣地來說，Legendre符號也可以判斷模非素數的二次同餘方程的解的存在性。（可借鑒模不兩兩互素時變形利用中國剩餘定理的方式）

接下來，我們簡單地介紹一下Jacobi符號，並且說明他們之間的聯繫與區別。

三、Jacobi符號

定義： $P$ 為大於1的奇數，其素數分解式 $P=p_1p_2...p_k(p_i均為素數),(a,P)=1$ 。則 $(frac{a}{P})=(frac{a}{p_1})(frac{a}{p_2})...(frac{a}{p_k})$ 定義為Jacobi符號。

Jacobi符號取值也只能為 $pm 1$ 。容易知道的是， $P$ 為素數時，Jacobi符號就是Legendre符號。自然地，我們推測Jacobi符號會具有Legendre符號的大多數性質：

1、若 $a_1equiv a_2(mod p)$ ，則 $(frac{a_1}{P})=(frac{a_2}{P})$ （證略）

2、 $(frac{-1}{P})=(-1)^{frac{P-1}{2}}$

證明：

$(frac{-1}{P})=(frac{-1}{p_1})(frac{-1}{p_2})...(frac{-1}{p_k})=(-1)^{frac{p_1-1}{2}+...+frac{p_k-1}{2}}$

在此不妨設 $p_i=1+2m_i(1leq ileq k)$

$(frac{-1}{P})=(-1)^{m_1+...+m_k}$

而 $(-1)^{frac{P-1}{2}}=(-1)^{frac{(1+2m_1)...(1+2m_k)-1}{2}}$

又容易知道的是 $(1+2m_1)(1+2m_2)...(1+2m_k)equiv 1+2(m_1+...+m_k)(mod 4)$ （展開即可證明）

故 $(frac{-1}{P})=(-1)^{frac{P-1}{2}}$ 。

後續性質可模仿性質2進行證明，留作習題。

3、 $(frac{a_1a_2...a_n}{P})=(frac{a_1}{P})(frac{a_2}{P})...(frac{a_n}{P})$ （關於 $a$ 的完全積性）

4、 $(frac{2}{P})=(-1)^{frac{P^2-1}{8}}$

5、 $P,Q$ 均為大於1的奇數，且 $(P,Q)=1$ ，則 $(frac{P}{Q})(frac{Q}{P})=(-1)^{frac{P-1}{2}frac{Q-1}{2}}$ 。（二次互反律）

值得說明的一點是Jacobi符號與Legendre符號的本質區別。

Jacobi符號 $(frac{a}{P})=1$ 並不表示同餘方程 $x^2equiv a(mod P)$ 一定有解。

此處舉出一個反例：

例：考慮同餘方程 $x^2equiv 2(mod 3599)$ 。

解：

Jacobi符號 $(frac{2}{3599})=(frac{2}{59})(frac{2}{61})=(-1)^{frac{59^2-1}{8}+frac{61^2-1}{2}}=1$

然而，該同餘方程等價於方程組

$egin{cases} x^2equiv 2(mod 59)\ x^2equiv 2(mod 61) end{cases}$

而Legendre符號 $(frac{2}{59})=-1，(frac{2}{61})=-1$ ，方程組無解，故原方程無解。

所以Jacobi符號並不能判斷二次同餘方程是否有解。

剩下的更多的有用、有趣的性質以及他們所能證明的有趣結論我們都留作習題。

習題：（若無特別說明 $p$ 為大於2的素數，字母均為正整數）

1、證明： $pequiv 1(mod 4)$ 時， $((frac{p-1}{2})!)^2equiv -1(m od p)$

2、判斷下列方程的解數：

（1）： $x^2equiv 6(mod 79)$

（2）： $x^2equiv -63(mod 187)$

3、證明：若 $A$ 為偶數， $p|A^2+1$ ，則 $pequiv 1(mod 4)$

4、證明：存在無窮多個 $mod 4$ 餘1的素數。

5、證明：若 $A$ 為偶數， $p>3,$ $p|A^2+3$ ，則 $pequiv 1(mod 6)$

6、證明：存在無窮多個 $mod 6$ 餘1的素數。

7、證明：（均為Jacobi符號）

（1） $(frac{a_1a_2...a_n}{P})=(frac{a_1}{P})(frac{a_2}{P})...(frac{a_n}{P})$ （關於 $a$ 的完全積性）

（2） $(frac{2}{P})=(-1)^{frac{P^2-1}{8}}$

（3） $P,Q$ 均為大於1的奇數，且 $(P,Q)=1$ ，則 $(frac{P}{Q})(frac{Q}{P})=(-1)^{frac{P-1}{2}frac{Q-1}{2}}$ 。（二次互反律）

8、證明： $pequiv 1(mod 4)$ 時， $exists a,bin mathbb{Z},a^2+b^2=p$ 。（Fermat，模4餘1的數必能寫成兩個整數平方和的形式）

提示或解答：

1、提示：回憶 $mod p RRS$ 的性質：任意兩個 $mod p RRS$ 中所有元素的乘積 $mod p$ 同餘。由此規範性，考慮 $left { 1,2,...,p-1 ight }$ 與 $left { -frac{p-1}{2}, -frac{p-1}{2}+1,...,-1,1,...,frac{p-1}{2} ight }$ ，再應用Wilson定理即可得證。