初等数论/二次剩余与二次互反律

数论 > 初等数论 > 初等数论/二次剩余与二次互反律

---

二次剩余

二次剩余的定义：若有一同余方程$x^{2}\equiv d{\pmod {p}}$，其中p是一个奇质数，且p不能整除d，若此同余方程成立，则称d为模p的二次剩余，若此同余方程不成立，则称d为模p的二次非剩余

欧拉准则

二次剩余有个判别法，名叫欧拉准则： 此处的d与p及其他符号皆依照上面对于二次剩余的定义

d为模p的二次剩余的充要条件为：$d^{(p-1)/2}\equiv 1{\pmod {p}}$

d为模p的二次非剩余的充要条件为：$d^{(p-1)/2}\equiv -1{\pmod {p}}$

证明：

只需证明定理的前一半。

• 必要性：

设$d\equiv x^{2}{\pmod {p}}$，且$d$不能被$p$整除。

则由费马小定理可知 $d^{(p-1)/2}\equiv x^{p-1}\equiv 1{\pmod {p}}$ 。

• 充分性：

勒让德符号

依照上面对于二次剩余的定义，对于奇质数 p 以及整数 d，如果 p 不能整除 d，我们可以定义勒让德符号$\left({\frac {d}{p}}\right)$如下：

$\left({\frac {d}{p}}\right)$

=1，若d为模p的二次剩余；

=-1，若d为模p的二次非剩余

由二次剩余和勒让德符号的定义可推出：

• $\left({\frac {1}{p}}\right)=1$；

$\left({\frac {-1}{p}}\right)=(-1)^{(p-1)/2}$

• $\left({\frac {d+p}{p}}\right)=\left({\frac {d}{p}}\right)$

• $\left({\frac {de}{p}}\right)=\left({\frac {d}{p}}\right)\left({\frac {e}{p}}\right)$

• $\left({\frac {d^{2}}{p}}\right)=1$

上面的欧拉判别法亦可用勒让德符号表示，即：$\left({\frac {d}{p}}\right)\equiv d^{(p-1)/2}{\pmod {p}}$

二次互反律

对于奇质数p,q，有以下定理：

$\left({\frac {d^{2}}{p}}\right)=\left({\frac {q}{p}}\right)\left({\frac {p}{q}}\right)=(-1)^{(p-1)(q-1)/4}$