初等數論/二次剩餘與二次互反律

数论 > 初等数论 > 初等數論/二次剩餘與二次互反律

---

二次剩餘

二次剩餘的定義：若有一同餘方程$x^2\equiv d(\mathrm{mod}p)$，其中p是一個奇質數，且p不能整除d，若此同餘方程成立，則稱d為模p的二次剩餘，若此同餘方程不成立，則稱d為模p的二次非剩餘

歐拉準則

二次剩餘有個判別法，名叫歐拉準則： 此處的d與p及其他符號皆依照上面對於二次剩餘的定義

d為模p的二次剩餘的充要條件為：$d^{(p-1)/2}\equiv 1(\mathrm{mod}p)$

d為模p的二次非剩餘的充要條件為：$d^{(p-1)/2}\equiv -1(\mathrm{mod}p)$

證明：

只需证明定理的前一半。

• 必要性：

设$d\equiv x^2(\mathrm{mod}p)$，且$d$不能被$p$整除。

则由費馬小定理可知 $d^{(p-1)/2}\equiv x^{p-1}\equiv 1(\mathrm{mod}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}(\mathrm{mod}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}$