在合數的情況下，雖然一個整數 \( a \) 是模 \( n \) 的二次剩餘，但這並不保證它的乘積也在所有模下仍然是二次剩餘。這是因為二次剩餘的性質不僅依賴於模的性質，還受到因數分解的影響。

具體來說，考慮以下的例子來說明這一點：

假設我們考慮模 \( n = 15 \)，我們可以列出在模 \( 15 \) 下的整數及其二次剩餘：

- 二次剩餘有：\( 0, 1, 4, 6, 9, 10, 14 \)
- 二次非剩餘有：\( 2, 3, 5, 7, 8, 11, 12, 13 \)

在這個例子中，考慮 \( 2 \) 和 \( 8 \) 這兩個二次非剩餘。根據前面的敘述，二次非剩餘的乘積可能是二次剩餘或非剩餘。讓我們來計算它們的乘積：

\[
2 \times 8 \equiv 16 \equiv 1 \pmod{15}
\]

在這裡，我們看到 \( 2 \) 和 \( 8 \) 的乘積 \( 16 \) 在模 \( 15 \) 下是 \( 1 \)，而 \( 1 \) 是二次剩餘。因此，兩個二次非剩餘的乘積得到了一個二次剩餘的結果。

再考慮一個例子，現在我們使用非剩餘 \( 2 \) 和 \( 7 \)：

\[
2 \times 7 \equiv 14 \pmod{15}
\]

在這裡，\( 14 \) 是二次剩餘（因為它是 \( 14 \equiv 14 \pmod{15} \)），但下列情況會更加說明問題的複雜性：如果我們考慮兩個數 \( 2 \) 和 \( 3 \)（這都是模 \( 15 \) 的二次非剩餘），我們計算它們的乘積：

\[
2 \times 3 \equiv 6 \pmod{15}
\]

在這裡， \( 6 \) 是一個二次剩餘。

從這些例子中可以看出，即使在合數 \( n \) 下，對於某些非剩餘的整數乘積也是可能結果為剩餘，這說明了二次剩餘的結構在合數的情況下是更加複雜的。
在合數的情況下，如果一個整數是二次剩餘，為什麼這並不保證它的乘積在所有模下仍然是二次剩餘？能否提供一個具體的例子來說明這一點？
在數論中，特別在同餘理論裏，一個整數 $X$ 對另一個整數 $p$ 的**二次剩餘**（英語：Quadratic residue）指 $X$ 的平方 $X^{2}$ 除以 $p$ 得到的餘數。

當存在某個 $X$ ，式子 $X^{2}\equiv d{\pmod {p}}$ 成立時，稱 **「 $d$ 是模 $p$ 的二次剩餘」** 

當對任意 $X$ ， $X^{2}\equiv d{\pmod {p}}$ 不成立時，稱 **「 $d$ 是模 $p$ 的二次非剩餘」** 

研究二次剩餘的理論稱為**二次剩餘理論**。二次剩餘理論在實際上有廣泛的應用，包括從噪音工程學到密碼學以及大數分解。

## 前幾個自然數的二次剩餘

下表列出了 1 至 25 對 2 至 25 的二次剩餘。

## 研究歷史以及基本概念

從 17 世紀到 18 世紀，費馬、歐拉、拉格朗日和勒讓德等數論學家對二次剩餘理論作了初步的研究，證明了一些定理並作出了一些相關的猜想，但首先對二次剩餘進行有系統的研究的數學家是高斯。他在著作《算術研究》（_Disquisitiones Arithmeticae_，1801 年）中首次引入了術語「二次剩餘」與「二次非剩餘」，並聲明在不至於導致混淆的行文中，可以省略「二次」兩字。

為了得到關於一個整數 $n$ 的所有二次剩餘（在一個完全剩餘系中），我們可以直接計算 0, 1,…, _n_ − 1 的平方模 $n$ 的餘數。但只要注意到 _a_2 ≡(_n_ − _a_)2(mod _n_)，我們就可以減少一半的計算量，只算到 _n_/2 了。於是，關於 $n$ 的二次剩餘的個數不可能超過 _n_/2 + 1（_n_ 為偶數）或 (_n_ + 1)/2（_n_ 為奇數）。

兩個二次剩餘的乘積必然還是二次剩餘。

## 基本結論

### 質數二次剩餘

對於質數 2，每個整數都是它的二次剩餘。

以下討論 $p$ 是奇質數的情況：

對於 $X$ ， $X^{2}\equiv d{\pmod {p}}$ 而言，能滿足「 $d$ 是模 $p$ 的二次剩餘」的 $d$ 共有 ${\frac {(p+1)}{2}}$ 個（剩餘類），分別為：

 $0^{2},1^{2},...\left({{\frac {(p-1)}{2}}-1}\right)^{2},\left({\frac {p-1}{2}}\right)^{2}$ （0 計算在內）

