Legendre symbol & Law of Quadratic Reciprocity勒讓德符號與二次互反律

作者：由 WeiWei 發表于書法時間：2021-03-25

在學習數論判定二次同餘方程的過程中，第一次有幸接觸到 Legendre 符號，當時並沒有很好的對它產生比較整體的理解（中午實在沒有時間來好好休息。。。）。OK，那就正好借這個機會在專欄寫第一篇文章來一起學一遍吧！

Legendre Symbol 簡介

對於素數

，任意整數

，定義 Legendre 符號如下：

$\left(\frac{d}{p}\right)=\left\{\begin{array}{ll}1, & \text { 如果 } x^{2} \equiv d \quad(\bmod p) \text { 有非零解, } \\ -1, & \text { 如果 } x^{2} \equiv d \quad(\bmod p) \text { 無解, } \\ 0, & \text { 如果 } p \mid d .\end{array}\right.$

例如

$\left(\frac{2}{5}\right)=-1$

。

這一符號需要一個素數，以及一個任意整數，這兩個引數就可以定義一個二次同餘方程：

$x^{2} \equiv d \quad(\bmod p)$

，這裡，稱

是模

的二次剩餘。

Legendre 符號就表示了該方程解的三種存在情況。這樣看好像單獨定義這樣的記號顯得很麻煩，但是這樣來源於一個看似很簡單問題的定義在數學體系裡很多地方都存在，而且能儲存至今的，都發揮著巨大的作用。

下面簡述幾個性質，並介紹（照搬wiki）我自己在學習過程中幾個疑惑點的解答。

簡單的一些性質

由於沒查到名字，我就隨便整幾個，其他地方千萬不要用啊！！！

分子週期

$\left(\frac{d}{p}\right)=\left(\frac{p+d}{p}\right)$

即，Legendre 符號中，單看分子部分的話，是一個以

為週期的週期函式，這是個很顯然的性質，由於在恆等號

$\equiv$

左右加減模掉的數，仍然是恆等式。

函式解析式

$\left(\frac{d}{p}\right)=d^{(p-1) / 2} \quad(\bmod p) \tag{1}$

這個性質將需要解方程的問題簡單轉化為了一個帶餘除法問題，是個好性質，但是做起來挺複雜的。在看這個的時候由於之前查到的資料有些差錯，還好在友人幫助下給我指了一條明路。

由於給出定義時，分了三種情況，其中

$p \mid d$

的情況實在簡單，這裡不贅述，於是

情況一 : 方程有非零解

即，存在

$a \in \mathbb{Z}$

，滿足

$a^{2} \equiv d \quad(\bmod p)$

那麼，兩邊同時進行乘冪運算，必有

$d^{(p-1) / 2} \equiv a^{p-1}\quad(\bmod p)$

由於這裡的

是素數，於是引用Fermat 小定理

［1］

可以得知

$a^{p-1} \equiv 1 \quad(\bmod p)$

於是，情況一就可以使用

$d^{(p-1) / 2} \quad(\bmod p)$

代替原本的

情況二 : 方程無解

即，一次同餘方程

$j \cdot x \equiv d \quad(\bmod p)$

的解

$x_{j}$

滿足：

$x_{j} \neq j$

這樣，我們可以考慮模

得到的剩餘類乘法群，運用群運算的封閉性，在這裡可以用如下語言敘述：

在集合

$\{ 1,2,3, \cdots, p-1\}$

中必能分出

個數對

$\{j,x_{j}\}$

，

這些數對滿足上述的一次同餘方程，將這些數對對應的方程全部乘起來，有如下方程：

$d^{(p-1) / 2} \equiv(p-1) ! \quad(\bmod p)$

同時由於

是素數這一強大的條件，可以運用Wilson定理

［2］

，得到了和題設相同的結果

$d^{(p-1) / 2}\equiv-1 \quad(\bmod p)$

。

$\square$

至此，“函式解析式”性質的證明完成了，如果需要證明過程其中引用的，兩大素數相關結論細節的話在文末或者會專門開一篇文章來進行敘述。

完全積性（這個倒是挺官方的一個名字）

$\left(\frac{d c}{p}\right)=\left(\frac{d}{p}\right)\left(\frac{c}{p}\right)$

這個性質可以簡單的運用解析式得到，不再贅述。

二次互反律

如果

均是奇素數，且

$p \neq q$

，那麼：

$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{(p-1)(q-1)}{4}} \tag{2}$

；

特殊的，有：

$\left(\frac{2}{p}\right)=(-1)^{\frac{p^{2}-1}{8}} \tag{3}$

。

為了證明這個定理，我們先證明一個引理。

