二次剩余的判定及應用 本文檔格式為 WORD,感謝你的閱讀。 【摘 要】通過討論形式如 x2a （ mod m）的同余式，引出二次剩余的概念，應用數論中常用的函數（勒讓德符號和雅可比符號）去討論二次同余式中 m 是單質數的情形和一般的情形，并利用其解二次同余式。 【關鍵詞】二次剩余；二次同余式；勒讓德符號；二次反轉定律 Second remaining judgement and application Lv Xiao-mei 【 Abstract】 Through the discussion form like x2a （ mod m） congruence type， leads to second remaining concept， application of the general functions （ theory， Legendre symbols and Jacobi symbols） to discuss the second congruence type in the number of elemental m is condition and the general situation， this paper briefly introduces solutions second congruence type equations. 【 Key words】 Second remaining； second congruence type equations； Legendre symbols； Second reverse law 引 言 數論是數學本科的基礎課程之一，是學習數 學的必修課程之一。數論問題的豐富性，多樣性及解題所具有的高度技巧對培養靈活創新的思維品質，邏輯思維，發散思維能力，系統的掌握各種數學思維，都是必不可少的。本文針對數論中一般二次同余式的解法問題進行總結概括。為了找到更為簡單，有效地解一般二次同余式的方法，主要通敘述定理和舉例，總結說明了歐拉判別條件，勒讓德符號在解一般二次同余式時的具體應用以及一般二次同余式的解和解數問題。 1. 一般二次同余式 二次同余式最基本的形式： （ 1） x2a （ mod m），（ a， m） =1 二次剩余。 我們已經知道，解同余式（ 1）歸結到 m 為素數的情形，因為 m=2 時，解同余式（ 1）變得極為容易，所以著重討論 m=p 的情形，這里 p 是一個奇素數。 定義 1 ：設 m 1，若（ 1）有解，則 a 叫做模 m 的二次剩余；若無解，則 a 叫做模 m 的二次非剩余。 2. 單質數的二次剩余的判定 2.1 歐拉判別條件。 討論 p 是單質數的二次剩余和二次非剩余，即討論形如： x2a （ mod p），（ a， p） =1 定理 1（歐拉判別條件）且 （ a， p） =1，則 a 是模 p的二次剩 余的充分與必要條件是： ap-121 （ mod p） （ 2） 而 a 是模 p 的二次非剩余的充分與必要條件是： ap-12 -1（ mod p） 且若 a 是模 p 的二次剩余，則（ 2）式恰有二解。 例 1 利用定理 1 來判斷： （ i） 3 是不是模 17的二次剩余； （ ii） 7 是不是模 29的二次剩余。 解： 由 3310 （ mod 17）， 3430 -4（ mod 17）， 38 -1（ mod 17）知， 3 是模 17的二次非剩余。 由 72 -9（ mod 29）， 73 -5（ mod 29）， 76 -4（ mod 29）， 771 （ mod 29）， 7141 （ mod 29）知， 7 是模 29的二次剩余。 2.2 勒讓德符號。 歐拉判別條件是適用于 p 比較小時，很難實際運用，我們引入勒讓德符號，再給出一個便于實際計算的方法。 定義 2 ：勒讓德符號 （ ap）（讀作 a 對 p 的勒讓德符號）是一個對于給定的單質數 p 定義在一切整數 a 上的函數，它的值規定如下： （ ap） =1， a 是模 p 的二次平方剩余； -1， a 是模 p 的二次平方非剩余 ； 0， p|a. 利用引進的勒讓德符號，定理 2 可表述為勒讓德符號的性質。 定理 2 勒讓德符號有以下性質： a） （ ap） =（ a+dp）； b） （ ap） a （ p-1） 2（ mod p）； c） （ ap） =（ a1p）； d） （ a1a2anp ） =（ a1p）（ a2p） （ anp）； e） 當 pd時，（ d2p） =1； f） （ 1p） =1；（ -1p） =（ -1）（ p-1） 2； g） （ 2p） =（ -1）（ p2-1） 8. 例 2 判斷同余方程 x2 -1（ mod 137） 是否有解。 解 因為 137 是素數，可以計算勒讓德符號如下： （ -1137） =（ -1） 137-12=1，所以方程有解。 例 3 判斷方程 x25 （ mod 11） 有沒有解。 解 由定理 2，因為（ 511） 511 -12=555 545 321 （ mod 11），方程有解。 2.2.1 二次反轉定律。 以下要對勒讓德符號和二次剩余做進一步的研究。以下，總以 p 表示奇素數。 引理 1 設（ n， p） =1，對于整數 k（ 1kp-12，以 rk 表示 nk對模 p 的最小非負剩余。設在 r1， r2， rp -12中大于p2的有 m 個，則 （ np） =（ -1） m。 定理 3 下面的結論成立： （ ） （ 2p） =（ -1） p2-18； （ ） 若 n 是奇數，（ n， p） = 1，則 （ np） =（ -1） li=1nip ， 其中 l=p-12 . 推論 設 p 是素數，則 （ 2p） =1，當 p1 （ mod 8）， -1，當 p3 （ mod 8）。 定理 4（二次互反律） 設 p 與 q 是不相同的兩個素數，則 （ qp） =（ -1） p-12 q-12 （ pq）。 例 4 判斷同余式 x2438 （ mod 593）是否有解。 解 因為 593 是質數，且 438=2 3 73，故 （ 438593） =（ 2593）（ 3593）（ 73593） 因為 5931 （ mod 8），再次利用二次反轉定律和前面的相關性質，有 （ 438593） =（ 5933）（ 59373） =（ 23）（ 973） =-1 故 438 是模 593 的二次非剩余，因而原同余式無解。 2.3 雅可比符號。 為避免計算勒讓德符號 的標準分解式是帶來的麻煩，引進雅可比符號。 定義 3 雅可比符號（ am）（讀作 a 對 m 的雅可比符號）是一個對于給定的大于 1 的單整數 m 定義在一切整數 a上的函數，它在 a 上的函數值是 （ am） =（ ap1）（ ap2） （ apr） 其中 m=p1p2pr ， pi 是質數，（ api）是 a 對 pi的勒讓德符號。 例 5 m = 45 = 3 3 5，則 （ 245） =（ 23）（ 23）（ 25） =（ 25） =（ -1） 52-18=-1， （ 2845） =（ 283）（ 283）（ 285） =（ 35） =（ -1） 3-12 5-12（ 53） =（ 23） =-1。 注 1：當 m 是奇素數時，雅可比符號就是勒讓德符號。前者是后者的推廣。 注 2：如果 m 是奇素數，當 （ am） = 1 時，方程（ 1）有解。當 m 不是奇素數時，這個結論不一定成立。例如，方程 x25 （ mod 9）無解，但是 （ 59） =（ 53）（ 53） = 1。 盡管如此，利用雅可比符號仍可對方程（ 5）的無解性給出判斷。事實上，如果方程（ 1）有解， m = p1ppk ，則對于每個 pi（ 1ik），當 p = pi 時方程（ 1）有解，因此，由雅可比符號的定義可知 （ am） = 1。這樣，若 （ am） = -1，則方程（ 1）必無解。 下面，我們研究雅可比符號的計算方法。 定理 5 使用定義 1 中的符號，下面的結論成立： （ ） 若 aa1 （ mod m） ，則 （ am） =（ a1m）； （ ） （ 1m） = 1； （ ） 對于任意的整數 a1a2at ，有 （ a1a2atm ） =（ a1m）（ a2m） （ atm）； （ 20） （ ） 對于任意的整數 a、 b ，（ a， m） =1，有 （ a2bm） =（ bm）。 例 6 已知 3371 是素數，判斷方程 x212345 （ mod 3371）是否有解。 解 利用雅可比符號的性質，有 （ 123453371） =（ 22323371） =（ 23371） （ 43371） （ 2793371） =（ -1） 33712-18（ -1） 3371-12 279-12（ 23279） =（ 23279） =（ -1） 279-12 23-12（ 27923） =-（ 323） =-（ -1） 23-12 3-12（ 233） =-1。 因此，方程本題無解。 3. 合數模的二次同余式 對于（ 1）式，若 m 是合數，可把 m 寫成分解式：m=2p11p22pnn. 因此，（ 1）有解的充分與必要條件是同余式組 x2 a （ mod 2 ）， x2 a （ mod pii ） =1，2， ， k （ 3） 有解，并且在有解的情況下，（ 1）的解數是（ 3）中各式解數的乘積，因此，首先討論同余式 x2 a （ mod p ）， 0，（ a， p） =1 （ 4） 開始。 定理 6 （ 4）有解的充分與必要條件是（ ap） =1，并且在有解的情況下，（ 4）式的解數是 2. 接下來討論同余式 x2 a （ mod 2 ）， 0 ，（ 2， a） =1 （ 5） 的解。首先可以看出，當 =1 時，（ 5）永遠有解，并且解數是 1.因此只討論 1 的情形。 定理 7 設 1 則（ 5）有解的必要條件是 （ i） 當 =2 時， a=1（ mod 4）； （ ii） 當 3 時， a=1（ mod 8） . 若上述條件成立，則（ 5）有解，并且當 =2 時，解數是 2；當 3 時，解數是 4. 例 7 解 x2 57 （ mod 64） 因為 57 1 （ mod 8），故有四解，把 x 寫成 x=（ 1+4t3） ，代入原同余式得到（ 1+4t3） 257 （ mod 16）。由此得 t31 （ mod 2），故 x= （ 1+4（ 1+2t4） = （ 5+8t4） 是適合 x2 57 （ mod 16）的一切整數，再代入同余式得到（ 5+8t4） 2 57 （ mod 32） 。由此得 t40（ mod 2），故 x= （ 5+8 2t5） = （ 5+16t5）是適合 x2 57 （ mod 32）的一切整數。仿前由（ 5+16t5） 257 （ mod 64）得到 t5=1（ mod 2），故 x= （ 5+16（ 1+2t6） =（ 21+36t6）是適合 x2 57 （ mod 16）的一切整數解，因此： x21 ， 53， -21， -53（ mod 64） 是所求的四個解。 結 論 二次剩余的判定問題等價于判斷一般二次同余式 x2a （ mod p），（ a， p） =1是否有解的問題。而當 p 取不同的數時，解決問題的方法 不同。本文針對不同情況，運用了不同的方法，從而更簡便地得出判斷結果。單質數的二次剩余判定可以利用歐拉判別條件，勒讓德符號和二次反轉定律，合數模的二次剩余也可以轉化成單質數的二次剩余進行判定。 參考文獻 1 祝龍 . 關于 Euler 數問題的一個注記 J. 安徽師范大學學報（自然科學版）， 2007 2 潘承桐 . 初等數論（第二版） M. 北京大學出版社 . 2003： 192 3 閔嗣鶴，嚴士健 . 初等數論（第三版） M.高等教育出版社 . 2009： 88-118 4 柯召 . 數論講義 M 高等教育出版社 . 2005 5 Neal Koblitz. 數論與密碼學教程（第二版） M. 世界圖書出版公司北京公司 . 2008： 43 6 葉文洪 . 關于二次剩余的一些結果 J. 信陽師范學院學報（自然科學版）， 1986 7 武勝利 . 二次剩余及其相關問題 J. 寶雞文理學院學報（自然科學版）， 1997 收稿日期： 2013-03-14 閱讀相關文檔 :結合體育運動學校的專業特點實施英語教 學 談如何優化課堂練習教學 如何有效培養小學生個性寫作 在初中英語教學中如何激發學生學習興趣 “ 教育回歸生活世界 ” 的話語分析 記憶周期應用于英語單詞網站的實驗研究 籃球后衛的作用與素質分析 太極樁相比于深蹲的抗疲勞