研究一般的二次同餘式αx2+bx+с≡0(modm)，可歸結為討論形如

的同餘式，其其中 m＞1，( m， n)=1。若它有解，則 n叫作模 m的二次剩餘；若它無解，則 n叫作模 m的二次非剩餘。設 p是一個奇素數，在模 p的縮系中有 個二次剩餘和 個二次非剩餘，且 1 2， 2 2，…， 就是模 p的全部二次剩餘。如果 n是模 p的二次剩餘，則 ，如果 n是模 p的二次非剩餘，則

　　勒讓德符號與二次互反律　設p

n，當 n是模 p的二次剩餘，記為 ；當 n是模 p的二次非剩餘，記為 。符號 叫做勒讓德符號。它是 A.-M.勒讓德於1798年引入的，對於計算 n是否模 p的二次剩餘，帶來很大的方便。勒讓德符號有以下一些簡單的性質：①當 n≡ n′( mod p)時， ；②

；③ ， ；④

。因此，任給一個整數 n，隻需計算 ， ， （ q為奇素數）這三種值。1801年， C.F.高斯證明瞭以下結果：設 p是奇素數，（ p， n）=1，在 個數 n， 2 n，…， 模 p的最小正剩餘數中有 l個大於 ，則 ，一般叫做高斯引理。由高斯引理可知 。1801年，高斯還用這個引理證明瞭著名的二次互反律：設 p＞2， q＞2是兩個素數， p≠ q，則 ，這是 初等數論中至關重要的定理，它不僅能夠方便地計算勒讓德符號的值，而且在數論許多方面都非常有用。例：計算 ，因為438=2·3·73，所以 =

。二次互反律由L.歐拉首先提出，而由高斯於1796年首先證明。後來，各種證明不斷出現，迄今已有150多個不同的證明。高斯自己就給出瞭好幾個證明，其中第三個證明是運用高斯引理得出的。二次互反律引起許多數學傢對代數數域中高次互反律的研究，從而使得在這個方面出現瞭不少意義深刻的工作。

　　雅可比符號　設m是一個正奇數，m=p1…pt，pi(i=1，2，…，t)是素數，（m，n）=1，則

叫做雅可比符號。引入勒讓德符號，運用二次互反定律，可判斷二次同餘式是否有解，但計算時需要把一個正整數分解成標準分解式，而計算雅可比符號就不需要這樣做。利用勒讓德符號的性質，容易推得：① 和 。②若 m和 n是二正奇數，且( m， n)=1，則 。需要註意的是，當 時，則 x 2≡ n(mod m)無解，但當 時， x 2≡ n(mod m)不一定有解。

　　原根和指數　設h為一整數，n為正整數，(h，n)=1，適合hl≡1(modn)的最小正整數l叫做h對模n的次數。如果l=φ(n)，此時h稱為模n的原根。1773年，L.歐拉首先證明瞭素數p有原根存在。1785年，勒讓德證明瞭；設

，恰有 φ( l)個模 p互不同餘的數對模 p的次數為 l。1801年，高斯證明瞭： n有原根存在的充分必要條件是 n=2，4， p l， 2 p l，這裡 l≥1， p是奇素數。設 g是素數 p的一個原根，對任一整數 n，( n， p)＝1，必有一數 α使 n≡ g α(mod p)，0≤ α＜ p-1， α叫做 n對模 p的指數，以 α=i nd g n表示，在不致混淆時，簡寫成 α＝ind n，它具有與通常對數類似的性質。例如，如果 p α b，則in d α b≡ind α+ ind b(mo d p-1)。指數的引入，對於簡化問題有幫助。

　　估計模p的最小正原根的上界是著名的原根問題之一。設m為p-1的不同素因數的個數，g（p）表示模p的最小正原根，可證得

。運用更精密的方法，1959～1962年，D.A.伯吉斯與王元獨立地證明瞭

，其中ε為任意正數，而與“ ”有關的常數僅依賴於ε。另一個重要的原根問題是 E.阿廷在1927年提出的猜想：對於任意不等於1、 p-1及完全平方的正整數 α，必定存在無窮多個素數 p，以 α為原根。人們稱之為阿廷猜想。這一猜想尚未解決。

　　原根和指數可應用於代數編碼和數字信號處理等領域。例如，運用原根存在的定理，1968的，C.M.雷德證明瞭長為p的離散傅裡葉變換(DFT)可化為循環卷積，其中p為奇素數。後來人們還證明瞭長為pl和2pl的情形。

　　k次剩餘　設k＞1，m＞1，(m，n)=1，若二項同餘式xk≡n(modm)有解，則n叫做模m的k次剩餘；若無解，則n叫做模m的k次非剩餘。模m的情形可化為模pα的情形，α≥1，p是素數。p=2的情形是容易解決的。設p是一個奇素數，n是模pα的k次剩餘的充分必要條件是d=(k，φ(pα))整除indgn，其中g是模pα的一個原根。恰有

個模 p α互不同餘的 k次剩餘。當 d= k時，模 p α的 k次剩餘叫做真 k次剩餘；當 d＜ k時，模 p α的 k次剩餘叫做非真 k次剩餘。可以證明，非真 k次剩餘可以歸結為真 k次剩餘來研究，而模 p α的真 k次剩餘，又可歸結為模 p的真 k次剩餘來研究。因此，對於 k次剩餘，總可假定 。設 k＞1， p是一個奇素數， p-1= k q，定義符號 ，其中 n q( mod p)表示 n q模 p的絕對值最小的剩餘，符號 叫做模 p的 k次剩餘特征。容易證明： n是模 p的 k次剩餘當且僅當 。設 ，此時， n是模 p的 2 k次非剩餘當且僅當 。1801年，高斯證明瞭以下結果：設 p≡1(mod8)， p= α 2+ 4 b 2，則 的充分必要條件是 b≡0(mod4)。高斯關於二次互反律和四次剩餘的深入研究，對以後數論的發展，產生瞭很大的影響。代數數域中的高次互反律，即希爾伯特第9問題，從 F.G.M.艾森斯坦、 D.希爾伯特到 高木貞治、 E.阿廷，才最後得到解決。一個著名的經典結果是：設 p≡1(mod6)， 的充分必要條件是 p= α 2+27 b 2， α、 b是整數。對於給定的不太大的 n和 k， 的充分必要條件是 p具有什麼形狀，近年來一直有不少工作。1969年，K.伯德證明瞭：設 p= α 2+ b 2， q= X 2+ d 2， α≡с≡1(mod2)， b≡ d≡0(mod2)， α b＞0，с d＞0， p和 q是素數且 ，則 。

　　

參考書目

　K.Ireland and M.Rosen，A Classical Introduction to Modern Number Theory，Springer-Verlag.New York，1982.