複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/二次剩餘/3990744
複製
複製成功

二次剩餘

鎖定
二次剩餘是數論基本概念之一。它是初等數論中非常重要的結果，不僅可用來判斷二次同餘式是否有解，還有很多用途。C.F.高斯稱它為算術中的寶石，他一人先後給出多個證明。 [1] 
研究二次剩餘的理論稱為二次剩餘理論。二次剩餘理論在實際上有廣泛的應用，包括從噪音工程學到密碼學以及大數分解。 [2] 
中文名
二次剩餘
外文名
Quadraticresidue
應用學科
數學
用    途
用來判斷二次同餘式是否有解
相關術語
二次剩餘理論
應用領域
噪音工程學到密碼學以及大數分解
定    義
數論基本概念

目錄

  1. 1 定義
  2. 2 幾個自然數
  3. 3 歷史及概念
  1. 4 基本結論
  2. ▪ 質數二次剩餘
  3. ▪ 質數乘方
  4. ▪ 合數二次剩餘
  1. 5 相關記號
  2. 6 推廣

二次剩餘定義

在數論中，特別在同餘理論裏，一個整數X對另一個整數p的二次剩餘（英語：Quadratic residue）指X的平方除以p得到的餘數。
當存在某個X，式子
成立時，稱“d是模p的二次剩餘”
當對任意不成立時，稱“ d是模 p的二次非剩餘”

二次剩餘幾個自然數

下表列出了1至25對2至25的二次剩餘。
二次剩餘列表
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
n
1
4
9
16
25
36
49
64
81
100
121
144
169
196
225
256
289
324
361
400
441
484
529
576
625
mod 2
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
mod 3
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
mod 4
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
mod 5
1
4
4
1
0
1
4
4
1
0
1
4
4
1
0
1
4
4
1
0
1
4
4
1
0
mod 6
1
4
3
4
1
0
1
4
3
4
1
0
1
4
3
4
1
0
1
4
3
4
1
0
1
mod 7
1
4
2
2
4
1
0
1
4
2
2
4
1
0
1
4
2
2
4
1
0
1
4
2
2
mod 8
1
4
1
0
1
4
1
0
1
4
1
0
1
4
1
0
1
4
1
0
1
4
1
0
1
mod 9
1
4
0
7
7
0
4
1
0
1
4
0
7
7
0
4
1
0
1
4
0
7
7
0
4
mod 10
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
mod 11
1
4
9
5
3
3
5
9
4
1
0
1
4
9
5
3
3
5
9
4
1
0
1
4
9
mod 12
1
4
9
4
1
0
1
4
9
4
1
0
1
4
9
4
1
0
1
4
9
4
1
0
1
mod 13
1
4
9
3
12
10
10
12
3
9
4
1
0
1
4
9
3
12
10
10
12
3
9
4
1
mod 14
1
4
9
2
11
8
7
8
11
2
9
4
1
0
1
4
9
2
11
8
7
8
11
2
9
mod 15
1
4
9
1
10
6
4
4
6
10
1
9
4
1
0
1
4
9
1
10
6
4
4
6
10
mod 16
1
4
9
0
9
4
1
0
1
4
9
0
9
4
1
0
1
4
9
0
9
4
1
0
1
mod 17
1
4
9
16
8
2
15
13
13
15
2
8
16
9
4
1
0
1
4
9
16
8
2
15
13
mod 18
1
4
9
16
7
0
13
10
9
10
13
0
7
16
9
4
1
0
1
4
9
16
7
0
13
mod 19
1
4
9
16
6
17
11
7
5
5
7
11
17
6
16
9
4
1
0
1
4
9
16
6
17
mod 20
1
4
9
16
5
16
9
4
1
0
1
4
9
16
5
16
9
4
1
0
1
4
9
16
5
mod 21
1
4
9
16
4
15
7
1
18
16
16
18
1
7
15
4
16
9
4
1
0
1
4
9
16
mod 22
1
4
9
16
3
14
5
20
15
12
11
12
15
20
5
14
3
16
9
4
1
0
1
4
9
mod 23
1
4
9
16
2
13
3
18
12
8
6
6
8
12
18
3
13
2
16
9
4
1
0
1
4
mod 24
1
4
9
16
1
12
1
16
9
4
1
0
1
4
9
16
1
12
1
16
9
4
1
0
1
mod 25
1
4
9
16
0
11
24
14
6
0
21
19
19
21
0
6
14
24
11
0
16
9
4
1
0

二次剩餘歷史及概念

