单质数模的平方剩余与平方非剩余(共6页).doc

精选优质文档-倾情为你奉上2 奇质数模的平方剩余与平方非剩余本节考虑同余式 （1）的解。定理1 若则是模的平方剩余的充分必要条件是 （2）而是模的平方非剩余的充分必要条件是 （3）且若是模的平方剩余，则同余式（1）恰有二解。证 （）因，故存在整系数多项式使得故 （4）若是模的平方剩余，则存在整数使得 （5）易得 在（4）式中令得 （6）由（5），（6）两式及费马定理得但故（2）式成立。因除的余式的每一系数都是的倍数，故同余式（1）恰有二解。反之，若（2）式成立，则由第四 4定理5得是模的平方剩余。（） 由费马定理，若，则因为奇质数，故（2），（3）两式中必有一个成立，且只能有一个成立。于是由（）可得，是模的平方非剩