資源描述：
《《數(shù)論算法》教案 4章(二次同余方程與平方剩余)》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、《數(shù)論算法》第四章二次同余方程與平方剩余第4章二次同余方程與平方剩余內容1.二次同余方程，平方剩余2.模為奇素數(shù)的平方剩余3.勒讓德符號、雅可比符號4.二次同余方程的求解要點二次同余方程有解的判斷與求解4.1一般二次同余方程(一)二次同余方程＋bx＋c≡0（modm），（a0（modm））（1）(二)化簡設m＝，則方程（1）等價于同余方程問題歸結為討論同余方程＋bx＋c≡0（mod），（pa）（2）(三)化為標準形式p≠2，方程（2）兩邊同乘以4a，4＋4abx＋4ac≡0（mod）≡－4ac（mod）49/49《數(shù)論算法》第四章二次同余方程與平方剩余變量代換，y＝
2、2ax＋b（3）有≡－4ac（mod）（4）當p為奇素數(shù)時，方程（4）與（2）等價。即l兩者同時有解或無解；有解時，對（4）的每個解，通過式（3）（x的一次同余方程，且（p,2a）＝1，所以解數(shù)為1）給出（2）的一個解，由（4）的不同的解給出（2）的不同的解；反之亦然。l兩者解數(shù)相同。結論：只須討論以下同余方程≡a（mod）（5）【例】化簡方程7x2＋5x－2≡0（mod9）為標準形式。（解）方程兩邊同乘以4a＝4×7＝28，得196x2＋140x－56≡0（mod9）配方(14x＋5)2－25－56≡0（mod9）移項(14x＋5)2≡81（mod9）變量代換y＝
3、14x＋5得y2≡0（mod9）（解之得y＝0,±3，從而原方程的解為x≡(y－5)≡(y－5)≡2(y－5)≡2y－10≡2y－1≡－7,－1,5≡－4,－1,2（mod9））49/49《數(shù)論算法》第四章二次同余方程與平方剩余(一)二次剩余【定義4.1.1】設m是正整數(shù)，a是整數(shù)，ma。若同余方程≡a（modm）（6）有解，則稱a是模m的平方剩余（或二次剩余）；若無解，則稱a是模m的平方非剩余（或二次非剩余）。問題：（1）設正整數(shù)a是模p的平方剩余，若記方程（6）中的解為x≡（modm），那么此處的平方根（modm）與通常的代數(shù)方程＝a的解有何區(qū)別？（2）如何判斷
4、方程（6）有解？（3）如何求方程（6）的解？(二)例【例1】1是模4平方剩余，－1是模4平方非剩余。【例2】1、2、4是模7平方剩余，3、5、6是模7平方非剩余?！纠?】直接計算12，22，…，142得模15的平方剩余（實際上只要計算（12，22，…，72）1，4，9，10，6平方非剩余：2，3，5，7，8，11，12，13，14【例4】求滿足方程E：≡＋x＋1（mod7）的所有點。（解）對x＝0，1，2，3，4，5，6分別解出y：＝0，≡1（mod7），y≡1，6（mod7）＝1，≡3（mod7），無解49/49《數(shù)論算法》第四章二次同余方程與平方剩余＝2，≡4（
5、mod7），y≡2，5（mod7）＝3，≡3（mod7），無解＝4，≡6（mod7），無解＝5，≡5（mod7），無解＝6，≡6（mod7），無解所以，滿足方程的點為（0,1），（0,6），（2,2），（2,5）。說明：方程E：≡＋x＋1的圖形稱為橢圓曲線。4.1模為奇素數(shù)的平方剩余與平方非剩余模為素數(shù)的二次方程≡a（modp）,(a,p)＝1（1）因為＝，故方程（1）要么無解，要么有兩個解。(一)平方剩余的判斷條件【定理4.2.1】（歐拉判別條件）設p是奇素數(shù)，(a,p)＝1，則（i）a是模p的平方剩余的充要條件是≡1（modp）（2）（ii）a是模p的平方非剩余
6、的充要條件是≡－1（modp）（3）并且當a是模p的平方剩余時，同余方程（1）恰有兩個解。（證）先證pa時，式（2）或（3）有且僅有一個成立。由費馬定理≡1（modp）－1≡0（modp）49/49《數(shù)論算法》第四章二次同余方程與平方剩余≡0（modp）（4）即＝但＝1或2且素數(shù)p>2。所以，p能整除，但p不能同時整除和（否則，p能整除它們的最大公因子1或2）所以，由式（4）立即推出式（2）或式（3）有且僅有一式成立。（i）必要性。若a是模p的二次剩余，則必有使得≡a（modp），因而有≡（modp）。即（modp）。由于pa，所以p，因此由歐拉定理知≡1（modp
7、）。即（2）式成立。充分性。已知≡1（modp），這時必有pa。故一次同余方程≡a（modp）,(1≤b≤p－1)（5）有唯一解，對既約剩余系－(p－1)/2，…，－1，1，…，(p－1)/2（6）由式（6）給出的模p的既約剩余系中的每個j，當b＝j時，必有唯一的屬于既約剩余系（6），使得式（5）成立。若a不是模p的二次剩余，則必有。這樣，既約剩余系（6）中的p－1個數(shù)就可按j、xj作為一對，兩兩分完。49/49《數(shù)論算法》第四章二次同余方程與平方剩余（b1≠b2，則相應的解x1≠x2，且除了±1之外，每個數(shù)的逆不是它本身）因此有由威爾遜定理知與式（2）矛盾。所
