文档介绍：. .
- 优选
§2奇质数模的平方剩余与平方非剩余
本节考虑同余式
（1）
的解。
定理1 若则是模的平方剩余的充分必要条件是
（2）
而是模的平方非剩余的充分必要条件是
（3）
且若是模的平方剩余，则同余式（1）恰有二解。
证 （ⅰ）因，故存在整系数多项式使得
故
（4）
若是模的平方剩余，则存在整数使得
（5）
易得
在（4）式中令得
（6）
由（5），（6）两式及费马定理得但故（2）式成立。因除的余式的每一系数都是的倍数，故同余式（1）恰有二解。
反之，若（2）式成立，则由第四 §4定理5得是模的平方剩余。
. .
- 优选
（ⅱ） 由费马定理，若，则
因为奇质数，故（2），（3）两式中必有一个成立，且只能有一个成立。于是由（ⅰ）可得，是模的平方非剩余
定理2 模的简化剩余系中，平方剩余与平方非剩余的个数各为，而且个平方剩余分别与系列
（6）
中一数同余且仅与一数同余。
证 由定理1得，在模的简化剩余系中，平方剩余的个数等于同余式
的解数。因
故该同余式的解数为，故平方剩余的个数为，而非平方剩余的个数为
下证定理的第二部分。易知（6）中的每一个数都是模的平方剩余，且对模两两部同余。因为若则但矛盾。由定理的第一部分即知，定理的第二部分成立。
. .
-