二次剩餘- 維基百科，自由的百科全書

1 前幾個自然數的二次剩餘; 2 研究歷史以及基本概念; 3 基本結論. 3.1 質數二次剩餘; 3.2 質數乘方的二次剩餘; 3.3 合數二次剩餘. 4 相關記號; 5 推廣; 6 相關條目 ... 二次剩餘 維基百科，自由的百科全書 跳至導覽 跳至搜尋 在數論中，特別在同餘理論裏，一個整數 X {\displaystyleX} 對另一個整數 p {\displaystylep} 的二次剩餘（英語：Quadraticresidue）指 X {\displaystyleX} 的平方 X 2 {\displaystyleX^{2}} 除以 p {\displaystylep} 得到的餘數。

當存在某個 X {\displaystyleX} ，式子 X 2 ≡ d ( mod p ) {\displaystyleX^{2}\equivd{\pmod{p}}} 成立時，稱「 d {\displaystyled} 是模 p {\displaystylep} 的二次剩餘」 當對任意 X {\displaystyleX} ， X 2 ≡ d ( mod p ) {\displaystyleX^{2}\equivd{\pmod{p}}} 不成立時，稱「 d {\displaystyled} 是模 p {\displaystylep} 的二次非剩餘」 研究二次剩餘的理論稱為二次剩餘理論。

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

目次 1前幾個自然數的二次剩餘 2研究歷史以及基本概念 3基本結論 3.1質數二次剩餘 3.2質數乘方的二次剩餘 3.3合數二次剩餘 4相關記號 5推廣 6相關條目 7注釋及參考來源 8外部連結 前幾個自然數的二次剩餘[編輯] 下表列出了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 n2 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 mod2 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 mod3 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 mod4 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 mod5 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 mod6 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 mod7 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 mod8 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 mod9 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 mod10 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 mod11 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 mod12 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 mod13 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 mod14 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 mod15 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 mod16 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 mod17 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 mod18 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 mod19 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 mod20 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 mod21 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 mod22 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 mod23 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 mod24 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 mod25 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世紀，費馬、歐拉、拉格朗日和勒讓德等數論學家對二次剩餘理論作了初步的研究，證明了一些定理[1]並作出了一些相關的猜想[2]，但首先對二次剩餘進行有系統的研究的數學家是高斯。

他在著作《算術研究》（DisquisitionesArithmeticae，1801年）中首次引入了術語「二次剩餘」與「二次非剩餘」，並聲明在不至於導致混淆的行文中，可以省略「二次」兩字。

為了得到關於一個整數 n {\displaystylen} 的所有二次剩餘（在一個完全剩餘系中），我們可以直接計算0,1,…,n−1的平方模 n {\displaystylen} 的餘數。

但只要注意到a2≡(n−a)2(modn)，我們就可以減少一半的計算量，只算到n/2了。

於是，關於 n {\displaystylen} 的二次剩餘的個數不可能超過n/2+1（n為偶數）或(n+1)/2（n為奇數）[3]。

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

基本結論[編輯] 質數二次剩餘[編輯] 對於質數2，每個整數都是它的二次剩餘。

以下討論 p {\displaystylep} 是奇質數的情況： 對於 X {\displaystyleX} ， X 2 ≡ d ( mod p ) {\displaystyleX^{2}\equivd{\pmod{p}}} 而言，能滿足「 d {\displaystyled} 是模 p {\displaystylep} 的二次剩餘」的 d {\displaystyled} 共有 ( p + 1 ) 2 {\displaystyle{\frac{(p+1)}{2}}} 個（剩餘類），分別為： 0 2 , 1 2 , . . . ( ( p − 1 ) 2 − 1 ) 2 , ( p − 1 2 ) 2 {\displaystyle0^{2},1^{2},...\left({{\frac{(p-1)}{2}}-1}\right)^{2},\left({\frac{p-1}{2}}\right)^{2}} （0計算在內） 此外是 ( p − 1 ) 2 {\displaystyle{\frac{(p-1)}{2}}} 個二次非剩餘。

但在很多情況下，我們只考慮乘法群Z/pZ，因此不將0包括在內。

[4]這樣，每個二次剩餘的乘法逆元仍然是二次剩餘；二次非剩餘的乘法逆元仍然是二次非剩餘。

[5]二次剩餘的個數與二次非剩餘的個數相等，都是 ( p − 1 ) 2 {\displaystyle{\frac{(p-1)}{2}}} 。

[4]此外，兩個二次非剩餘的乘積是二次剩餘，二次剩餘和二次非剩餘的乘積是二次非剩餘。

[5] 應用二次互反律可以知道，當 p {\displaystylep} 模4餘1時，-1是 p {\displaystylep} 的二次剩餘；如果 p {\displaystylep} 模4餘3，那麼，-1是 p {\displaystylep} 的二次非剩餘。

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

質數乘方的二次剩餘[編輯] 每個奇數的平方都模8餘1，因此模4也餘1。

設a是一個奇數。

m為8，16或2的更高次方，那麼a是關於m的二次剩餘當且僅當a≡1(mod8)[6]。

比如說，在模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(8n+1)形式的所有數，其中 k {\displaystylek} 、 n {\displaystylen} 為整數。

對於奇質數 p {\displaystylep} 以及與 p {\displaystylep} 互質的整數 A {\displaystyleA} ， A {\displaystyleA} 是關於 p {\displaystylep} 的若干次乘方的剩餘當且僅當它是關於 p {\displaystylep} 的剩餘。

設模的是pn（n次乘方）， 那麼pkA 當k≥n時是模pn的剩餘； 當k