二次剩余的判定及应用

【摘 要】通过讨论形式如x2a（mod m）的同余式，引出二次剩余的概念，应用数论中常用的函数（勒让德符号和雅可比符号）去讨论二次同余式中m是单质数的情形和一般的情形，并利用其解二次同余式。

【关键词】二次剩余；二次同余式；勒让德符号；二次反转定律

Second remaining judgement and application

Lv Xiao-mei

【Abstract】Through the discussion form like x2a （mod m） congruence type， leads to second remaining concept， application of the general functions （theory， Legendre symbols and Jacobi symbols）to discuss the second congruence type in the number of elemental m is condition and the general situation， this paper briefly introduces solutions second congruence type equations.

【Key words】Second remaining；second congruence type equations；Legendre symbols；Second reverse law

引 言

数论是数学本科的基础课程之一，是学习数学的必修课程之一。数论问题的丰富性，多样性及解题所具有的高度技巧对培养灵活创新的思维品质，逻辑思维，发散思维能力，系统的掌握各种数学思维，都是必不可少的。本文针对数论中一般二次同余式的解法问题进行总结概括。为了找到更为简单，有效地解一般二次同余式的方法，主要通叙述定理和举例，总结说明了欧拉判别条件，勒让德符号在解一般二次同余式时的具体应用以及一般二次同余式的解和解数问题。

1. 一般二次同余式 二次同余式最基本的形式：

（1）x2a（mod m），（a，m）=1

二次剩余。

我们已经知道，解同余式（1）归结到m为素数的情形，因为m=2时，解同余式（1）变得极为容易，所以着重讨论m=p的情形，这里p是一个奇素数。

定义1 ：设m >1，若（1）有解，则a叫做模m的二次剩余；若无解，则a叫做模m的二次非剩余。

2. 单质数的二次剩余的判定

2.1 欧拉判别条件。

讨论p是单质数的二次剩余和二次非剩余，即讨论形如：

x2a（mod p），（a，p）=1

定理1（欧拉判别条件）且 （a，p）=1，则a是模p的二次剩余的充分与必要条件是：

ap-121（mod p） （2）

而a是模p的二次非剩余的充分与必要条件是：

ap-12-1（mod p）

且若a是模p的二次剩余，则（2）式恰有二解。

例1 利用定理1来判断：

（i）3是不是模17的二次剩余；

（ii） 7是不是模29的二次剩余。

解： 由3310（mod 17）， 3430-4（mod 17），38-1（mod 17）知，3是模17的二次非剩余。

由72 -9（mod 29）， 73-5（mod 29），76-4（mod 29）， 771（mod 29），7141（mod 29）知，7是模29的二次剩余。

2.2 勒让德符号。

欧拉判别条件是适用于p比较小时，很难实际运用，我们引入勒让德符号，再给出一个便于实际计算的方法。

定义2 ：勒让德符号 （ap）（读作a对p的勒让德符号）是一个对于给定的单质数p定义在一切整数a上的函数，它的值规定如下：

（ap）=1，a是模p的二次平方剩余；-1，a是模p的二次平方非剩余；0，p|a.

利用引进的勒让德符号，定理2可表述为勒让德符号的性质。

定理2 勒让德符号有以下性质：

a） （ap）=（a+dp）；

b） （ap）a（p-1）2（mod p）；

c） （ap）=（a1p）；

d） （a1a2…anp）=（a1p）（a2p）…（anp）；

e） 当pd时，（d2p）=1；

f） （1p）=1；（-1p）=（-1）（p-1）2；

g） （2p）=（-1）（p2-1）8.

例2 判断同余方程x2-1（mod 137） 是否有解。

解 因为137 是素数，可以计算勒让德符号如下：

（-1137）=（-1）137-12=1，所以方程有解。

例3 判断方程x25（mod 11） 有没有解。

解 由定理2，因为（511）511-12=555・545・321（mod 11），方程有解。

2.2.1 二次反转定律。

以下要对勒让德符号和二次剩余做进一步的研究。以下，总以p表示奇素数。

引理1 设（n，p）=1，对于整数k（1kp-12，以rk表示nk对模p的最小非负剩余。设在r1，r2，…rp-12中大于p2的有m个，则

（np）=（-1）m。

定理3 下面的结论成立：

（） （2p）=（-1）p2-18；

（） 若n是奇数，（n， p） = 1，则

（np）=（-1）∑li=1[nip]， 其中l=p-12 .

推论 设p是素数，则

（2p）=1，当p±1（mod 8），-1，当p±3（mod 8）。

定理4（二次互反律） 设p与q是不相同的两个素数，则

（qp）=（-1）p-12・q-12 （pq）。

例4 判断同余式x2438（mod 593）是否有解。

解 因为593是质数，且438=2・3・73，故

（438593）=（2593）（3593）（73593）

因为5931（mod 8），再次利用二次反转定律和前面的相关性质，有

（438593）=（5933）（59373）=（23）（973）=-1

故438是模593的二次非剩余，因而原同余式无解。

2.3 雅可比符号。

为避免计算勒让德符号 的标准分解式是带来的麻烦，引进雅可比符号。

