Legendre符號(hào)及Gauss二次互反律的證明

郭向榮

（唐山師范學(xué)院 數(shù)學(xué)與信息科學(xué)系，河北 唐山 063000）

Legendre符號(hào)是由法國(guó)數(shù)學(xué)家阿德里安-馬里·勒讓德在1798年嘗試證明二次互反律時(shí)引入的函數(shù)。這個(gè)符號(hào)是許多高次剩余符號(hào)的原型，它的延伸和推廣包括雅可比符號(hào)、克羅內(nèi)克符號(hào)、希爾伯特符號(hào)，以及阿廷符號(hào)。二次互反律被譽(yù)為“算術(shù)中的寶石”，特別是在同余理論里，二次互反律是一個(gè)用于判別二次剩余，即二次同余方程 x2≡p(modq）之整數(shù)解的存在性的定律。Legendre曾經(jīng)提出過(guò)二次互反律的猜想。但第一個(gè)嚴(yán)格的證明是由 Gauss在 1796年作出的，隨后他又發(fā)現(xiàn)了另外七個(gè)不同的證明。Gauss之后Kummer、Eisenstein、Hilbert、Artin、Furtwangler等也相繼給出了新的證明。至今，二次互反律已有超過(guò)200個(gè)不同的證明。本文利用有限域的一些知識(shí)，給出這個(gè)定理的一個(gè)證明。Jacobi符號(hào)是Legendre符號(hào)的一種推廣，允許底數(shù)為合數(shù)，但底數(shù)仍然必須是奇數(shù)和正數(shù)。這個(gè)推廣提供了計(jì)算所有勒讓德符號(hào)的一個(gè)有效的方法。本文將 Legendre符號(hào)與Jacobi符號(hào)在計(jì)算上進(jìn)行了比較和總結(jié)。

1 Legendre符號(hào)定義及其基本性質(zhì)

設(shè)Zp表示模p的剩余類環(huán)，當(dāng)p為素?cái)?shù)時(shí)，Zp形成域，其中僅含p個(gè)元素，令 Zp*=Zp-{0}，則 Zp*對(duì) Zp的乘法形成一個(gè)p-1階的循環(huán)群，本文總假定p為素?cái)?shù)。

定義1 設(shè)p為素?cái)?shù)，a ∈ Zp*若 xn≡ a(mod p)（這里n為大于1的整數(shù)）于Zp里有解，則稱a叫做模Zp*的n次方元。否則a就稱為Zp*的非n次方元。

定理 （1）如果p=2，則Zp*中每個(gè)元素都是平方元素。（2）如果p≠2則Zp*的平方元素形成Zp*的指數(shù)為2的不變子群。

由此定理得到，所有Zp*平方元素作成一個(gè)Zp*的子群，并且是Zp*的階循環(huán)子群。

從而將

擴(kuò)充到Zp的全部元素上，并且對(duì)于x∈Zp，若x有象元素x'∈ Zp ，則記作

性質(zhì)1 若p/| mn ，則

為一積性函數(shù)。

性質(zhì)2 （1）兩個(gè)平方元素之積仍為平方元素。

（2）兩個(gè)非平方元素之積仍為平方元素。

（3）一個(gè)平方元素與一非平方元素之積為一非平方元素。

性質(zhì)3 p＞2，則

換言之，若 p≡1（mo d u）則-1為 Zp的平方元素，若p≡3（mo d u）則-1為Zp的非平方元素。

設(shè)p為奇素?cái)?shù)，S為Zp*的子集，Zp*為S與-S的并集，取

如果s∈S，a ∈ Zp*我們記為形式 as= es（a ）sa，其中es（a）= ±1, Sa∈S

證明 若s與s'是S的兩個(gè)相異元素，則有 sa± sa'，否則 sa= sa'，即有 as=± as'，即s=±s'。

若s=s'這與s,s'相異不合；若s=-s'，說(shuō)明s,s'不同屬于S，無(wú)論哪種情況都引出矛盾。所以 sa≠ sa'。

建立映射 φ: s→sa，這是s到它本身之上的一一映射。

因?yàn)閷?duì)任意的s∈S，由a ∈ Zp*則a有逆元a-1。所以sa-1∈Zp*，令

于是

且使得

說(shuō)明φ是一個(gè)滿射。對(duì)于 s,s '∈ s, s ≠ s'，則sa≠ s'a，即φ是單射。

