二次互反律
来自维基百科,自由的百科全书
在數論中,特別是在同餘理論里,二次互反律(Law of Quadratic Reciprocity)是一個用於判別二次剩餘,即二次同餘方程之整數解的存在性的定律。二次互反律揭示了方程 可解和 可解的簡單關係。運用二次互反律可以將模數較大的二次剩餘判別問題轉為模數較小的判別問題,並最後歸結為較少的幾個情況,從而在實際上解決了二次剩餘的判別問題。然而,二次互反律只能提供二次剩餘的存在性,對於二次同餘方程的具體求解並沒有實際幫助。
其中是勒讓德符號。但是對於更一般的雅可比符號和希爾伯特符號也有對應的二次互反律。
歐拉和勒讓德都曾經提出過二次互反律的猜想。但第一個嚴格的證明是由高斯在1796年作出的,隨後他又發現了另外七個不同的證明[1]。在《算數研究》一書和相關論文中,高斯將其稱為「基石」:
這個定理肯定屬於最優雅的基本定理。(Art. 151)
私下裡高斯把二次互反律譽為算術理論中的寶石,是一個黃金定律[2]。
高斯之後雅可比、柯西、劉維爾、克羅內克、弗洛貝尼烏斯等也相繼給出了新的證明。至今,二次互反律已有超過200個不同的的證明。二次互反律可以推廣到更高次的情況,如三次互反律等等。
相關術語
一個整數 是模整數 的二次剩餘,是指它與某個整數的平方關於模 同餘。直觀來說,是指二次同餘方程有整數解。如果這樣的整數解不存在,則稱 是模整數 的二次非剩餘。術語中的「二次」一詞是為了表示與平方同餘,在不至於混淆的行文中,可以略掉。當模數是質數時,通常將0的情況區別討論,因此有:
- 在模為質數時,二次剩餘與二次非剩餘的個數是相等的。
- 在模為質數時,剩餘與剩餘、非剩餘與非剩餘的乘積都是剩餘,剩餘與非剩餘的乘積是非剩餘。
幾個簡單情況
有了上節的關於乘積的性質,可以發現:研究一個合數是否是模某個質數的剩餘,只需將這個合數進行質因數分解,研究其每個質因數是不是模的剩餘即可。因此,為了尋找模質數的二次剩餘的規律,可以先研究對於前幾個質數2、3、5等的情況,看對於什麼樣的質數,2、3、5等是模它們的剩餘。此外為了研究正負號對乘積的影響,也要研究-1的情況。為了發現規律,可以藉助50以內的質數的二次剩餘表。
下表列出了1至20模50以內的質數的二次剩餘。其中每一行列出了模相應質數的所有剩餘。因此要看某個整數 是否是模某個質數 的剩餘,只需要看 是否在模 的那一行中出現就行了。
- 例如,要檢查7是不是模37的剩餘,可以查看7是否出現在模37的一行中。實際上7出現在左數第9個格子裡,因此7是模37的二次剩餘。
- 又如,要檢查7是不是模43的剩餘,可以查看7是否出現在模43的一行中。實際上並沒有7出現,因此7是模43的二次非剩餘。
- 又如,要檢查7是不是模41的剩餘,可以查看7是否出現在模41的一行中。實際上並沒有7出現,因此7是模41的二次非剩餘。
- 又如,要檢查18是不是模47的剩餘,可以查看18是否出現在模47的一行中。實際上並沒有18出現,但是注意了,當時,,因此18是模47的二次剩餘(如要判斷質數,至少須寫到)。
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
n2 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 | 121 | 144 | 169 | 196 | 225 | 256 | 289 | 324 | 361 | 400 |
mod 3 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
mod 5 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 |
mod 7 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 | 4 | 1 |
mod 11 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 |
mod 13 | 1 | 4 | 9 | 3 | 12 | 10 | 10 | 12 | 3 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 3 | 12 | 10 | 10 |
mod 17 | 1 | 4 | 9 | 16 | 8 | 2 | 15 | 13 | 13 | 15 | 2 | 8 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 |
mod 19 | 1 | 4 | 9 | 16 | 6 | 17 | 11 | 7 | 5 | 5 | 7 | 11 | 17 | 6 | 16 | 9 | 4 | 1 | 0 | 1 |
mod 23 | 1 | 4 | 9 | 16 | 2 | 13 | 3 | 18 | 12 | 8 | 6 | 6 | 8 | 12 | 18 | 3 | 13 | 2 | 16 | 9 |
mod 29 | 1 | 4 | 9 | 16 | 25 | 7 | 20 | 6 | 23 | 13 | 5 | 28 | 24 | 22 | 22 | 24 | 28 | 5 | 13 | 23 |
mod 31 | 1 | 4 | 9 | 16 | 25 | 5 | 18 | 2 | 19 | 7 | 28 | 20 | 14 | 10 | 8 | 8 | 10 | 14 | 20 | 28 |
mod 37 | 1 | 4 | 9 | 16 | 25 | 36 | 12 | 27 | 7 | 26 | 20 | 33 | 21 | 11 | 3 | 34 | 30 | 28 | 28 | 30 |
mod 41 | 1 | 4 | 9 | 16 | 25 | 36 | 8 | 23 | 40 | 18 | 39 | 21 | 5 | 32 | 20 | 10 | 2 | 37 | 33 | 31 |
mod 43 | 1 | 4 | 9 | 16 | 25 | 36 | 6 | 21 | 38 | 14 | 35 | 15 | 40 | 24 | 10 | 41 | 31 | 23 | 17 | 13 |
mod 47 | 1 | 4 | 9 | 16 | 25 | 36 | 2 | 17 | 34 | 6 | 27 | 3 | 28 | 8 | 37 | 21 | 7 | 42 | 32 | 24 |
首先,看看對於什麼樣的質數,–1是模它的二次剩餘。查對上表後可以發現:–1對於模是二次剩餘,而對則不是。比如:
,,,等等。
可以發現前者都是模4餘1的質數,後者都是模4餘3的質數。於是可以猜想:
- 同餘方程 有解若且唯若 。
接下來看對什麼樣的質數,2是模它的二次剩餘。同樣查對上表後可以發現:對於模8餘±1的質數,如,2是模它的二次剩餘。對於模8餘±3的質數如 等則不然。
3是模11、13、23、37和47的剩餘,但不是模5、7、17、19、29、31、41或43的剩餘。
前者模12都余±1,後者都模12餘±5。
–3是模7、13、19、31、37和43的剩餘,但不是模5、11、17、23、29、41或47的剩餘,前者模3都餘1,後者模3都餘2。
由於模3的剩餘只有1,可以發現一個規律:對於所有為模3的剩餘的質數,-3是模它的剩餘。
5是模11、19、29、31和41的剩餘,但不是模3、7、13、17、23、37、43或47的剩餘,前者模5都余±1,後者模5都余±2。
由於模5的剩餘只有±1,可以發現規律:對於所有為模5的剩餘的質數,5是模它的剩餘。
6是模5、19、23、29、43和47的剩餘,但不是模7、11、13、17、31、37或41的剩餘,前者模24都余±1或±5,後者模24都余±7或±11。
7是模3、19、29、31、37和47的剩餘,但不是模5、11、13、17、23、41或43的剩餘,前者模28都余±1、±3或±9,後者模28都余±5、±11或±13。
–7是模2、11、23、29、37和43的剩餘,但不是模3、5、13、17、19、31、41或47的剩餘,前者模7都餘1、2、4,後者模7都餘3、5、6。
由於模7的剩餘只有1、2或4,可以發現一個規律:對於所有為模7的剩餘的質數,-7是模它的剩餘。
質因數分解 | 質因數分解 | ||||
---|---|---|---|---|---|
0 | 2 | 2 | 21 | 464 | 24⋅29 |
1 | 4 | 22 | 22 | 508 | 22⋅127 |
2 | 8 | 23 | 23 | 554 | 2⋅277 |
3 | 14 | 2⋅7 | 24 | 602 | 2⋅7⋅43 |
4 | 22 | 2⋅11 | 25 | 652 | 22⋅163 |
5 | 32 | 25 | 26 | 704 | 26⋅11 |
6 | 44 | 22⋅11 | 27 | 758 | 2⋅379 |
7 | 58 | 2⋅29 | 28 | 814 | 2⋅11⋅37 |
8 | 74 | 2⋅37 | 29 | 872 | 23⋅109 |
9 | 92 | 22⋅23 | 30 | 932 | 22⋅233 |
10 | 112 | 24⋅7 | 31 | 994 | 2⋅7⋅71 |
11 | 134 | 2⋅67 | 32 | 1058 | 2⋅232 |
12 | 158 | 2⋅79 | 33 | 1124 | 22⋅281 |
13 | 184 | 23⋅23 | 34 | 1192 | 23⋅149 |
14 | 212 | 22⋅53 | 35 | 1262 | 2⋅631 |
15 | 242 | 2⋅112 | 36 | 1334 | 2⋅23⋅29 |
16 | 274 | 2⋅137 | 37 | 1408 | 27⋅11 |
17 | 308 | 22⋅7⋅11 | 38 | 1484 | 22⋅7⋅53 |
18 | 344 | 23⋅43 | 39 | 1562 | 2⋅11⋅71 |
19 | 382 | 2⋅191 | 40 | 1642 | 2⋅821 |
20 | 422 | 2⋅211 | 41 | 1724 | 22⋅431 |
不難發現,在是整數的情況,只能被模7二次剩餘的質數整除,不可能被模7二次非剩餘的質數整除,因為,所以只能被模7二次剩餘的質數整除。
對於2、7、11、23、29、37、43、53、67、71、79、107、109、113、127、137等質數都是模7的二次剩餘。(OEIS數列A045373)
對於3、5、13、17、19、31、41、47、59、61、73、83、89、97、101、103、131、139等質數都是模7的二次非剩餘。(OEIS數列A003625)
高斯和勒讓德的敘述
對於一般的情況,也有類似的規律。在此基礎上,高斯和勒讓德提出了兩個一般性的敘述(沒有使用勒讓德符號),兩者是等價的。
如果 那麼 可解若且唯若可解。
如果 那麼 可解若且唯若可解。 藉助於以下變量:,命題可以簡化為:
- 可解若且唯若可解。
在高斯的敘述中已經可以見到「互反」的體現,即將 的可解性與的可解性聯繫起來。在下表中可以看出,這表現了一種對稱性(反對稱性)。
下表列明了質數之間相互是否為二次剩餘的情況。方格內為R表示對應的(橫列元素)為對應的(豎列元素)的二次剩餘,N則表示相反情況(此表示法由高斯創造)。可以看到白格內的元素是關於對角線對稱的,黃格內則關於對角線反對稱。可以說黃格代表了一種「特殊情況」[3]。
q | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 | 97 | ||
p | 3 | N | R | N | R | N | R | N | N | R | R | N | R | N | N | N | R | R | N | R | R | N | N | R | |
5 | N | N | R | N | N | R | N | R | R | N | R | N | N | N | R | R | N | R | N | R | N | R | N | ||
7 | N | N | R | N | N | N | R | R | N | R | N | R | N | R | N | N | R | R | N | R | N | N | N | ||
11 | R | R | N | N | N | N | R | N | R | R | N | N | R | R | R | N | R | R | N | N | N | R | R | ||
13 | R | N | N | N | R | N | R | R | N | N | N | R | N | R | N | R | N | N | N | R | N | N | N | ||
17 | N | N | N | N | R | R | N | N | N | N | N | R | R | R | R | N | R | N | N | N | R | R | N | ||
19 | N | R | R | R | N | R | R | N | N | N | N | R | R | N | N | R | N | N | R | N | R | N | N | ||
23 | R | N | N | N | R | N | N | R | R | N | R | N | R | N | R | N | N | R | R | N | N | N | N | ||
29 | N | R | R | N | R | N | N | R | N | N | N | N | N | R | R | N | R | R | N | N | R | N | N | ||
31 | N | R | R | N | N | N | R | N | N | N | R | N | R | N | R | N | R | R | N | N | N | N | R | ||
37 | R | N | R | R | N | N | N | N | N | N | R | N | R | R | N | N | R | R | R | N | R | N | N | ||
41 | N | R | N | N | N | N | N | R | N | R | R | R | N | N | R | R | N | N | R | N | R | N | N | ||
43 | N | N | N | R | R | R | N | R | N | R | N | R | R | R | R | N | R | N | N | R | R | N | R | ||
47 | R | N | R | N | N | R | N | N | N | N | R | N | N | R | R | R | N | R | N | R | R | R | R | ||
53 | N | N | R | R | R | R | N | N | R | N | R | N | R | R | R | N | N | N | N | N | N | R | R | ||
59 | R | R | R | N | N | R | R | N | R | N | N | R | N | N | R | N | N | R | N | R | N | N | N | ||
61 | R | R | N | N | R | N | R | N | N | N | N | R | N | R | N | N | N | N | R | N | R | N | R | ||
67 | N | N | N | N | N | R | R | R | R | N | R | N | N | R | N | R | N | R | R | N | R | R | N | ||
71 | R | R | N | N | N | N | R | N | R | N | R | N | R | N | N | N | N | N | R | R | R | R | N | ||
73 | R | N | N | N | N | N | R | R | N | N | R | R | N | N | N | N | R | R | R | R | N | R | R | ||
79 | N | R | N | R | R | N | R | R | N | R | N | N | N | N | N | N | N | R | N | R | R | R | R | ||
83 | R | N | R | R | N | R | N | R | R | R | R | R | N | N | N | R | R | N | N | N | N | N | N | ||
89 | N | R | N | R | N | R | N | N | N | N | N | N | N | R | R | N | N | R | R | R | R | N | R | ||
97 | R | N | N | R | N | N | N | N | N | R | N | N | R | R | R | N | R | N | N | R | R | N | R |
觀察上表中黃格的情況,可以看出相對應的兩個質數都是模4餘3的。因此勒讓德的陳述為:
- 如果 或者 那麼
- 可解若且唯若 可解。
- 如果 那麼
- 可解若且唯若 不可解。
研究歷史
二次互反律曾被不少的數學家研究,因此二次互反律的敘述有很多種。要注意的是當時的數學記號並不統一。歐拉和勒讓德並沒有高斯的同餘記號,高斯也不知道勒讓德符號。
下文中的和总是不相等的正奇质数。
費馬曾經證明了[4](或聲稱證明了[5])一系列關於將質數表示成平方和的定理
- 若且唯若 或
- 若且唯若 或
- 若且唯若 或
他並沒有給出二次互反律的陳述,儘管由此類的定理可以得到–1、±2和±3的情況。
- 如果 那麼
- 如果 那麼
證明費馬的這類命題是導致二次互反律的發現的因素之一。
1) 如果 那麼是模的二次剩餘若且唯若,其中是一個模的二次剩餘。
2) 如果 那麼是模的二次剩餘若且唯若, 其中為奇數但不被整除。
勒讓德用和表示模4餘1的正質數,用和表示模4餘3的正質數。他建立了一個有8個定理的表格,這8個定理合起來就是二次互反律[10]。
定理 | 如果 | 則有 |
---|---|---|
I | ||
II | ||
III | ||
IV | ||
V | ||
VI | ||
VII | ||
VIII |
勒讓德認為表達式出現了太多次,可以簡寫為:
其中、為互質的數[11]。
這個符號就是現在使用的勒讓德符號[12]: 對於所有的整數以及任意奇質數:
如果整除; 如果是模的二次剩餘且不整除 如果是模的二次非剩餘。
- .
- ;
- .
- .
勒讓德使用勒讓德符號的敘述為:
- ,如果 或
- ,如果
他也提到上面的兩種情況可以合併為:
勒讓德完整地證明了八種情況中的第一、第二和第七種。在證明第八種情況時,勒讓德作了一個可以等價於狄利克雷定理的假設。正如高斯在其《算術研究》中指出的。勒讓德實際上證明了二次互反律是狄利克雷定理成立的情況下的一個推論[13]。

