问题及解答

Euler 准则.

设 $p$ 是一个奇素数, $a$ 是一不能被 $p$ 整除的整数. 则 $a$ 是模 $p$ 的平方剩余当且仅当

\[
a^{\frac{p-1}{2}}\equiv 1\pmod p
\]

Remark: 证明要用到模素数的剩余构成一个域这个事实.

若 $a\equiv 0\pmod p$, 则 $a^{p-1}\equiv 0\pmod p$. 否则, 根据 Fermat's little theorem $a^{p-1}\equiv 1\pmod p$. 于是, 可改写为

\[
\biggl(a^{\frac{p-1}{2}}-1\biggr)\biggl(a^{\frac{p-1}{2}}+1\biggr)\equiv 0\pmod p\qquad (*)
\]

由于模 $p$ 的余数构成一个域, 其中一个因子必定同余 0. 

现在若 $a$ 是模 $p$ 的二次剩余, 即存在 $x$ ($p\not|x$), 使得 $a\equiv x^2\pmod p$, 则

\[
a^{\frac{p-1}{2}}\equiv(x^2)^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1\pmod p
\]

因此每个模 $p$ 二次剩余都使得(*)式的第一个因子同余为 0.

References:

https://en.wikipedia.org/wiki/Euler%27s_criterion