將各等式 as= es（a ）sa相乘，得到

作為這個(gè)引理的應(yīng)用，我們證明 Legendre符號(hào)的一個(gè)性質(zhì)。

其中 n（ p）是滿足

的整數(shù)s的個(gè)數(shù)。

如果p有形式4k+1（或4k+3）則 n（ p）= k（或 k+1），由此可知，

在證明二次互反律之前，還需要建立一個(gè)三角恒等式。

引理2 設(shè)m為奇自然數(shù)m=2k+1，則有次多項(xiàng)式。對(duì)奇數(shù)m應(yīng)用歸納法：

（1）當(dāng)m=1時(shí)

是 sin2x 的0次多項(xiàng)式，故當(dāng)m=1時(shí)等式成立。當(dāng)m=3時(shí)

是 sin2x 的一次多項(xiàng)式，故當(dāng)m=3時(shí)等式成立。

（2）假設(shè)結(jié)論對(duì)不大于2k-1的奇自然數(shù)集來(lái)說(shuō)成立，當(dāng)m=2k+1時(shí)，由

及歸納假設(shè)知

即結(jié)論對(duì)任意的奇自然數(shù)k成立。

次多項(xiàng)式，令

個(gè)互異的零點(diǎn)。由廣義余式定理就有

下面求a。

由歐拉公式

由此可以看出（）eim-1x的系數(shù)為1，而

故右邊（）eim-1x的系數(shù)為

比較兩邊的系數(shù)知

有了以上的定義性質(zhì)及其引理，下面證明本文的中心定理——Gauss二次互反律：設(shè) p 和 q是兩個(gè)不同的素?cái)?shù)，則有

由等式qs=e（）sqsq ，有

將等式相乘，并考慮到 s→ sq是s上的一一映射，便得到

對(duì)于m=q，根據(jù)引理3可知：

由p和q的對(duì)稱性，交換p和q的位置，得到

所以

Gauss二次互反律告訴我們：

兩個(gè)奇素?cái)?shù)p、q只要有一個(gè)是4k+1的形式時(shí)，就有：

當(dāng)且僅當(dāng)p、q都是4k+3的形式時(shí)，才有

2 Legendre符號(hào)的計(jì)算

勒讓德符號(hào)有許多有用的性質(zhì)，可以用來(lái)加速計(jì)算。Legendre符號(hào)的一個(gè)推廣是Jacobi符號(hào)。以下在計(jì)算上將兩者進(jìn)行了比較。

定義（Jacobi符號(hào)） 設(shè)奇數(shù)P＞1， P =p1p2…pk，其中 pi（1≤ i≤ k） 是素?cái)?shù)，定義

其中

是模pj的Legendre符號(hào)，則稱

為Jacobi符號(hào)。

定理1 對(duì)于Jacobi符號(hào)，我們有

顯然，當(dāng)P本身是素?cái)?shù)時(shí)，Jacobi符號(hào)就是 Legendre符號(hào)。對(duì)于Jacobi符號(hào)，以下的互反律成立：

定理2 設(shè)奇數(shù)P＞1，奇數(shù)Q＞1，且（P, Q ）=1，有

用Legendre符號(hào)，Jacobi符號(hào)的求值有：

（1） 計(jì)算Jacobi符號(hào)并不需要求出素因數(shù)分解式例如，計(jì)算若用Legendre符號(hào)，則為：

而用Jacobi符號(hào)，計(jì)算方法為：

顯然，用Jacobi符號(hào)比僅使用Legendre符號(hào)簡(jiǎn)便。

（2）Jacobi符號(hào)與Legendre符號(hào)的本質(zhì)區(qū)別Legendre符號(hào)中

時(shí)，二次同余方程 x2≡ d（mo d P）一定有解，而Jacobi符號(hào)中

并不能確定二次同余方程 x2≡ d（mo d P） 有解。

例如，取奇素?cái)?shù) p≡-1（mo d 4），再取 P= p2，我們有

但 x2≡-1 （mod P） 無(wú)解（因?yàn)?x2≡- 1（mo dp） 無(wú)解）

具體例子：當(dāng)p=3時(shí)， P= p2=9

但 x2≡- 1（mo d 9）無(wú)解（因?yàn)?x2≡-1 （mo d3）無(wú)解）

又例： P=3599= 59×61，Jacobi符號(hào)

但x2≡2（mod 3599）無(wú)解。