第一個完整地給出二次互反律的證明的人是德國數學家高斯。高斯在1796年給出了二次互反律的第一個證明[14]。高斯首先證明了[15] -1和2的情況。作為進行數學歸納法的開始,他證明了[16]±3和±5的情況。他注意到-3和+5的情況較有規律,容易敘述[17],因此把定理敘述為[18]:
如果 是形式為,那麼 (如果 是形式為那麼)是模每個為模的二次剩餘(非剩餘)的質數的二次剩餘(非剩餘)。
在下一句中,高斯將其列為「基本定理」(但沒有用到「互反律」的稱謂)。
在引進()表示是模的二次剩餘(非剩餘)後,高斯令和表示模4餘1的質數,用和表示模4餘3的,於是寫出了勒讓德得到的8種情況:
情況 | 如果 | 那麼 |
---|---|---|
1) | ±a R a′ | ±a′ R a |
2) | ±a N a′ | ±a′ N a |
3) | +a R b –a N b |
±b R a |
4) | +a N b –a R b |
±b N a |
5) | ±b R a | +a R b –a N b |
6) | ±b N a | +a N b –a R b |
7) | +b R b′ –b N b′ |
–b′ N b +b′ R b |
8) | –b N b′ +b R b′ |
+b′ R b –b′ N b |
在接下來的文章中他將其推廣到關於所謂的雅可比符號,以下的大寫字母表示的意思和相應的小寫字母一樣,但不再是質數。
情況 | 如果 | 那麼 |
---|---|---|
9) | ±a R A | ±A R a |
10) | ±b R A | +A R b –A N b |
11) | +a R B | ±B R a |
12) | –a R B | ±B N a |
13) | +b R B | –B N b +N R b |
14) | –b R B | +B R b –B N b |
最後他分各種情況分別運用強數學歸納法將其證明[19]。
證明中高斯用到了[20]一個引理:
如果 是質數,那麼存在奇質數 使得
如果使用勒讓德符號,那麼高斯的陳述就是
- 令,也就是說 且 。
- 那麼
高斯一生中給出了二次互反律的八個證明,其中他最為滿意的是第五個證明。
其它陳述
- 如果 那麼 [21]
- 如果 並且 那麼
- 令 和 為整數,那麼對每個整除 的質數有:
- 如果 有一個非平凡解,那麼
- 也有。
關於雅可比符號的互反律
雅可比符號是勒讓德符號的一個推廣,與後者主要的區別是「分母」只需為正奇數,而不需要一定是質數。當「分母」為質數時,兩者意義相同。雅可比符號的運算規律與勒讓德符號相同,即:
如果兩個數都是正奇數,那麼二次互反律對雅可比符號也成立:
然而,當雅可比符號為+1,「分母」為合數時,「分子」不一定是「分母」的二次剩餘。高斯的第九至十四種情況可以被表示為:
由於為質數,上式左邊是勒讓德符號,於是我們可以知道是否是模的剩餘。
以上各節的公式對雅可比符號仍然成立。歐拉的公式可以寫作:
其中為整數,
舉例來說:
2是模7、23、31的剩餘,但2是模5的非剩餘,因此也不是模15的。這與勒讓德提出過的一個問題有關:若已知 ,我們知道是模、、……中所有質數的非剩餘,如果這種質數存在的話。但此種質數的存在性直到數十年後才由狄利克雷證明。
艾森斯坦的公式則需要兩數互質才能成立: 如果 是正奇數,且 ,那麼
如果 且 ,則
使用希爾伯特符號的互反律
二次互反律也可以用希爾伯特符號: 來敘述。其中、是兩個非零的有理數,則可代表任意非平凡的有理數絕對值(的常用的或p進的絕對值)。希爾伯特符號: 的值取1或−1。按照定義,它的值取1若且唯若方程在有理數關於的完備空間中有除了之外的解。希爾伯特二次互反律聲稱:對於固定的、,當變動時,除了對有限個以外,的值都是1,並且取遍所有時,所有 的乘積為1(這與複分析中的留數定理相似)。
希爾伯特二次互反律的證明可以歸結到幾個特殊情況,可以證明其中非平凡的情況與勒讓德符號下的二次互反律的兩個輔助定理(-1和2的情況)是等價的。在希爾伯特二次互反律中其實並沒有「互反」的情形,它的名字只是表明它的歷史來源是作為二次互反律的研究成果。不同於二次互反律要考慮正負問題,並要區分2的情況,希爾伯特二次互反律對所有的有理數都是平等的。因此使用希爾伯特符號的二次互反律推廣起來更為自然:其推廣到整體域時只需做出很少改變,並對所有的整體域都適用[24]。
應用
以二次互反律配合以下兩個輔助定理
即能迅速地計算勒讓德符號,從而解決二次剩餘的判別問題。
例如判別37是否是模89的二次剩餘:
所以
因此37不是模89的二次剩餘。
推廣
二次互反律的推廣主要是在代數數論中。
例如:高斯考察過四次互反律。在他的[25]首篇論文裡他證明了一系列定理,其中最重要的是:如果,那麼有解若且唯若,其中、是整數,如果,那麼有解若且唯若,其中、是整數,如果,那麼有解若且唯若,其中、是整數,如果,那麼模的二次剩餘必然是四次剩餘。
在第二篇論文中[26],高斯引進了著名的高斯整數。高斯證明了模4餘1的質數總能分解為兩個高斯整數中質數的乘積、唯一分解定理等其它代數數論的基礎定理,並引進了一些基本概念,如範數和單位元。在高斯整數中,四次互反律的敘述十分簡單。高斯並且注意到在艾森斯坦整環中,三次互反律最為簡單。一部分的原因是高斯整數中1有4個四次方根,而艾森斯坦整數中1有3個三次方根。
其它的推廣是在以上整環中的二次互反律。高斯率先研究了高斯整數中的二次互反律[27]。
參見
注釋及參考來源
外部連結
Wikiwand - on
Seamless Wikipedia browsing. On steroids.