二次剩余+欧拉准则

二次剩余

p 是素数，a不是p的倍数且与一个平方数模p同余，则称a是模p的二次剩余，记作 $a \in QR$
即$\exist b, 使 b^2 \equiv a \pmod p$
若不存在$b, 使 b^2 \equiv a \pmod p，且a != 0$， 则称a为非二次剩余，记作$a \in NR$

雅可比符号/勒让德符号 (p为素奇数)：

$(\frac{a}{p}) = \begin{cases} 1 & , a \in QR \\ -1 & , a \in NR \end{cases}$

欧拉准则

设p为素奇数，有 (这里的括号是雅可比符号/勒让德符号)

公式

$a^\frac{p-1}{2} \equiv (\frac{a}{p}) \pmod p$

证：