奇素数模的二次剩余-初等数论基础

为研究二次二项同余方程，需要引入重要的二次剩余的概念.

定义6.2.1　设m为大于1的整数，a∈Z且（a，m）=1.若x2≡a（modm）有解，则称a为模m的二次剩余，否则称其为模m的二次非剩余.

注6.2.2　显然，若a≡b（modm），则a是模m的二次剩余当且仅当b是模m的二次剩余.这说明要找模m的二次剩余只要在模m的一个简化剩余系中找即可.另外，据上述概念，全体与m互素的整数分为两类：二次剩余和二次非剩余.例如，1，2，4均为模7的二次剩余，而3，5，6是模7的二次非剩余.又，1是模4的二次剩余，而3是模4的二次非剩余.

本节以下主要讨论奇素数模的二次剩余.下面的定理给出了奇素数模的二次剩余的个数及其分布特点.

定理6.2.3　设p是奇素数.则模p的简化剩余系中二次剩余与二次非剩余的个数各为其中的个二次剩余分别与序列12，22，…，中的一个数对模p同余且仅与其中的一个数对模p同余.

证明　显然，12，22，…，中诸数均与p互素.下证它们两两对模p不同余.事实上，若1≤j＜i≤且i2≡j2（modp），则p|i2-j2=（i+j）（ij）.由p是素数知p|i+j或p|i-j.但这是不可能的，因为0＜i-j＜i+j＜p-1.由上述论证，可补充个整数使得

构成模p的简化剩余系.下证诸ai均不是模p的二次剩余.若不然，则存在xi∈Z使得≡ai（modp）.显然于是可设xi=qp+r，0＜r＜p.故

由于r及p-r中必有一个属于，从而ai必与中之一同余，这与（6.2.1）是简化剩余系矛盾.这表明在简化剩余系（6.2.1）中，二次剩余与二次非剩余的个数各为据注6.2.2，定理的结论对任何简化剩余系都成立.证毕.

例6.2.4　在最小正简化剩余系中找出模17的二次剩余与二次非剩余.

解　据定理6.2.3，12，22，…，82被17除的余数1，2，4，8，9，13，15，16就是模17在其最小正简化剩余系中的二次剩余，而3，5，6，7，10，11，12，14就是模17在其最小正简化剩余系中的二次非剩余.解毕.

如何判断一个与奇素数p互素的整数是模p的二次剩余还是二次非剩余是要解决的首要问题.下面的定理给出了一种回答.(www.xing528.com)

定理6.2.5（欧拉判别准则）　设p是奇素数，a∈Z且（a，p）=1.则a是模p的二次剩余当且仅当），a是模p的二次非剩余当且仅当≡-1（modp）.当a是模p的二次剩余时，x2≡a（modp）恰有两解.

证明　设a是模p的二次剩余，则存在x0∈Z使得≡a（modp）.由p是奇素数知是正整数.由（a，p）=1及≡a（modp）知（x0，p）=1.据欧拉定理，有

反之，设≡1（modp）.则据命题1.1.4，有

记=（x2-a）u（x）.则

这表明x2-a除xp-x的余式为据事实及定理5.4.8便知x2≡a（modp）有两个解.

另一方面，由欧拉定理及（a，p）=1知ap-1≡1（modp）.于是

由p是素数知下列同余式之一成立：

但这二者不能同时成立.否则，有1≡-1（modp），进而有p|2，这与p是奇素数矛盾.这表明有且仅有一款成立，结合本定理的前一部分便知定理的后一部分也成立.证毕.

例6.2.6　用欧拉判别准则证明1，2，4均为模7的二次剩余，而3，5，6是模7的二次非剩余.

证明　由13≡23≡43≡1（mod7），33≡53≡63≡-1（mod7）立得结论.证毕.