查看“二次剩余”的源代码

在[[数论]]中，特别在[[同余]]理论裏，一个整数<math>X</math>对另一个整数<math>p</math>的'''二次剩余'''（{{lang-en|Quadratic residue}}）指<math>X</math>的[[平方]]<math>X^2</math>除以<math>p</math>得到的[[余数]]。

當存在某個<math>X</math>，式子<math>X^2 \equiv d \pmod{p}</math>成立時，稱'''「<math>d</math>是模<math>p</math>的二次剩余」'''

當对任意<math>X</math>，<math>X^2 \equiv d \pmod{p}</math>不成立時，稱'''「<math>d</math>是模<math>p</math>的二次非剩余」'''

研究二次剩余的理论称为'''二次剩余理论'''。二次剩余理论在实际上有广泛的应用，包括从[[噪音工程学]]到[[密码学]]以及[[大数分解]]。

==前几个自然数的二次剩余==
下表列出了1至25对2至25的二次剩余。

{|  class="wikitable" style="text-align:center" cellpadding="2"

|+二次剩余列表

|-
! 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<sup>2</sup> 
! width="25" |1 
! width="25" |4
! width="25" |9
! width="25" |16
! width="25" |25
! width="25" |36
! width="25" |49
! width="25" |64 
! width="25" |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世纪，[[费马]]、[[欧拉]]、[[拉格朗日]]和[[勒让德]]等数论学家对二次剩余理论作了初步的研究，证明了一些定理<ref>Lemmemeyer, Ch. 1</ref>并作出了一些相关的猜想<ref>Lemmermeyer, pp 6–8, p. 16 ff</ref>，但首先对二次剩余进行有系统的研究的数学家是[[高斯]]。他在著作《[[算术研究]]》（''Disquisitiones Arithmeticae''，1801年）中首次引入了[[术语]]“二次剩余”与“二次非剩余”，并声明在不至于导致混淆的行文中，可以省略“二次”两字。

为了得到关于一个整数<math>n</math>的所有二次剩余（在一个[[完全剩余系]]中），我们可以直接计算0, 1,…, ''n'' − 1的平方模<math>n</math>的余数。但只要注意到''a''<sup>2</sup> ≡(''n'' − ''a'')<sup>2</sup>(mod ''n'')，我们就可以减少一半的计算量，只算到''n''/2了。于是，关于<math>n</math>的二次剩余的个数不可能超过''n''/2 + 1（''n''为偶数）或(''n'' + 1)/2（''n''为奇数）<ref> Gauss, ''Disquisitiones Arithmeticae''（以下称DA）, art. 94</ref>。

两个二次剩余的乘积必然还是二次剩余。

==基本结论==
===质数二次剩余===
对于质数2，每个整数都是它的二次剩余。

以下討論<math>p</math>是奇[[質數]]的情況：

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

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

此外是<math>\frac {(p-1)}{2}</math>个二次非剩余。但在很多情况下，我们只考虑乘法[[群]]'''Z/''p''Z'''，因此不将0包括在内。<ref name="DA96"> Gauss, DA, art. 96</ref>这样，每个二次剩余的[[可逆元|乘法逆元]]仍然是二次剩余；二次非剩余的[[可逆元|乘法逆元]]仍然是二次非剩余。<ref name="DA98"> Gauss, DA, art. 98</ref>二次剩余的个数与二次非剩余的个数相等，都是<math>\frac {(p-1)}{2}</math>。<ref name="DA96" />此外，两个二次非剩余的乘积是二次剩余，二次剩余和二次非剩余的乘积是二次非剩余。<ref name="DA98" />

应用[[二次互反律]]可以知道，当<math>p</math>模4余1时，-1是<math>p</math>的二次剩余；如果<math>p</math>模4余3，那么，-1是<math>p</math>的二次非剩余。

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

===质数乘方的二次剩余===
每个奇数的平方都模8余1，因此模4也余1。设''a''是一个奇数。''m''为8，16或2的更高次方，那么''a''是关于''m''的二次剩余[[当且仅当]]''a'' ≡ 1(mod 8)<ref> Gauss, DA, art. 103</ref>。

<blockquote>比如说，在模[[32]]时，所有的[[奇數]]的平方分别是：
:1<sup>2</sup> ≡ 15<sup>2</sup> ≡ 1
:3<sup>2</sup> ≡ 13<sup>2</sup> ≡ 9
:5<sup>2</sup> ≡ 11<sup>2</sup> ≡ 25
:7<sup>2</sup> ≡ 9<sup>2</sup> ≡ 17<br>

模8都余1。而偶数的二次剩余是：
:0<sup>2</sup> ≡ 8<sup>2</sup> ≡ 16<sup>2</sup> ≡ 0
:2<sup>2</sup> ≡ 6<sup>2</sup>≡ 10<sup>2</sup> ≡ 14<sup>2</sup>≡ 4
:4<sup>2</sup> ≡ 12<sup>2</sup> ≡ 16

</blockquote>

可以看出，关于8，16或2的更高次方的二次剩余是具有4<sup>''k''</sup>(8''n'' + 1)形式的所有数，其中<math>k</math>、<math>n</math>为整数。

对于奇质数<math>p</math>以及与<math>p</math> [[互质]]的整数<math>A</math>，<math>A</math>是关于<math>p</math>的若干次乘方的剩余当且仅当它是关于<math>p</math>的剩余。

设模的是''p''<sup>''n''</sup>（n次乘方）， 
:那么''p''<sup>''k''</sup>''A'' <br>
::当''k'' ≥ ''n''时是模''p''<sup>''n''</sup>的剩余； 
::当''k'' < ''n''并为奇数时是模''p''<sup>''n''</sup>的非剩余。

当''k'' < ''n''并为偶数时，
:如果<math>A</math>是关于<math>p</math>的剩余，那么''p''<sup>''k''</sup>''A''就是模''p''<sup>''n''</sup>的剩余；
:如果<math>A</math>是关于<math>p</math>的非剩余，那么''p''<sup>''k''</sup>''A''就是模''p''<sup>''n''</sup>的非剩余<ref> Gauss, DA, art. 102</ref>。

===[[合数]]二次剩余===

首先可以看出，
:如果''a''是模''n''的剩余，并且''p''<sup>''k''</sup> [[整除]]''n''，那么''a''是模''p''<sup>''k''</sup>的剩余。
:如果''a''是模''n''的非剩余，那么存在''p''<sup>''k''</sup> [[整除]]''n''，使得''a''是模''p''<sup>''k''</sup>的非剩余。

对于模合数的情况，两个剩余的乘积仍然是剩余，剩余和非剩余的乘积必为非剩余，但是两个非剩余的乘积则可能是剩余、非剩余或0。

<blockquote>
比如，对于模15的情况 
<br>
 '''''1''''', 2, 3, '''''4''''', 5, '''''6''''', 7, 8,  '''''9''''', '''''10''''', 11, 12, 13, 14（粗斜体为二次剩余）。
<br>
两个二次非剩余2和8的乘积是二次剩余1，但另外两个二次非剩余2和7的乘积是二次非剩余14。
</blockquote>

==相关记号==
高斯使用<ref>Gauss, DA, art. 131</ref>'''R'''和'''N'''来分别表示二次剩余及二次非剩余。例如：2 R 7，5 N 7，并且1 和5 R 8，3和7 N 8。尽管这种记号在某些方面来说十分简洁<ref>比如哈代和怀特就使用它们。</ref><ref>Gauss, DA, art 230 ff.</ref>，但现今最常用的是[[勒让德符号]]，或称[[二次特征]]（见[[狄利克雷特征]]）。对于整数''a''及奇质数''p''，

:{| align=none border="0"
|rowspan=3| <math>\left(\frac{a}{p}\right) =\begin{cases}\;\;\,0 \\+1 \\-1 \end{cases}</math>
| 如果p整除a；
|-
| 如果a是模p的二次剩余且p不整除a
|-
| 如果a是模p的二次非剩余。
|}
:
:
:
:

之所以将0另分一类有两个原因。首先，这使公式和定理叙述方便。其次，二次特征是一个从乘法群'''Z/pZ'''射到复数域的[[群同态]]，<math>(\tfrac{np}{p}) = 0</math>可以将这个同态扩张到整数构成的乘法[[半群]]<ref>这个扩张对于定义''L''函数是必须的。 </ref>。

相比高斯的记号，勒让德符号的优势在于可以写在公式里（作为一个数字值）。此外勒让德符号可以推广到三次以至[[高次剩餘]]。

勒让德符号中的分母只限奇质数，对于一般的合数，有推广的[[雅可比符号]]。雅可比符号的性质比前者复杂。如果''a'' '''R''' ''m''那么<math>(\tfrac{a}{m}) = 1</math>，如果<math>(\tfrac{a}{m}) = -1</math>那么''a'' '''N''' ''m''。但如果<math>(\tfrac{a}{m}) = 1</math>，我们不能知道''a'' '''R''' ''m''还是''a'' '''N''' ''m''。

==推广==

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

== 相關條目 ==

*[[勒让德符号]]
*[[同餘]]
*[[欧拉准则]]
*[[二次互反律]]
*[[三次互反律]]

==注释及参考来源==
{{reflist}}
*闵嗣鹤、严士健，《初等数论》，第二版，高等教育出版社，2001年。

==外部链接==
*[http://www.math.ntu.edu.tw/msa/act/mathcamp/95page/lecture/K.doc 李宗儒，高斯二次互反律]{{dead link|date=2018年2月 |bot=InternetArchiveBot |fix-attempted=yes }}

[[Category:二次剩余]]
[[Category:NP完全问题]]