什麼是二次剩餘

教育
關注：2.26K次

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

的同餘式，其中m>1，(m，n)=1。若它有解，則n叫作模m 的二次剩餘；若它無解，則n叫作模m 的二次非剩餘。設p 是一個奇素數，在模p的縮系中有

個二次剩餘和

個二次非剩餘，且12，22，…，

就是模p的全部二次剩餘。如果n是模p的二次剩餘，則

，如果n是模p的二次非剩餘，則

勒讓德符號與二次互反律

設p

n，當n是模p的二次剩餘，記為

；當n是模p 的二次非剩餘，記為

。符號

叫做勒讓德符號。它是 A.-M.勒讓德於1798年引入的，對於計算n是否模p的二次剩餘，帶來很大的方便。勒讓德符號有以下一些簡單的性質：

（1）當n呏n┡(modp)時，

；

（2）

；

（3）

，

；

（4）

。因此，任給一個整數 n，只需計算

，

（q 為奇素數）這三種值。1801年，C.F.高斯證明了以下結果：設p 是奇素數，（p，n）=1，在

個數n，2n，…，

模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，則

叫做雅可比符號。引入勒讓德符號，運用二次互反定律，可判斷二次同餘式是否有解，但計算時需要把一個正整數分解成標準分解式，而計算雅可比符號就不需要這樣做。利用勒讓德符號的性質，容易推得：

（1）

和

。

（2）若m和n是二正奇數，且(m，n)=1，則

。需要注意的是，當

時，則x2呏n(mod m)無解，但當

時，x2呏n(mod m)不一定有解。

原根和指數

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

，恰有φ(l)個模p互不同餘的數對模p 的次數為l。1801年，高斯證明了：n 有原根存在的充分必要條件是n=2，4，pl，2pl，這裏l≥1，p是奇素數。設g是素數p的一個原根，對任一整數n，(n，p)＝1，必有一數 α使n呏gα(modp)，0≤α<p-1，α叫做n對模p的指數，以α=indgn表示，在不致混淆時，簡寫成 α＝indn，它具有與通常對數類似的性質。例如，如果p

αb，則indαb呏indα+indb(modp-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α的一個原根。恰有