-1是模p平方剩余吗? 2呢

通过前一章的讨论，我们清楚了对于任何一个素数，[1,p−1]" role="presentation">[1,p−1]$[1,p-1]$有一半是二次剩余，以及哪些数字是二次剩余，哪些不是。 现在我们考虑对于一个数a" role="presentation">a$a$，看看对于哪些p" role="presentation">p$p$，这个数是QR" role="presentation">QR$QR$ 先考虑这样一个问题，对于哪些素数p" role="presentation">p$p$，同余式x2≡−1 (mod p)" role="presentation">x2≡−1 (mod p)$x^2\equiv -1(modp)$有解。或者说，对哪些素数，(−1p)=1" role="presentation">(−1p)=1$\left(\frac{-1}{p}\right)=1$ 同样，通过列出小的数据，可以看出： 若p" role="presentation">p$p$与1模4同余，则−1" role="presentation">−1$-1$似乎是p" role="presentation">p$p$的QR" role="presentation">QR$QR$；若p" role="presentation">p$p$与3模4同余，则−1" role="presentation">−1$-1$似乎是二次非剩余。 用来证明这个猜想的工具称为“费马小定理的平方根”， 即A=ap−12 mod p" role="presentation">A=ap−12 mod p$A=a^{\frac{p-1}{2}}modp$值为多少？ 显然A2≡1 mod p" role="presentation">A2≡1 mod p$A^2\equiv 1modp$ 因此p" role="presentation">p$p$整除(A−1)(A+1)" role="presentation">(A−1)(A+1)$(A-1)(A+1)$ 从而p" role="presentation">p$p$要么整除(A−1)" role="presentation">(A−1)$(A-1)$要么整除(A+1)" role="presentation">(A+1)$(A+1)$ 因此A" role="presentation">A$A$要么和1" role="presentation">1$1$模p" role="presentation">p$p$同余，要么和−1" role="presentation">−1$-1$ 一个结论是，对于一个p" role="presentation">p$p$，若a" role="presentation">a$a$是二次剩余，则A≡1 (mod p)" role="presentation">A≡1 (mod p)$A\equiv 1(modp)$； 若a" role="presentation">a$a$不是二次剩余，则A≡−1 (mod p)" role="presentation">A≡−1 (mod p)$A\equiv -1(modp)$ 即下面的欧拉准则 欧拉准则： 设p" role="presentation">p$p$为素数，则
ap−12≡(ap)mod p" role="presentation">ap−12≡(ap)mod p$$a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)modp$$
证明 当a" role="presentation">a$a$是QR" role="presentation">QR$QR$时，则a≡g2k (mod p)" role="presentation">a≡g2k (mod p)$a\equiv g^{2k}(modp)$ ，则ap−12≡(gp−1)k≡1 (mod p)" role="presentation">ap−12≡(