二次剩余

定义

$m$ 为正整数，若 $x^2\equiv a\left(\mod m\right),\left(a,m\right)=1$ 有解，则 $a$ 为 $m$ 的二次剩余，否则为二次非剩余

$p$ 为奇素数， $\left(a,p\right)=1$

$a$ 是模 $p$ 的平方剩余 $\Longleftrightarrow a^{\frac{p-1}{2}}\equiv1\left(\mod p\right)$
$a$ 是模 $p$ 的非平方剩余 $\Longleftrightarrow a^{\frac{p-1}{2}}\equiv-1\left(\mod p\right)$

推论:

$p$ 为奇素数， $\left(a_1,p\right)=1,\left(a_2,p\right)=1$ ，则 $a_1\cdot a_2$ 为模 $p$ 的平方非剩余 $\Longleftrightarrow a_1,a_2$ 同为模 $p$ 的平方剩余或平方非剩余
平方剩余与平方非剩余数量相等

最后更新于3年前

欧拉判别条件

p

为奇素数，

\left(a,p\right)=1

$a$ 是模 $p$ 的平方剩余 $\Longleftrightarrow a^{\frac{p-1}{2}}\equiv1\left(\mod p\right)$

$a$ 是模 $p$ 的非平方剩余 $\Longleftrightarrow a^{\frac{p-1}{2}}\equiv-1\left(\mod p\right)$

推论:

$p$ 为奇素数， $\left(a_1,p\right)=1,\left(a_2,p\right)=1$ ，则 $a_1\cdot a_2$ 为模 $p$ 的平方非剩余 $\Longleftrightarrow a_1,a_2$ 同为模 $p$ 的平方剩余或平方非剩余

平方剩余与平方非剩余数量相等