二次剩餘

標籤: 暫無標籤

54

更新時間: 2013-09-12

廣告

研究一般的二次同餘式αx2+bx+с呏0(modm),可歸結為討論形如的同餘式,其中m>1,(m,n)=1。

廣告

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的二次剩餘,帶來很大的方便。勒讓德符號有以下一些簡單的性質:①當nn┡(modp)時,二次剩餘;②二次剩餘二次剩餘;③二次剩餘,二次剩餘;④二次剩餘二次剩餘。因此,任給一個整數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,則二次剩餘叫做雅可比符號。引入勒讓德符號,運用二次互反定律,可判斷二次同餘式是否有解,但計算時需要把一個正整數分解成標準分解式,而計算雅可比符號就不需要這樣做。利用勒讓德符號的性質,容易推得:①二次剩餘二次剩餘。②若m和n是二正奇數,且(m,n)=1,則二次剩餘。需要注意的是,當二次剩餘時,則x2n(mod m)無解,但當二次剩餘時,x2n(mod m)不一定有解。
  原根和指數  設h為一整數,n為正整數,(hn)=1,適合hl呏1(modn)的最小正整數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,必有一數α使ngα(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,若二項同餘式xkn(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=kq,定義符號二次剩餘,其中nq(modp)表示nq模p的絕對值最小的剩餘,符號二次剩餘叫做模p的k次剩餘特徵。容易證明:n是模p的k次剩餘當且僅當二次剩餘。設二次剩餘,此時,n是模p的2k次非剩餘當且僅當二次剩餘。1801年,高斯證明了以下結果:設p呏1(mod8),p =α2+4b2,則二次剩餘的充分必要條件是b呏0(mod4)。高斯關於二次互反律和四次剩餘的深入研究,對以後數論的發展,產生了很大的影響。代數數域中的高次互反律,即希爾伯特第9問題,從F.G.M.艾森斯坦、D.希爾伯特到高木貞治、E.阿廷,才最後得到解決。一個著名的經典結果是:設p呏1(mod6),二次剩餘的充分必要條件是p =α2+27b2,αb是整數。對於給定的不太大的nk二次剩餘的充分必要條件是p具有什麼形狀,近年來一直有不少工作。1969年,K.伯德證明了:設p =α2+b2,q=X2+d2α呏с呏1(mod2),bd呏0(mod 2),αb>0,сd>0,p 和q是素數且二次剩餘,則二次剩餘
  參考書目
 K.Ireland and M.Rosen,A Classical Introduction to Modern Number Theory,Springer-Verlag. New York,1982.

2 二次剩餘 -配圖

3 二次剩餘 -相關連接

廣告