二次剩余的判定及應(yīng)用[權(quán)威資料]

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