此外是 ${\frac {(p-1)}{2}}$ 個二次非剩餘。但在很多情況下，我們只考慮乘法群 **Z/_p_Z**，因此不將 0 包括在內。這樣，每個二次剩餘的乘法逆元仍然是二次剩餘；二次非剩餘的乘法逆元仍然是二次非剩餘。二次剩餘的個數與二次非剩餘的個數相等，都是 ${\frac {(p-1)}{2}}$ 。此外，兩個二次非剩餘的乘積是二次剩餘，二次剩餘和二次非剩餘的乘積是二次非剩餘。

應用二次互反律可以知道，當 $p$ 模 4 餘 1 時，-1 是 $p$ 的二次剩餘；如果 $p$ 模 4 餘 3，那麼，-1 是 $p$ 的二次非剩餘。

要知道 d 是否為模 p 的二次剩餘，可以運用歐拉判別法（或叫歐拉準則）。

### 質數乘方的二次剩餘

每個奇數的平方都模 8 餘 1，因此模 4 也餘 1。設 _a_ 是一個奇數。_m_ 為 8，16 或 2 的更高次方，那麼 _a_ 是關於 _m_ 的二次剩餘若且唯若 _a_ ≡ 1(mod 8)。

> 比如說，在模 32 時，所有的奇數的平方分別是：
> 
> 　
> : 12 ≡ 152 ≡ 1
> 
> 　
> : 32 ≡ 132 ≡ 9
> 
> 　
> : 52 ≡ 112 ≡ 25
> 
> 　
> : 72 ≡ 92 ≡ 17
> 
> 模 8 都餘 1。而偶數的二次剩餘是：
> 
> 　
> : 02 ≡ 82 ≡ 162 ≡ 0
> 
> 　
> : 22 ≡ 62≡ 102 ≡ 142≡ 4
> 
> 　
> : 42 ≡ 122 ≡ 16
> 
> 

可以看出，關於 8，16 或 2 的更高次方的二次剩餘是具有 4k(8_n_ + 1) 形式的所有數，其中 $k$ 、 $n$ 為整數。

對於奇質數 $p$ 以及與 $p$ 互質的整數 $A$ ， $A$ 是關於 $p$ 的若干次乘方的剩餘若且唯若它是關於 $p$ 的剩餘。

設模的是 _p_n（n 次乘方），

　
: 那麼 _p_k_A_ 

　
: 當 _k_ ≥ _n_ 時是模 _p_n 的剩餘；

　
: 當 _k_ < _n_ 並為奇數時是模 _p_n 的非剩餘。

當 _k_ < _n_ 並為偶數時，

　
: 如果 $A$ 是關於 $p$ 的剩餘，那麼 _p_k_A_ 就是模 _p_n 的剩餘；

　
: 如果 $A$ 是關於 $p$ 的非剩餘，那麼 _p_k_A_ 就是模 _p_n 的非剩餘。

### 合數二次剩餘

首先可以看出，

　
: 如果 _a_ 是模 _n_ 的剩餘，並且 _p_k 整除 _n_，那麼 _a_ 是模 _p_k 的剩餘。

　
: 如果 _a_ 是模 _n_ 的非剩餘，那麼存在 _p_k 整除 _n_，使得 _a_ 是模 _p_k 的非剩餘。

對於模合數的情況，兩個剩餘的乘積仍然是剩餘，剩餘和非剩餘的乘積必為非剩餘，但是兩個非剩餘的乘積則可能是剩餘、非剩餘或 0。

> 
> 比如，對於模 15 的情況 
> 
> _**1**_, 2, 3, _**4**_, 5, _**6**_, 7, 8, _**9**_, _**10**_, 11, 12, 13, 14（粗斜體為二次剩餘）。 
> 兩個二次非剩餘 2 和 8 的乘積是二次剩餘 1，但另外兩個二次非剩餘 2 和 7 的乘積是二次非剩餘 14。
> 
> 

## 相關記號

高斯使用 **R** 和 **N** 來分別表示二次剩餘及二次非剩餘。例如：2 R 7，5 N 7，並且 1 R 8，3,5,7 N 8。儘管這種記號在某些方面來說十分簡潔，但現今最常用的是勒讓德符號，或稱二次特徵（見狄利克雷特徵）。對於整數 _a_ 及奇質數 _p_，

　
:

　
: 

　
: 

　
: 

　
:

之所以將 0 另分一類有兩個原因。首先，這使公式和定理敘述方便。其次，二次特徵是一個從乘法群 **Z/pZ** 射到複數域的群同態， $({\tfrac {np}{p}})=0$ 可以將這個同態擴張到整數構成的乘法半群。

相比高斯的記號，勒讓德符號的優勢在於可以寫在公式里（作為一個數字值）。此外勒讓德符號可以推廣到三次以至高次剩餘。

勒讓德符號中的分母只限奇質數，對於一般的奇合數，有推廣的雅可比符號。雅可比符號的性質比前者複雜。如果 _a_ **R** _m_ 那麼 $({\tfrac {a}{m}})=1$ ，如果 $({\tfrac {a}{m}})=-1$ 那麼 _a_ **N** _m_。但如果 $({\tfrac {a}{m}})=1$ ，我們不能知道 _a_ **R** _m_ 還是 _a_ **N** _m_。

