Legendre符号及Gauss二次互反律的证明

郭向荣

（唐山师范学院 数学与信息科学系，河北 唐山 063000）

Legendre符号是由法国数学家阿德里安-马里·勒让德在1798年尝试证明二次互反律时引入的函数。这个符号是许多高次剩余符号的原型，它的延伸和推广包括雅可比符号、克罗内克符号、希尔伯特符号，以及阿廷符号。二次互反律被誉为“算术中的宝石”，特别是在同余理论里，二次互反律是一个用于判别二次剩余，即二次同余方程 x2≡p(modq）之整数解的存在性的定律。Legendre曾经提出过二次互反律的猜想。但第一个严格的证明是由 Gauss在 1796年作出的，随后他又发现了另外七个不同的证明。Gauss之后Kummer、Eisenstein、Hilbert、Artin、Furtwangler等也相继给出了新的证明。至今，二次互反律已有超过200个不同的证明。本文利用有限域的一些知识，给出这个定理的一个证明。Jacobi符号是Legendre符号的一种推广，允许底数为合数，但底数仍然必须是奇数和正数。这个推广提供了计算所有勒让德符号的一个有效的方法。本文将 Legendre符号与Jacobi符号在计算上进行了比较和总结。

1 Legendre符号定义及其基本性质

设Zp表示模p的剩余类环，当p为素数时，Zp形成域，其中仅含p个元素，令 Zp*=Zp-{0}，则 Zp*对 Zp的乘法形成一个p-1阶的循环群，本文总假定p为素数。

定义1 设p为素数，a ∈ Zp*若 xn≡ a(mod p)（这里n为大于1的整数）于Zp里有解，则称a叫做模Zp*的n次方元。否则a就称为Zp*的非n次方元。

定理 （1）如果p=2，则Zp*中每个元素都是平方元素。（2）如果p≠2则Zp*的平方元素形成Zp*的指数为2的不变子群。

由此定理得到，所有Zp*平方元素作成一个Zp*的子群，并且是Zp*的阶循环子群。

从而将

扩充到Zp的全部元素上，并且对于x∈Zp，若x有象元素x'∈ Zp ，则记作

性质1 若p/| mn ，则

为一积性函数。

性质2 （1）两个平方元素之积仍为平方元素。

（2）两个非平方元素之积仍为平方元素。

（3）一个平方元素与一非平方元素之积为一非平方元素。

性质3 p＞2，则

换言之，若 p≡1（mo d u）则-1为 Zp的平方元素，若p≡3（mo d u）则-1为Zp的非平方元素。

设p为奇素数，S为Zp*的子集，Zp*为S与-S的并集，取

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

证明 若s与s'是S的两个相异元素，则有 sa± sa'，否则 sa= sa'，即有 as=± as'，即s=±s'。

若s=s'这与s,s'相异不合；若s=-s'，说明s,s'不同属于S，无论哪种情况都引出矛盾。所以 sa≠ sa'。

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

因为对任意的s∈S，由a ∈ Zp*则a有逆元a-1。所以sa-1∈Zp*，令

于是

且使得

说明φ是一个满射。对于 s,s '∈ s, s ≠ s'，则sa≠ s'a，即φ是单射。

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

作为这个引理的应用，我们证明 Legendre符号的一个性质。

其中 n（ p）是满足

的整数s的个数。

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

在证明二次互反律之前，还需要建立一个三角恒等式。

引理2 设m为奇自然数m=2k+1，则有次多项式。对奇数m应用归纳法：

（1）当m=1时

是 sin2x 的0次多项式，故当m=1时等式成立。当m=3时

是 sin2x 的一次多项式，故当m=3时等式成立。

（2）假设结论对不大于2k-1的奇自然数集来说成立，当m=2k+1时，由

及归纳假设知

即结论对任意的奇自然数k成立。

次多项式，令

个互异的零点。由广义余式定理就有

下面求a。

由欧拉公式

由此可以看出（）eim-1x的系数为1，而

故右边（）eim-1x的系数为

比较两边的系数知

有了以上的定义性质及其引理，下面证明本文的中心定理——Gauss二次互反律：设 p 和 q是两个不同的素数，则有

由等式qs=e（）sqsq ，有

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

对于m=q，根据引理3可知：

由p和q的对称性，交换p和q的位置，得到

所以

Gauss二次互反律告诉我们：

两个奇素数p、q只要有一个是4k+1的形式时，就有：

当且仅当p、q都是4k+3的形式时，才有

2 Legendre符号的计算

勒让德符号有许多有用的性质，可以用来加速计算。Legendre符号的一个推广是Jacobi符号。以下在计算上将两者进行了比较。

定义（Jacobi符号） 设奇数P＞1， P =p1p2…pk，其中 pi（1≤ i≤ k） 是素数，定义

其中

是模pj的Legendre符号，则称

为Jacobi符号。

定理1 对于Jacobi符号，我们有

显然，当P本身是素数时，Jacobi符号就是 Legendre符号。对于Jacobi符号，以下的互反律成立：

定理2 设奇数P＞1，奇数Q＞1，且（P, Q ）=1，有

用Legendre符号，Jacobi符号的求值有：

（1） 计算Jacobi符号并不需要求出素因数分解式例如，计算若用Legendre符号，则为：

而用Jacobi符号，计算方法为：

显然，用Jacobi符号比仅使用Legendre符号简便。

（2）Jacobi符号与Legendre符号的本质区别Legendre符号中

时，二次同余方程 x2≡ d（mo d P）一定有解，而Jacobi符号中

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

例如，取奇素数 p≡-1（mo d 4），再取 P= p2，我们有

但 x2≡-1 （mod P） 无解（因为 x2≡- 1（mo dp） 无解）

具体例子：当p=3时， P= p2=9

但 x2≡- 1（mo d 9）无解（因为 x2≡-1 （mo d3）无解）

又例： P=3599= 59×61，Jacobi符号

但x2≡2（mod 3599）无解。