作者：Chenglin_Yu
时间：2019年4月8日
来源：https://chenglinyu.blog.csdn.net/article/details/89081707
1.1 举个例子
1.定义
设p是奇素数(大于2的），如果二次同余式 x^2 = a(mod\ p), (a, p) = 1 有解，则称a为模p的平方剩余(一个数的平方模p的余数)，否则a称模p的平方非剩余。平方剩余和平方非剩余又称为二次剩余和二次非剩余。
请求出11的所有二次剩余。
在解决这个问题之前，首先我们要清楚11的一个剩余系为0,1，2，3，…,10。所以11的二次剩余只可能来源于这些数。为了决定哪些整数是11的二次剩余，我们计算整数1,2,3,…,10的平方(有同学可能就要问了，为什么只计算这10个数的平方呢？因为《初等数论及其应用》中的引理11.1提到了同余方程或者无解或者有两个模p不同于的解，所以我们只需要找这10个数就可以了，那有可能同学又要问了，怎么把0给漏掉了，因为(a,p) = 1,可以打消疑虑了吧。)，得到
1^2 \equiv 10^2 \equiv 1 (mod \ 11)
2^2 \equiv 9^2 \equiv 4 (mod \ 11)
3^2 \equiv 8^2 \equiv 9(mod\ 11)
4^2 \equiv 7^2 \equiv 5(mod \ 11)
5^2 \equiv 6^2 \equiv 3 (mod \ 11)
因此，11的二次剩余是1，3，4，5，9，二次非剩余是2,6,7,8,10.
2.平方剩余和平方非剩余的个数
设p是奇素数，在模p的简化剩余系中，有\frac {p-1}{2}个平方剩余，\frac {p-1}{2}个平方非剩余。
这个定理很有用：以后我们求模p的平方剩余时，就可以只计算下列数了
1^2, 2^2,…,(\frac {p-1} {2})^2 (mod\ p)3.欧拉判别法
欧拉判别法可以判断一个数是不是模p的平方剩余
设p是奇素数，(a,p) = 1。a是模p平方剩余的充分必要条件是
a^{\frac {p-1}{2}} \equiv 1 (mod \ p)a是模p的平方非剩余的充分必要条件是
a^{\frac {p-1}{2}} \equiv -1 (mod \ p)
3.1 例1
判断3是不是模17的平方剩余？
根据欧拉判别法，
a = 3, p = 17, 所以
\frac {p-1}{2} = 8
我们需要得到
3^8 \equiv 1(mod \ 17)
或者
3^8 \equiv -1(mod \ 17)
我们的计算方式是”从底层起”
因为
3^2 \equiv 9 (mod\ 17 )
所以
3^4 \equiv 81\equiv -4 (mod\ 17)
方程同时平方得
3^8 \equiv 16 (mod \ 17)\equiv -1 (mod \ 17)
所以3是模17的平方非剩余
3.2 例2
7是不是模29的平方剩余
\frac {p-1}{2} = 14
7^{14} 是我们的目标。老办法，从底层起
7^2 = 49 \equiv -9 (mod\ 29)
7^4 \equiv (-9)^2 \equiv 81\equiv -6 (mod 29)
7^8 \equiv (-6)^2 \equiv 36 \equiv 7 (mod \ 29)
所以
7^{14} = 7^8 \times 7^4\times 7^2 \equiv 1 (mod \ 29)
所以7是模29的平方剩余。