## 推廣

二次剩餘的推廣叫做高次剩餘，是研究任意 $X$ ， $X^{n}\equiv d{\pmod {p}}$ 中 $d$ 是否為模 $p$ 的 $n$ 次剩餘的問題。

## 相關條目

* 勒讓德符號
* 同餘
* 歐拉準則
* 二次互反律
* 三次互反律

## 注釋及參考來源

* 閔嗣鶴、嚴士健，《初等數論》，第二版，高等教育出版社，2001 年。

## 外部連結

* 李宗儒，高斯二次互反律
在數論中，**高斯引理**給出了一個整數是模另一個整數的二次剩餘的條件。儘管高斯引理沒有實際計算上的意義，但作為二次互反律的證明中的一環，高斯引理有著理論上的重要性。

高斯引理最早出現在高斯 1808 年發表的二次互反律的第三個證明中，並在第五個證明中再次用到。

## 敘述

設 $p$ 為奇質數， $a$ 是一個與 _$p$_ 互質的整數。考慮以下數組： $a,2a,3a,\dots ,{\frac {p-1}{2}}a$ , 取它們模 _$p$_ 的最小非負剩餘。這些剩餘兩兩不等，因此我們共有 ${\frac {p-1}{2}}$ 個兩兩不等的介於 1 和 _$p-1$_ 之間的整數： $t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}$ 。設其中有 $n$ 個數比 ${\frac {p}{2}}$ 大，那麼高斯引理聲稱：

　
: $\left({\frac {a}{p}}\right)=(-1)^{n}$

上式左邊是勒讓德符號，當其值為 + 1 時，表示 _$a$_ 是模 _$p$_ 的二次剩餘；其值為 - 1 時，表示 _$a$_ 是模 _$p$_ 的二次非剩餘。

用通俗的語言來說，就是：如果 $t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}$ 裡面比 ${\frac {p}{2}}$ 大的有偶數個，那麼 _$a$_ 是模 _$p$_ 的二次剩餘，如果有奇數個，那麼 _$a$_ 是模 _$p$_ 的二次非剩餘。 ## 例子

令 $p=11$ ， $a=7$ ，則我們考慮的數組是 $7,14,21,28,35$ 。模 11 之後，就得到 $7,3,10,6,2$ 。其中比 ${\frac {11}{2}}$ 大的有三個： $6,7,10$ 。3 是奇數，因此由高斯引理得到結論：7 是模 11 的二次非剩餘。

這個結論是正確的，因為模 11 的全部二次剩餘是 $1,3,4,5,9$ ，不包括 7 在內。 ## 研究歷史以及基本概念

從 17 世紀到 18 世紀，費馬、歐拉、拉格朗日和勒讓德等數論學家對二次剩餘理論作了初步的研究，證明了一些定理並作出了一些相關的猜想，但首先對二次剩餘進行有系統的研究的數學家是高斯。他在著作《算術研究》（_Disquisitiones Arithmeticae_，1801 年）中首次引入了術語「二次剩餘」與「二次非剩餘」，並聲明在不至於導致混淆的行文中，可以省略「二次」兩字。

為了得到關於一個整數 $n$ 的所有二次剩餘（在一個完全剩餘系中），我們可以直接計算 0, 1,…, _n_ − 1 的平方模 $n$ 的餘數。但只要注意到 _a_2 ≡(_n_ − _a_)2(mod _n_)，我們就可以減少一半的計算量，只算到 _n_/2 了。於是，關於 $n$ 的二次剩餘的個數不可能超過 _n_/2 + 1（_n_ 為偶數）或 (_n_ + 1)/2（_n_ 為奇數）。

兩個二次剩餘的乘積必然還是二次剩餘。 高斯之後雅可比、柯西、劉維爾、克羅內克、弗洛貝尼烏斯等也相繼給出了新的證明。至今，二次互反律已有超過 200 個不同的的證明。二次互反律可以推廣到更高次的情況，如三次互反律等等。

## 相關術語

一個整數 $a$ 是模整數 $n$ 的**二次剩餘**，是指它與某個整數的平方關於模 _$n$_ 同餘。直觀來說，是指二次同餘方程 $x^{2}\equiv a{\pmod {n}}$ 有整數解。如果這樣的整數解不存在，則稱 $a$ 是模整數 $n$ 的**二次非剩餘**。術語中的「二次」一詞是為了表示與平方同餘，在不至於混淆的行文中，可以略掉。當模數是質數時，通常將 0 的情況區別討論，因此有：

1. 在模為質數時，二次剩餘與二次非剩餘的個數是相等的。
2. 在模為質數時，剩餘與剩餘、非剩餘與非剩餘的乘積都是剩餘，剩餘與非剩餘的乘積是非剩餘。