二次同余式与平方剩余VIP专享VIP免费

本章的目的是较深入地讨论1.一般二次了解一般二次及：教学过程:本节主要讨论2.单质数的了解单质数的：教学过程:这节我们讨论单质数p的)(mod121pap：而)(mod121pap单质数p的使的)(mod),(mod222121parpar于是有)(mod)(21221paarr这说明一般二次同余式在第四章中，我们讨论了高次同余式的解的一般理论，但在实际中，要解一个高次同余式一般比较困难。在本章我们重点讨论二次同余式的解法。思路是先把一般二次同余式化为特殊的二次同余式，再引入平方剩余与平方非剩余，并利用勒让得符号来判断特殊二次同余式是否有解。二次同余式的一般形式二次同余式的一般形式是，0（）（1）化一般二次同余式为特殊二次同余式由高次同余式的理论知，若的标准分解式为，则（1）有解的充要条件是下面同余式组中每个同余式有解。于是要判别（1）是否有解及如何解（1），我们可重点讨论为质数。（2）下面对（2）分情况进行讨论。找到（2）有解的判别法。由于（2）为二次同余式，故可假定，若有但(,,)，则（2）化为。而。故还可假定(,,)。1)|，|。则。因而同余式无解。故（2）设有解。2)|，。则无解，故（2）有解的充要条件是有解，即有解。但（，）＝1。故有解，从而（2）有解，且（2）的解可由的解求出。3)，>2。则。用4乘（2）后再配方，即得（3）易证（2）和（3）等价。用代2＋得（4）则（2）有解的充要条件是（4）有解，于是将（2）化为（4）讨论。4)，＝2。这时为奇。（i）若2，则无解。故（2）有解的充要条件是有解。因对任何整数恒有。所以（2）有解的充要条件是有解，即2|。（ii）若2|，令。由知（2）有解的充要条件是有解。即(5)有解。作代换＝＋，则（2）有解的充要条件是有解。由上面讨论，可将（2）的问题化为二次同余式或一般情况即(6)平方剩余和非平方剩余定义若同余式（6）有解，则叫模的平方剩余，若同余式（6）无解，则叫模的平方非剩余。由这一定义，要判断（6）是否有解，就是判断是否为模的平方剩余，下面几节就讨论为模的平方剩余及平方非剩余的判别。单质数的平方剩余和平方非剩余在这一节里我们只讨论单质数的平方剩余和平方非剩余，即讨论形如（1）的同余式的解。定理1（欧拉判别条件）若（，）＝1，则是模的平方剩余的充分与必要条件是（2）而是模的平方非剩余的充分与必要条件是（3）且若是模的平方剩余，则（1）式恰有两个解。证（i）因为能整除，即有一整系数多项式（）使，故若是平方剩余，则（2）成立。因而由质数模高次同余式解的个数的结果知有二解。反之，若（2）成立，则是模的平方剩余。（ii）由费尔马定理知，若（，）＝1，则。因此。由于是单质数，故（2），（3）有一且仅有一成立。但由（i）知是平方剩余的充要条件是。故是平方非剩余的充要条件是（3）。定理（2）模的简化剩余系中平方剩余和非平方剩余的个数各为。而且个平方剩余分别与序列（4）中之一数同余，且仅与一数同余。证由定理1知平方剩余的个数等于同余式的解数。但能整除。故由质数模高次同余式解数的结果知，平方剩余的个数是，而平方非剩余的个数是。下面证定理的第二部分：显然（4）中的数均是平方剩余，且互不同余，因若，则有四个解，这与定理1矛盾。故由定理前一部分结论即知成立。例求出模11的平方剩余和平方非剩余。解：＝11为单质数。由定理2，对模11共有5个平方剩余，5个平方非剩余。其5个平方剩余与下列5个数对模11一对一地同余:故5个平方剩余为1，4，9，5，3而5个平方非剩余为：2，6，7，8，10由此即知同余式，有解，且有两个解。而同余式无解。勒让得符号在上一节给出了欧拉判别条件判别平方剩余与平方非剩余，但当比较大时，计算很困难。当然由上节定理2，从理论上讲，对一些给定的，我们可以构造出平方剩余表，要判别一个同余式是否有解，只须查一下表即可。但单质数太多，无法也不可能对每个单质数构造一张表。故在本节我们引入勒让得符号，给出一个便于实际计算的判别方法。勒让得符号的定义勒让得符号(读作对的勒让得符号)是一个对于给定的单质数定义在一切整数上的函数，它的值规定如下：由勒让得符号的定义可以看出，如果能够很快地计算出它的值，那么就会立刻知道同余式有解与...