二次剩余

定义

$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$的平方剩余或平方非剩余

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