class="markdown_views prism-github-gist">

1.定义

设p是奇素数(大于2的素数），如果二次同余式 $x^2 = a(mod p), (a, p) = 1$ 有解，则称a为模p的平方剩余(一个数的平方模p的余数)，否则a称模p的平方非剩余。平方剩余和平方非剩余又称为二次剩余和二次非剩余。

1.1 举个例子

请求出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}} = -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 81equiv -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 81equiv -6 (mod 29)$ $7^8 equiv (-6)^2 equiv 36 equiv 7 (mod 29)$ 所以 $7^{14} = 7^8 imes 7^4 imes 7^2 equiv 1 (mod 29)$ 所以7是模29的平方剩余。