class="markdown_views prism-dracula">

前言

在有些时候，我们会需要求解这样的问题$x^2equiv apmod{p}$
给定$a$求是否有$x$满足这个式子，若有r则称a是模p的二次剩余
若没有满足条件的$x$，则称a是模p的非二次剩余
然而在一些题目中，我们既要判定它是否是模p的二次剩余，也要判断其值，本文就对此进行一些探究

对于所有模数

二次剩余数量

我们发现$a^2equiv (p-a)^2pmod p$
所以满足条件的二次剩余数量不可能超过$leftlfloorfrac n2 ight floor+1$

不同模数下的二次剩余

模数为偶质数

显然偶质数只有一个，那就是2
显然$0$和$1$都是$2$的二次剩余

模数为奇质数

对于判定模数为奇素数时的情况
我们定义勒让德符号：
$left(frac ap ight)=egin{cases}+1&如果a otequiv0pmod p且有整数x满足x^2equiv apmod p\ -1&如果没有整数x满足x^2equiv apmod p\ 0&如果aequiv0pmod p end{cases}$ 我们先引入欧拉准则
这是一个用来判定的经典准则（其实勒让德符号的定义准确来说就是从这里定义的）
这里规定，当模数为奇素数的时候···（此处省略解释）
直接代入勒让德符号成为
$left(frac ap ight)=a^{frac{p-1}2}pmod p$

---

• 口糊一下证明
  由于模数是奇素数，所以我们就可以使用拉格朗日定理（$k$次多项式至多$k$个根）
  所以对于任意一个$a$，满足$x^2equiv apmod p$的$x$数量至多为$2$
  现在我们把$a=0$的情况扔掉，因为$a=0$显然满足上式
  只考虑$a eq0$的情况
  首先我们有费马小定理$a^{p-1}equiv1pmod p$
  由于$p$是奇数，我们开始推式子
  移项得
  $a^{p-1}-1equiv0pmod p$
  因式分解得
  $(a^{frac{p-1}2}-1)(a^{frac{p-1}2}+1)equiv0pmod p$
  我们发现，如果有$x$满足$x^2equiv apmod p$，那么根据费马小定理$x^{p-1}equiv1pmod p$
  将$x$用$a$代替
  $a^{frac{p-1}2}equiv1pmod p$
  如果没有满足条件的$x$，这说明
  $a^{frac{p-1}2} otequiv1pmod p$
  则根据上面的方程，两项中至少有一项为$0$
  则$a^{frac{p-1}2}equiv-1pmod p$
  证毕

---

现在我们已经会如何判定了，然而OI中更多的是要求这个值（大雾）
假设我们现在已经判定完了，发现$a$是模$p$的二次剩余
我们现在要求$x^2equiv apmod p$
移项得$a^{-1}x^2equiv 1pmod p$
设$x_i$