二次剩餘

二次剩餘指任意平方數除以某個數後可能的餘數。

定义

若對於任意正整數$x \ne 0, m \ne 0$與$a$而言，$x^2 \equiv a \pmod{m}$成立，則稱$a$為模$m$的二次剩餘，不然，則稱$a$為模$m$的二次非剩餘。

像例如對於$10$而言，$1, 4, 5, 6$和$9$即為模$10$的二次剩餘。

對於任意正整數$n$而言，$0$顯然是其二次剩餘，因為顯然有$n^2 \equiv 0 \pmod{n}$，所以$0$可以不被考慮。

二次剩餘在域中的分佈

對於任意奇質數$p$的一個完全剩餘系而言，該完全剩餘系中有一半的數是模$p$的二次剩餘，而剩下的數則是模$p$的二次非剩餘。

若$g$是奇素數$p$的一個原根，那麽它的所有二次剩餘可表示爲$\left\{ 1^2, 2^2, 3^2, \cdots, \left( \dfrac{p-1}{2} \right)^2 \right\} = \{ g^0, g^2, g^4, \cdots, g^{p-3} \}$；所有二次非剩餘可表示爲$\{ g^1, g^3, g^5, \cdots, g^{p-2} \}$

判定

歐拉準則是判定任意數是否為某個質數$p$的二次剩餘的方法，並可以之定義勒讓德符號，除了歐拉準則外，另亦有二次互反律可幫助驗證某兩個質數是否互為對方的二次剩餘。

上下節

• 上一節：k 次剩餘
• 下一節：Legendre 符號