定义3 雅可比符号（am）（读作a对m的雅可比符号）是一个对于给定的大于1的单整数m定义在一切整数a上的函数，它在a上的函数值是

（am）=（ap1）（ap2）……（apr）

其中m=p1p2…pr，pi是质数，（api）是a对pi的勒让德符号。

例5 m = 45 = 3・3・5，则

（245）=（23）（23）（25）=（25）=（-1）52-18=-1，

（2845）=（283）（283）（285）=（35）=（-1）3-12・5-12（53）=（23）=-1。

注1：当m是奇素数时，雅可比符号就是勒让德符号。前者是后者的推广。

注2：如果m是奇素数，当 （am）= 1时，方程（1）有解。当m不是奇素数时，这个结论不一定成立。例如，方程x25（mod 9）无解，但是

（59）=（53）（53）= 1。

尽管如此，利用雅可比符号仍可对方程（5）的无解性给出判断。事实上，如果方程（1）有解，m = p1p…pk，则对于每个pi（1ik），当p = pi时方程（1）有解，因此，由雅可比符号的定义可知 （am）= 1。这样，若 （am）= -1，则方程（1）必无解。

下面，我们研究雅可比符号的计算方法。

定理5 使用定义1中的符号，下面的结论成立：

（） 若aa1（mod m） ，则

（am）=（a1m）；

（） （1m）= 1；

（） 对于任意的整数a1a2…at，有

（a1a2…atm）=（a1m）（a2m）…（atm）； （20）

（） 对于任意的整数a、b ，（a，m）=1，有

（a2bm）=（bm）。

例6 已知3371是素数，判断方程x212345（mod 3371）是否有解。

解 利用雅可比符号的性质，有

（123453371） =（22323371） =（23371） （43371） （2793371）

=（-1）33712-18（-1）3371-12・279-12（23279）

=（23279）=（-1）279-12・23-12（27923）

=-（323）=-（-1）23-12・3-12（233）=-1。

因此，方程本题无解。

3. 合数模的二次同余式

对于（1）式，若m是合数，可把m写成分解式：m=2αp1α1p2α2…pnαn.因此，（1）有解的充分与必要条件是同余式组

x2 a（mod 2α），x2 a（mod piαi）=1，2，…，k （3）

有解，并且在有解的情况下，（1）的解数是（3）中各式解数的乘积，因此，首先讨论同余式

x2 a（mod pα），α>0，（a，p）=1 （4）

开始。

定理6 （4）有解的充分与必要条件是（ap）=1，并且在有解的情况下，（4）式的解数是2.

接下来讨论同余式

x2 a（mod 2α），α>0，（2，a）=1 （5）

的解。首先可以看出，当α=1 时，（5）永远有解，并且解数是1.因此只讨论α>1的情形。

定理7 设α>1则（5）有解的必要条件是

（i） 当α=2时，a=1（mod 4）；

（ii） 当α3时，a=1（mod 8）.

若上述条件成立，则（5）有解，并且当α=2时，解数是2；当α3时，解数是4.

例7 解x2 57（mod 64）

因为57 1（mod 8），故有四解，把x写成x=±（1+4t3） ，代入原同余式得到（1+4t3） 257（mod 16）。由此得t31（mod 2），故x=±（1+4（1+2t4）） =±（5+8t4） 是适合 x2 57（mod 16）的一切整数，再代入同余式得到（5+8t4）2 57（mod 32） 。由此得 t40（mod 2），故 x=±（5+8・2t5）=±（5+16t5）是适合 x2 57（mod 32）的一切整数。仿前由（5+16t5）257（mod 64）得到 t5=1（mod 2），故x=±（5+16（1+2t6））=±（21+36t6）是适合x2 57（mod 16）的一切整数解，因此：

x21，53，-21，-53（mod 64）

是所求的四个解。

结 论

二次剩余的判定问题等价于判断一般二次同余式 x2a（mod p），（a，p）=1是否有解的问题。而当p取不同的数时，解决问题的方法不同。本文针对不同情况，运用了不同的方法，从而更简便地得出判断结果。单质数的二次剩余判定可以利用欧拉判别条件，勒让德符号和二次反转定律，合数模的二次剩余也可以转化成单质数的二次剩余进行判定。

参考文献

[1] 祝龙. 关于Euler数问题的一个注记[J]. 安徽师范大学学报（自然科学版）， 2007

[2] 潘承桐. 初等数论（第二版）[M]. 北京大学出版社. 2003： 192

[3] 闵嗣鹤，严士健. 初等数论（第三版）[M].高等教育出版社. 2009： 88-118

[4] 柯召. 数论讲义[M] 高等教育出版社. 2005

[5] Neal Koblitz. 数论与密码学教程（第二版）[M]. 世界图书出版公司北京公司. 2008： 43

[6] 叶文洪. 关于二次剩余的一些结果[J]. 信阳师范学院学报（自然科学版）， 1986

[7] 武胜利. 二次剩余及其相关问题[J]. 宝鸡文理学院学报（自然科学版）， 1997

收稿日期：2013-03-14