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

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

---

二次剩餘

二次剩餘的定義：若有一同餘方程$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}$