求模7的二次剩余和非剩余

定义11.9 如果gcd（a，p）=1，m为正整数，且

x^m≡a（mod p）

若这个m次同余方程有解，则称a为模p的m次剩余；否则，称a为模p的m次非剩余。特别地，当m=2时，如果二次同余方程

x²≡a（mod p）有解，则称a为模p的平方剩余；否则称a为模p的非平方剩余。模n的平方剩余的集合记为QR_n，平方非剩余的集合记为QNR_n。

【例11-26】 求出p=7时，二次同余方程

x²≡a（mod 7）的平方剩余和非平方剩余。

【解析】 因为

1²≡1（mod 7），2²≡4（mod 7）

3²≡2（mod 7），4²≡2（mod 7）

5²≡4（mod 7），6²≡1（mod 7）

所以1，2，4是模7的平方剩余，而3，5，6是模7的非平方剩余。

定理11.14 若p是奇素数，a是模p的平方剩余，则

x²≡a（mod p）有两个解，分别为x和-x。

定理11.15 奇素数模p的剩余类{1，2，…，p-1}中，有

（p-1）/2

个是p的平方剩余，它们分别与

1²，2²，3²，…，[（p-1）/2]²

同理，其他的（p-1）/2个是p的平方非剩余。

【例11-27】 求出p=11时，二次同余方程(www.xing528.com)

x²≡a（mod 11）的平方剩余和非平方剩余。

【解析】 由

1²≡1（mod 11），2²≡4（mod 11）

3²≡9（mod 11），4²≡5（mod 11）

5²≡3（mod 11）可知，1，3，4，5，9是模11的平方剩余，而2，6，7，8，10是模11的非平方剩余。

定理11.16 （欧拉判别法则）设p为奇素数，gcd（a，p）=1，则a是模p的平方剩余的充要条件是

a是模p的平方非剩余的充要条件是

【例11-28】 判断3是不是模17的平方剩余，判断7是不是模29的平方剩余。

【解析】 因为

所以3是模17的非平方剩余。

因为

所以7是模29的平方剩余。

一个一般的一元二次同余方程ax²+bx+c≡0（mod m）（a关于模m不与0同余），总可以将之化为“x²≡a（mod m）”的形式。

如将方程两边同乘以4a，得

4a²x²+4abx+4ac≡0（mod m），

两边再加上b²，有

令2ax+b=y，b²-4ac=d，可得到

y²≡d（mod m）