1、第三章 二次剩余第一节 二次剩余一、二次剩余的定义二、二次剩余的性质定义 3.1.1 设整数 a与正整数 m互素，若同余式 x2a(modm)有解，则称 a为 模 m的二次剩余；若同余式 x2a(modm)无解，则称 a为模 m的非二次剩余。例 3.1.1 确定哪些整数是模 10的二次剩余。解 ： 首先 由于对任意的整数 n，由带余数除法，存在唯一的整数 k与 n1，使得n=10k+n1，其中 0n110，则n2=100k2+20kn1+n12，于是n2n12(mod10)， 0n110，因而为了确定哪些整数是模 10的二次剩余，只需要关注整数 1， 2， 3， ， 9的平方。 一、二次剩余的
2、定义例 3.1.1 确定哪些整数是模 10的二次剩余。解 ： 首先 为了确定哪些整数是模 10的二次剩余，只需要关注整数 1， 2， 3， ， 9的平方。而12921 (mod 10)，22824 (mod 10)，32729 (mod 10)，42626 (mod 10)，525 (mod 10)，同时，由于在整数 1， 4， 5， 6， 9中与 10互素的整数只有 1和 9，因而只有 1和 9是模 10的二次剩余，而整数 2， 3， 7， 8中与 10互素的整数只有 3和 7，因而只有 3和 7是模 10的二次非剩余。一、二次剩余的定义例 3.1.2确定哪些整数是模 11的二次剩余。解 ：
3、只需要关注整数 1， 2， 3， ， 10的平方。而121021 (mod 11)，22924 (mod 11)，32829 (mod 11)，42725 (mod 11)，52623 (mod 11)，同时由于整数 1， 2， 3， ， 10均与 11互素，因而整数 1， 3， 4， 5， 9是模 11的二次剩余，而整数 2， 6， 7， 8， 10是模 11的二次非剩余。 一、二次剩余的定义例 3.1.3确定哪些整数是模 13的二次剩余。解 ：类似于例 3.1.1的讨论，这里我们只需要关注整数 1， 2， 3， ， 12的平方。而121221 (mod 13)，221124 (mod 13
4、)，321029 (mod 13)，42923 (mod 13)，528212 (mod 13)，627210 (mod 13)，同时由于整数 1， 2， 3， ， 12均与 13互素，因而整数 1， 3， 4， 9， 10， 12是模 13的二次剩余，而整数 2， 5， 6， 7， 8， 11是模 13的二次非剩余。一、二次剩余的定义引理 3.1.1 设 p是奇素数， a是整数，且 pa，则同余式x2a (mod p)或者没有解或者恰有两个模 p不同余的解。证明 ：若同余式 x2a(mod p)有一个解 x=x0，则由于(-x0)2=x02a(mod p)，因而可以同时找到同余式的另一个解x
5、=-x0。用反证法来证明解 x=-x0与 x=x0不同余 ，假设x0-x0 (mod p)，即 2x00 (mod p)。此时由 x02a(modp)，得到p|(x02-a)，又 pa，因而 px0；又 p是奇数，进而p2x0，这与 2x00 (mod p)矛盾，二、二次剩余的性质引理 3.1.1 设 p是奇素数， a是整数，且 pa，则同余式 x2a (mod p)或者没有解或者恰有两个模 p不同余的解。证明 ： 接下来证明同余式 x2a(mod p)的解不多于两个。 假设x=x0与 x=x1都是同余式 x2a (mod p)的解，则x02x12a (mod p)，即x02-x12=(x0+
6、x1)(x0-x1)0 (mod p)。因而p|(x0+x1)或者 p|(x0-x1)，即x0x1 (mod p)或 x0-x1 (mod p)。综上，若同余式 x2a (mod p)有解，则恰有两个模 p不同余的解。 二、二次剩余的性质定理 3.1.1 若 p是奇素数，则在整数 1， 2， ， p-1中恰有 (p-1)/2个模 p的二次剩余， (p-1)/2个模 p的二次非剩余。证明 ： p-1个同余式x2a (mod p)， x=1, 2, , p-1，或者没有解或者恰有两个模 p不同余的解 xi与 p-xi， 0xip-1。即 1， 2， ， p-1能且仅能为 (p-1)/2个同余式提供解；即 1与 p-1， 2与 p-2， 3与 p-3， ， (p-1)/2与 (p+1)/2分别为 (p-1)/2个同余式的解，因而整数 1， 2， ， p-1中恰有 (p-1)/2个模 p的二次剩余，剩余的 p-1-(p-1)/2=(p-1)/2个小于 p-1的整数是模 p的二次非剩余。二、二次剩余的性质第二节 勒让德符号一、勒让德符号的定义二、 欧拉判别法三、高斯引理
