1、1二次剩余的判定及应用【摘 要】通过讨论形式如 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，
2、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 co
3、ngruence type equations；Legendre symbols；Second reverse law 引 言 数论是数学本科的基础课程之一，是学习数学的必修课程之一。数论问题的丰富性，多样性及解题所具有的高度技巧对培养灵活创新的思2维品质，逻辑思维，发散思维能力，系统的掌握各种数学思维，都是必不可少的。本文针对数论中一般二次同余式的解法问题进行总结概括。为了找到更为简单，有效地解一般二次同余式的方法，主要通叙述定理和举例，总结说明了欧拉判别条件，勒让德符号在解一般二次同余式时的具体应用以及一般二次同余式的解和解数问题。 1. 一般二次同余式 二次同余式最基本的形式： （1）x
4、2a（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
5、） 而 a 是模 p 的二次非剩余的充分与必要条件是： ap-12-1（mod p） 3且若 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 勒让德符号。 欧拉判别条
6、件是适用于 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） （a1a2anp）=（a1p） （a2p）（anp）
7、； e） 当 pd 时， （d2p）=1； 4f） （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
8、，对于整数 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=1nip， 其中 l=p-12 . 推论 设 p 是素数，则 （2p）=1，当 p1（mod 8） ，-1，当 p3（mod 8） 。 定理 4（二次互反律） 设 p 与 q 是不相同的两个素数，则 （qp）=（-1）p-12?q-12 （pq） 。 5例 4 判断同余式 x2438（mod
9、 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 上的函数值是 （a
10、m）=（ap1） （ap2）（apr） 其中 m=p1p2pr，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 不6是奇素数时，这个结论不一定成立。例如，方程 x25（mod 9）无解，但是 （59）=
11、（53） （53）= 1。 尽管如此，利用雅可比符号仍可对方程（5）的无解性给出判断。事实上，如果方程（1）有解，m = p1ppk，则对于每个 pi（1ik） ，当 p = pi 时方程（1）有解，因此，由雅可比符号的定义可知 （am）= 1。这样，若 （am）= -1，则方程（1）必无解。 下面，我们研究雅可比符号的计算方法。 定理 5 使用定义 1 中的符号，下面的结论成立： （?） 若 aa1（mod m） ，则 （am）=（a1m） ； （?） （1m）= 1； （?） 对于任意的整数 a1a2at，有 （a1a2atm）=（a1m） （a2m）（atm） ； （20） （?） 对于
12、任意的整数 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） 7=（23279）=（-1）279-12?23-12（27923） =-（323）=-（-1）23-12?3-12（233）=-1。 因此，方程本题无解。 3. 合数模的二次同余式 对于（1）式，若 m 是合数，可把 m 写成分解式
13、：m=2p11p22pnn.因此， （1）有解的充分与必要条件是同余式组 x2 a（mod 2） ，x2 a（mod pii）=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）有解的必
14、要条件是 （i） 当 =2 时，a=1（mod 4） ； （ii） 当 3 时，a=1（mod 8）. 若上述条件成立，则（5）有解，并且当 =2 时，解数是 2；当 3时，解数是 4. 8例 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+
15、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 取不同的数时，解决问题的方法不同。本文针对不同情况，运用了不同的方法，从而更简便地得出判断结果。单质数的二次剩余判定可以利用欧拉判别条件，勒让德符号和二
16、次反转定律，合数模的二次剩余也可以转化成单质数的二次剩余进行判定。参考文献 1 祝龙. 关于 Euler 数问题的一个注记 J. 安徽师范大学学报（自然科学版） ， 2007 2 潘承桐. 初等数论（第二版）M. 北京大学出版社. 2003： 9192 3 闵嗣鹤，严士健. 初等数论（第三版）M.高等教育出版社. 2009： 88-118 4 柯召. 数论讲义M 高等教育出版社. 2005 5 Neal Koblitz. 数论与密码学教程（第二版）M. 世界图书出版公司北京公司. 2008： 43 6 叶文洪. 关于二次剩余的一些结果J. 信阳师范学院学报（自然科学版） ， 1986 7 武胜利. 二次剩余及其相关问题J. 宝鸡文理学院学报（自然科学版） ， 1997 收稿日期：2013-03-14
