问题及解答

勒让德(Legendre)符号的性质.

勒让德符号 $\Bigl(\frac{a}{p}\Bigr)$ 定义为

\[
\biggl(\frac{a}{p}\biggr)=\begin{cases}
1, & a\ \text{是}\ p\ \text{的平方剩余},\\
-1, & a\ \text{不是}\ p\ \text{的平方剩余}.\\
\end{cases}
\]

所谓平方剩余是指:

若方程 $x^2\equiv a\pmod p$ 有解, 则称数 $a$ 是素数 $p$ 的平方剩余. (这里 $p$ 是奇素数.)

(1)  若 $a\equiv b\pmod p$, 则 $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$.

(2) $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$.

作为(2) 的推广, 我们有

(3) 

\[\left(\frac{a^n}{p}\right)=\left(\frac{a}{p}\right)^n,\quad \left(\frac{a^2}{p}\right)=+1,\quad \left(\frac{ab^2}{p}\right)=\left(\frac{a}{p}\right).\]

以上内容参见 [1] P. 99

References:

A. K. 苏什凯维奇 著  叶乃膺 译 《数论初等教程》,  哈尔滨工业大学出版社.

(1)  由于 $p$ 是奇素数, $\frac{p-1}{2}\in\mathbb{Z}^+$, 因此,

\[
(a-b)\ \biggr|\ (a^{\frac{p-1}{2}}-b^{\frac{p-1}{2}})
\]

因此, 若 $a\equiv b\pmod p$, 则

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

即有

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

(2) 

\[
\begin{aligned}
a^{\frac{p-1}{2}}&\equiv\left(\frac{a}{p}\right)\pmod p\\
b^{\frac{p-1}{2}}&\equiv\left(\frac{b}{p}\right)\pmod p\\
\end{aligned}
\]

将两式相乘, 得

\[
(ab)^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\pmod p\\
\]

而

\[
(ab)^{\frac{p-1}{2}}\equiv\left(\frac{ab}{p}\right)\pmod p
\]

即得

\[
\left(\frac{ab}{p}\right)\equiv\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\pmod p
\]

由于 $p > 2$, 故

\[
\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).
\]