設素數

$p> 2, p \nmid d, 1 \leq j \leq (p-1)/2$

，滿足：

$t_{j} \equiv j d \quad(\bmod p), \quad 0<t_{j}<p \tag{4}$

用

表示這

個

$t_{j}$

中大於

的項數個數，於是有：

$\left(\frac{d}{p}\right)=(-1)^{n}$

。

接下來，證明這個引理。

在

$\{t_{j}\}$

序列中，任取

$t_{i},t_{j}$

，

$i \neq j$

，

考慮

$t_{i}\pm t_{j}$

，有

$t_{j} \equiv j d \quad(\bmod p)$

，以及

$t_{i} \equiv i d \quad(\bmod p)$

，兩式相加，可以得到：

$t_{j}\pm t_{i} \equiv (j\pm i) d \quad(\bmod p)$

由於

都在

之間

$i\pm j$

永不整除

，故

$t_{i} \not \equiv \pm t_{j} \quad(\bmod p), \quad i \neq j . \tag{5}$

使用

$r_{1},r_{2},r_{3},\cdots,r_{n}$

來表示

$\left\{t_{j}\mid 1 \leq j \leq(p-1) / 2\right\}$

中大於

的數，

使用

$s_{1},s_{2},s_{3},\cdots,s_{k}$

來表示

$\left\{t_{j}: 1 \leq j \leq(p-1) / 2\right\}$

中小於

的數，

從（5）來看，位於

之間的

$t_{i}$

在同餘意義下是互不相等的，於是可以寫出：

$\left\{s_{1}, s_{2}, \cdots, s_{k}, p-r_{1}, p-r_{2}, \cdots, p-r_{n}\right\}=\{1,2, \cdots,(p-1) / 2\} \tag{6}$

那麼，仿照之前Legendre 符號的解析式證明方法，將這些連乘起來，可得到：

$\prod_{j=1}^{(p-1) / 2} t_{j} \equiv d^{(p-1) / 2} \prod_{j=1}^{(p-1) / 2} j \quad(\bmod p)$

，同時，根據（6），可以把

$t_{j}$

的連乘與下角標進行轉化，簡單的說明思路：由於在乘法分配律，

$\alpha t \equiv \alpha(t \pm p) \quad (\bmod p)$

這樣的同餘關係式是恆成立的，於是，得到我們的結果：

$d^{(p-1) / 2} \prod_{j=1}^{(p-1) / 2} j \equiv(-1)^{n} \prod_{j=1}^{(p-1) / 2} j \quad(\bmod p) \tag{7}$

這裡，運用之前的解析式（1），我們的引理得到證明。

$\square$

這樣，基本的準備工作就已經完成了，下一部分，將完成二次互反律的證明。

二次互反律的證明

這裡給出一個已知結論再進行的證明，其中的證明思路比較違背思考問題的順序，但也在一定程度上表現了這一定律的核心思想，關於具體的探索過程可見各大百科

［3］

。

以下證明中符號大部分沿用引理中的，故不再重複定義。

首先，考慮這樣的一個整數分解：

$j q=p\left[ \frac{j q}{p} \right]+t_{j}$

，其中

滿足

$1\leq j \leq (p-1)/2$

，將這樣的離散性質沿用之前的思路，連加起來，得到：

$q \sum_{j=1}^{(p-1) / 2} j=p \sum_{j=1}^{(p-1) / 2}\left[\frac{j q}{p}\right]+\sum_{j=1}^{(p-1) / 2} t_{j}$

，

為了以後證明的考慮以及等式的美化，令：

$T=\sum_{j=1}^{(p-1) / 2}\left[\frac{j q}{p}\right ] \tag{8}$

得到比較清晰的表示式：

$q \sum_{j=1}^{(p-1) / 2} j=p T+\sum_{j=1}^{(p-1) / 2} t_{j} \tag{9}$

，

看到這個，顯然需要把兩邊求和式中的

$t_{j},j$

聯絡起來，想到之前的（6），其中：

$\sum_{i=1}^{\lfloor p / 2\rfloor-n} s_{i}+\sum_{i=1}^{n}\left(p-r_{i}\right)=\sum_{j=1}^{(p-1) / 2} j$

，

$\sum_{j=1}^{(p-1) / 2} t_{j}=\sum_{i=1}^{n} r_{i}+\sum_{i=1}^{\lfloor p / 2\rfloor-n} s_{i}$

，

兩式進行消元，不難得到：

$\sum_{j=1}^{(p-1) / 2} t_{j} = \sum_{j=1}^{(p-1) / 2} j-n p+2 \sum_{j=1}^{n} r_{j} \tag{10}$

