《數(shù)論算法》教案 4章(二次同余方程與平方剩余)

《《數(shù)論算法》教案 4章(二次同余方程與平方剩余)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、第4章二次同余方程與平方剩余內(nèi)容1.二次同余方程，平方剩余2.模為奇素?cái)?shù)的平方剩余3.勒讓德符號(hào)、雅可比符號(hào)4.二次同余方程的求解要點(diǎn)二次同余方程有解的判斷與求解4.1一般二次同余方程(一)二次同余方程＋bx＋c≡0（modm），（a0（modm））（1）(二)化簡(jiǎn)設(shè)m＝，則方程（1）等價(jià)于同余方程問(wèn)題歸結(jié)為討論同余方程＋bx＋c≡0（mod），（pa）（2）(三)化為標(biāo)準(zhǔn)形式p≠2，方程（2）兩邊同乘以4a，4＋4abx＋4ac≡0（mod）≡－4ac（mod）變量代換，y＝2ax＋b（3）有≡－4ac（mod）（4）當(dāng)p為奇素?cái)?shù)時(shí)，方程（4）與

2、（2）等價(jià)。即l兩者同時(shí)有解或無(wú)解；有解時(shí)，對(duì)（4）的每個(gè)解，通過(guò)式（3）（x的一次同余方程，且（p,2a）＝1，所以解數(shù)為1）給出（2）的一個(gè)解，由（4）的不同的解給出（2）的不同的解；反之亦然。l兩者解數(shù)相同。結(jié)論：只須討論以下同余方程≡a（mod）（5）【例】化簡(jiǎn)方程7x2＋5x－2≡0（mod9）為標(biāo)準(zhǔn)形式。（解）方程兩邊同乘以4a＝4×7＝28，得196x2＋140x－56≡0（mod9）配方(14x＋5)2－25－56≡0（mod9）移項(xiàng)(14x＋5)2≡81（mod9）變量代換y＝14x＋5得y2≡0（mod9）（解之得y＝0,±3，

3、從而原方程的解為x≡(y－5)≡(y－5)≡2(y－5)≡2y－10≡2y－1≡－7,－1,5≡－4,－1,2（mod9））(一)二次剩余【定義4.1.1】設(shè)m是正整數(shù)，a是整數(shù)，ma。若同余方程≡a（modm）（6）有解，則稱a是模m的平方剩余（或二次剩余）；若無(wú)解，則稱a是模m的平方非剩余（或二次非剩余）。問(wèn)題：（1）設(shè)正整數(shù)a是模p的平方剩余，若記方程（6）中的解為x≡（modm），那么此處的平方根（modm）與通常的代數(shù)方程＝a的解有何區(qū)別？（2）如何判斷方程（6）有解？（3）如何求方程（6）的解？(二)例【例1】1是模4平方剩余，－1是模

4、4平方非剩余?！纠?】1、2、4是模7平方剩余，3、5、6是模7平方非剩余?！纠?】直接計(jì)算12，22，…，142得模15的平方剩余（實(shí)際上只要計(jì)算（12，22，…，72）1，4，9，10，6平方非剩余：2，3，5，7，8，11，12，13，14【例4】求滿足方程E：≡＋x＋1（mod7）的所有點(diǎn)。（解）對(duì)x＝0，1，2，3，4，5，6分別解出y：＝0，≡1（mod7），y≡1，6（mod7）＝1，≡3（mod7），無(wú)解＝2，≡4（mod7），y≡2，5（mod7）＝3，≡3（mod7），無(wú)解＝4，≡6（mod7），無(wú)解＝5，≡5（mod7），無(wú)解

5、＝6，≡6（mod7），無(wú)解所以，滿足方程的點(diǎn)為（0,1），（0,6），（2,2），（2,5）。說(shuō)明：方程E：≡＋x＋1的圖形稱為橢圓曲線。4.1模為奇素?cái)?shù)的平方剩余與平方非剩余模為素?cái)?shù)的二次方程≡a（modp）,(a,p)＝1（1）因?yàn)椋?，故方程?）要么無(wú)解，要么有兩個(gè)解。(一)平方剩余的判斷條件【定理4.2.1】（歐拉判別條件）設(shè)p是奇素?cái)?shù)，(a,p)＝1，則（i）a是模p的平方剩余的充要條件是≡1（modp）（2）（ii）a是模p的平方非剩余的充要條件是≡－1（modp）（3）并且當(dāng)a是模p的平方剩余時(shí)，同余方程（1）恰有兩個(gè)解。（證）先證

6、pa時(shí)，式（2）或（3）有且僅有一個(gè)成立。由費(fèi)馬定理≡1（modp）－1≡0（modp）≡0（modp）（4）即＝但＝1或2且素?cái)?shù)p>2。所以，p能整除，但p不能同時(shí)整除和（否則，p能整除它們的最大公因子1或2）所以，由式（4）立即推出式（2）或式（3）有且僅有一式成立。（i）必要性。若a是模p的二次剩余，則必有使得≡a（modp），因而有≡（modp）。即（modp）。由于pa，所以p，因此由歐拉定理知≡1（modp）。即（2）式成立。充分性。已知≡1（modp），這時(shí)必有pa。故一次同余方程≡a（modp）,(1≤b≤p－1)（5）有唯一解，對(duì)

7、既約剩余系－(p－1)/2，…，－1，1，…，(p－1)/2（6）由式（6）給出的模p的既約剩余系中的每個(gè)j，當(dāng)b＝j(luò)時(shí)，必有唯一的屬于既約剩余系（6），使得式（5）成立。若a不是模p的二次剩余，則必有。這樣，既約剩余系（6）中的p－1個(gè)數(shù)就可按j、xj作為一對(duì)，兩兩分完。（b1≠b2，則相應(yīng)的解x1≠x2，且除了±1之外，每個(gè)數(shù)的逆不是它本身）因此有由威爾遜定理知與式（2）矛盾。所以必有某一，使，由此及式（5）知，a是模p的二次剩余。（ii）由已經(jīng)證明的這兩部分結(jié)論，立即推出第（ii）條成立。其次，若0（modp）是方程（1）的解，則－也是其解，

8、且必有－（modp）。故當(dāng)(a,p)＝1時(shí)，方程（1）要么無(wú)解，要么同時(shí)有兩個(gè)解。（說(shuō)明：本定理只是一個(gè)理論結(jié)果，當(dāng)p>>