第5章二次同余式与平方剩余.doc

初等数论教案第五章 二次同余式与平方剩余本章的目的是较深入地讨论二次同余式。讨论方法是把问题归结到讨论形如的同余式，进而引入平方剩余和平方非剩余的概念，再应用数论中常用的函数(勒让德符号及雅可比符号)去讨论m是单质数的情形，进而讨论一般的情形。最后还应用本章结果解决两个不定方程的问题，并介绍一下与它们有关的著名的华林问题。教学内容:1.一般二次同余式教学目的: 了解一般二次同余式及平方剩余，平方非剩余的概念：教学重难点: 平方剩余的概念教学过程:本节主要讨论二次同余式，讨论方法是把问题归结到讨论形如的同余式，进而引入平方剩余和平方非剩余的概念，再应用数论中常用的函数讨论m是单质数的情形，进而讨论一般的情形：一 基本概念：首先：二次同余式的一般形式：（1）用4a乘（1）式再加上得：若令则上式变为（2）具体分析过程见书上P74:由同于是的性质可知（2）与（1）式同时有解或同时误解：故讨论（1）式有解的问题可以转为讨论（2）式有解的问题：为了讨论（2）式是否有解，我们引入平方剩余和平方非剩余的概念：定义：假设（a,m）=1，如果同余式有解，则a叫做模m的平方剩余，否则叫做模m的平方非剩余：例：根据同余式解的形式：他的接有0，1，2，3，4，5，6这7中可能，而a有1，2，3，4，5，6这六种可能，严整可知当a取1，2，4是有解，当a取3，5，6时误解，故1，2，4为模7的平方剩余，而3，5，6为模7的平方非剩余：教学内容:2.单质数的平方剩余与平方非剩余教学目的: 了解单质数的平方剩余，平方非剩余的基本性质及判别方法：教学重难点: 平方剩余，平方非剩余的判别教学过程: 这节我们讨论单质数p的平方剩余，平方非剩余：一 判别方法：定理1：（欧拉判别条件）：若（a,p）=1，则a是模p的平方剩余的充要条件是：而a是模p的平方非剩余的充要条件是：证明：见书上P76：由此定理我们就可以判别单质数p的平方剩余，平方非剩余：二基本性质：定理2：模p的平方剩余和平方非剩余各为，而且个平方剩余分别与序列中之一数同余，且仅与一数同余：证明：见书上P77：关于平方剩余和平方非剩余具有以下性质：定理3：对于同一素数p来说：1 二平方剩余之积仍是平方剩余：2 一平方剩余与一平方非剩余之积为平方非剩余：3 二平方非剩余之积为平方剩余：证明：1。设均为模p的平方剩余，即有两数使的于是有这说明是模p的平方剩余：故证。2设a为模p的平方剩余，故有(a,p)=1，由于1，2，p-1是模p的简化剩余系，故a,2a,(p-1)a也是模p的简化剩余系，而1，2，p-1中有个数为平方剩余，故a与这个平方剩余之积仍是平方剩余，因而，在a,2a,(p-1)a中除去这些平方剩余后，剩下全为平方非剩余，即一平方剩余与一平方非剩余之积为平方非剩余：3设b为模p的平方非剩余，则简化剩余系b,2b,(p-1)b 中，个平方非剩余是b与平方剩余之积，而个平方剩余是平方非剩余b与平方非剩余之积,所以，二平方非剩余之积为平方剩余：一般二次同余式在第四章中，我们讨论了高次同余式的解的一般理论，但在实际中，要解一个高次同余式一般比较困难。在本章我们重点讨论二次同余式的解法。思路是先把一般二次同余式化为特殊的二次同余式，再引入平方剩余与平方非剩余，并利用勒让得符号来判断特殊二次同余式是否有解。二次同余式的一般形式二次同余式的一般形式是，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，从理论上讲，对一些给定的，我们可以构造出平方剩余表，要判别一个同余式是否有解，只须查一下表即可。但单质数太多，无法也不可能对每个单质数构造一张表。故在本节我们引入勒让得符号，给出一个便于实际计算的判别方法。勒让得符号的定义勒让得符号(读作对的勒让得符号)是一个对于给定的单质数定义在一切整数上的函数，它的值规定如下： 由勒让得符号的定义可以看出，如果能够很快地计算出它的值，那么就会立刻知道同余式有解与否，下面通过讨论勒让得符号的性质给出计算勒让得符号的值的方法。勒让得符号的性质性质1 证由定义及欧拉判别法即得。性质2 ，其中证 由性质1可得前两式，由定义可得第三式。性质3 。证由性质1，由定义。又2，故得性质3。由性质3及定义立即可得性质4，。性质5；若（，）1，2，则，其中。由性质5可得推论当时，2是平方剩余；当时，2是平方非剩余。性质6（二次反转定理）若及 都是单质数，（，）1，则。注性质5和性质6的证明比较复杂，不要求大家掌握，只须会使用即可，有兴趣的同学可参看教材上给的证明。利用性质1到性质6，我们可比较容易地计算出勒让得符号的值。从而判别同余式是否有解。勒让得符号的应用下面通过一个例题说明勒让得符号的应用 例判断同余式是否有解。解因563为单质数，只须计算。因为28621113所以由性质3得 。由性质5得由性质6及性质2与性质4得同理由前面性质得故，因而原同余式无解。合数模的情况在前几节我们讨论了单质数模的同余式有解的条件，在本节我们将讨论合数模同余式 （1）有解的条件及解的个数。由高次同余式理论，若的标准分解式为：则（1）有解的充要条件是同余式组（2）有解，并且在有解的情况下，（1）的解数是（2）中各式解数的乘积，下面就先讨论同余式这里为单质数。定理1（3）有解的充要条件是，且在有解的情况下，（3）式的解数是2。证若，则同余式无解，因而（3）式无解，故条件的必要性成立。若，则由欧拉判别法知恰有两个解。设是它的一个解，那么由（，）1即得，又因为2，故。若令，则。故由高次同余式理论知，由出发可得出（3）的一个唯一解。因此由两个解给出（3）的两个解，并且（3）仅有两个解。下面我们来讨论同余式 （4）的解。首先，当时，（4）永远有解，并且解数是1，下面我们只讨论的情形。定理2设，则（4）有解的充要条件是（i）当时，（ii）当时， 并且在（4）有解的情况下，若，则解数是2；若，则解数是4。证若是（4）的任一解，由（，2）1即得，因此,，其中是整数，由此即得。（i）当时，因此（ii）当时，则，又由于，故。所以条件的必要性成立。下证充分性。当时，由（i）成立得，显然这时都是（4）的解，且此时（4）仅有此二解。当时，由（ii）成立得，显然这时是（4）的仅有的四个解。当时，由于适合的一切整数可表成 （5）下面我们就从（5）中分出适合的一切整数。将（5）式代入得：，即亦即故，是适合的一切整数。同理适