好耶，之後把（10）帶進（9），並且進行簡單的等差數列求和，於是有：

$\frac{p^{2}-1}{8}(q-1)=p(T-n)+2 \sum_{j=1}^{n} r_{j} \tag{11}$

，

這下，用這個結果返回要證的一個特殊情況：

，

之所以討論這個情況，需要回到（8）裡，從

的定義來看，

將

帶進去，得到：

$T = \sum_{j=1}^{(p-1)/2} \left [ \frac{2j}{p} \right ]$

，而對所有的

，在這個公式中都是小於

的，那麼就簡單的知道，

。

於是得到

$\frac{p^2 -1}{8} = -np + 2 \sum _{j =1}^{n}r_{j}$

，為了得到和

匹配的奇偶性，使用

來模：

$-nq \equiv\left(p^{2}-1\right) / 8 \quad(\bmod 2)$

，

其中

是不為

的素數，故他/她/它不會影響模去

的結果，那麼來了：

$n \equiv\left(p^{2}-1\right) / 8 \quad(\bmod 2)$

。

對應之前證明的引理，

$\left(\frac{2}{p}\right)=(-1)^{n}$

，這裡

與

$\left(p^{2}-1\right) / 8$

有相同的奇偶性，於是就得到其中一個結論（3）；

之後

，對（2）考慮，令

$p = 2t +1, t \in \mathbb{N}$

，於是

必有

這個因子，那就有（11）的變形：

$n \equiv T \quad(\bmod 2)$

，

於是有

$\left(\frac{q}{p}\right)=(-1)^{T}$

，這顯然不滿足我們的追求，把他/她/它寫的完整一些，就有：

$\left(\frac{q}{p}\right)=(-1)^{\sum_{j=1}^{(p-1) / 2}\left [\frac{j q}{p}\right]}$

，

這下，我們不得不考慮這裡的

究竟是什麼，有沒有更好的表達形式？

這裡，將高斯（Gauss）函式中的

$\frac{q}{p}$

看成斜率，那麼把

座標系中表達出來一切事情就清晰了。

把求和指標看成橫座標，每個

對應的求和項就是以這個

為橫座標，縱座標在

$\frac{q}{p} j$

下方的整點數量，單獨這樣求的話實在複雜，但是正如（2）給出的形式

$\left( \frac{q}{p}\right) \left ( \frac{p}{q}\right)$

，來進行考慮的話，就有：

$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\sum_{j=1}^{(p-1) / 2}\left[\frac{j q}{p}\right]+\sum_{j=1}^{(q-1) / 2}\left[\frac{j p}{q}\right]}$

，

那麼這裡的指數，就是在

$\frac{(p-1)}{2} \times \frac{(q-1)}{2}$

這個矩形內部的整點數，至此，（2）也完成了他/她/它的證明。

$\square$

後記

寫在這裡的只是關於 Legendre 符號和二次互反律的一小部分內容，之後可能會進行不定時的補充。鑑於個人水平有限，不能避免的會在某些地方出錯，如果能得到高人指點，感激不盡！！！

對於偶然刷到這篇文章的小夥伴，希望我寫的這些文字能幫到你哦。❤️❤️❤️

參考

Fermat小定理

https：//zh。wikipedia。org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86

Wilson定理

https：//zh。wikipedia。org/wiki/%E5%A8%81%E5%B0%94%E9%80%8A%E5%AE%9A%E7%90%86

二次互反律

https：//zh。wikipedia。org/wiki/%E4%BA%8C%E6%AC%A1%E4%BA%92%E5%8F%8D%E5%BE%8B

標簽：證明 Legendre E5% 素數同餘

上一篇:《紅樓夢》林黛玉的眼睛到底是什麼樣子的？

下一篇：滑雪跟拍一般是單板還是雙板?

Legendre symbol & Law of Quadratic Reciprocity勒讓德符號與二次互反律

猜你喜歡

求助！實習證明怎麼搞?

素數的分佈是由哥猜還是由黎猜決定的？

導數中的零點差問題（第三講）

素數及它的個數之三：解簡易不定方程的另類嘗試

人性中暴力血腥的成分是天生的嗎？

Legendre symbol & Law of Quadratic Reciprocity勒讓德符號與二次互反律

猜你喜歡

求助！實習證明怎麼搞?

素數的分佈是由哥猜還是由黎猜決定的？

導數中的零點差問題（第三講）

素數及它的個數 之三：解簡易不定方程的另類嘗試

人性中暴力血腥的成分是天生的嗎？

素數及它的個數之三：解簡易不定方程的另類嘗試