從17世紀到18世紀，費馬、歐拉、拉格朗日和勒讓德等數論學家對二次剩餘理論作了初步的研究，證明了一些定理並作出了一些相關的猜想，但首先對二次剩餘進行有系統的研究的數學家是高斯。他在著作《算術研究》（Disquisitiones Arithmeticae，1801年）中首次引入了術語“二次剩餘”與“二次非剩餘”，並聲明在不至於導致混淆的行文中，可以省略“二次”兩字。
為了得到關於一個整數 n的所有二次剩餘（在一個完全剩餘系中），我們可以直接計算0, 1,…,n− 1的平方模n的餘數。但只要注意到a≡(n−a)(modn)，我們就可以減少一半的計算量，只算到n/2了。於是，關於n的二次剩餘的個數不可能超過n/2 + 1（n為偶數）或(n+ 1)/2（n為奇數）。 [1] 
兩個二次剩餘的乘積必然還是二次剩餘。

二次剩餘基本結論

二次剩餘質數二次剩餘

對於質數2，每個整數都是它的二次剩餘。 [3] 
以下討論p是奇質數的情況：
對於X，
而言，能滿足“d是模 p的二次剩餘”的 d共有
個（剩餘類），分別為：
（0計算在內）
此外是
個二次非剩餘。但在很多情況下，我們只考慮乘法羣Z/pZ，因此不將0包括在內。這樣，每個二次剩餘的乘法逆元仍然是二次剩餘；二次非剩餘的乘法逆元仍然是二次非剩餘。二次剩餘的個數與二次非剩餘的個數相等，都是。此外，兩個二次非剩餘的乘積是二次剩餘，二次剩餘和二次非剩餘的乘積是二次非剩餘。
應用二次互反律可以知道，當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時，所有的奇數的平方分別是：
  • 1≡ 15≡ 1
  • 3≡ 13≡ 9
  • 5≡ 11≡ 25
  • 7≡ 9≡ 17
模8都餘1。而偶數的二次剩餘是：
  • 0≡ 8≡ 16≡ 0
  • 2≡ 6≡ 10≡ 14≡ 4
  • 4≡ 12≡ 16
可以看出，關於8，16或2的更高次方的二次剩餘是具有4(8n+ 1)形式的所有數，其中k、n為整數。
對於奇質數p以及與p互質的整數A，A是關於p的若干次乘方的剩餘當且僅當它是關於p的剩餘。
設模的是p（n次乘方），
  • 那麼pA
    • 當k≥n時是模p的剩餘；
    • 當k<n併為奇數時是模p的非剩餘。
當k<n併為偶數時，
  • 如果A是關於p的剩餘，那麼pA就是模p的剩餘；
  • 如果A是關於p的非剩餘，那麼pA就是模p的非剩餘。

二次剩餘合數二次剩餘

首先可以看出， [3] 
  • 如果a是模n的剩餘，並且p整除n，那麼a是模p的剩餘。
  • 如果a是模n的非剩餘，那麼存在p整除n，使得a是模p的非剩餘。
對於模合數的情況，兩個剩餘的乘積仍然是剩餘，剩餘和非剩餘的乘積必為非剩餘，但是兩個非剩餘的乘積則可能是剩餘、非剩餘或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 和5 R 8，3和7 N 8。儘管這種記號在某些方面來説十分簡潔，但現今最常用的是勒讓德符號，或稱二次特徵（見狄利克雷特徵）。對於整數a及奇質數p，
如果p整除a；
如果a是模p的二次剩餘且p不整除a
如果a是模p的二次非剩餘。
之所以將0另分一類有兩個原因。首先，這使公式和定理敍述方便。其次，二次特徵是一個從乘法羣Z/pZ射到複數域的羣同態，
可以將這個同態擴張到整數構成的乘法半羣。
相比高斯的記號，勒讓德符號的優勢在於可以寫在公式裏（作為一個數字值）。此外勒讓德符號可以推廣到三次以至高次剩餘。
勒讓德符號中的分母只限奇質數，對於一般的合數，有推廣的雅可比符號。雅可比符號的性質比前者複雜。如果aRm那麼
，如果
那麼aNm。但如果
，我們不能知道aRm還是aNm。

二次剩餘推廣

二次剩餘的推廣叫做高次剩餘，是研究任意X，
中d是否為模p的n次剩餘的問題。
參考資料
  • 1.    閔嗣鶴、嚴士健，《初等數論》，第二版，高等教育出版社，2001年
  • 2.    李子臣, 戴一奇. 二次剩餘密碼體制的安全性分析[J]. 清華大學學報: 自然科學版, 2001, 41(7): 80-82.
  • 3.    承洞, 承彪. 初等數論[M]. 北京大學出版社, 2003.