離散數(shù)學(xué)-11.3-5同余.ppt
《離散數(shù)學(xué)-11.3-5同余.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-11.3-5同余.ppt（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1,11.3同余,同余模算術(shù)運算模m等價類,2,同余,定義11.5設(shè)m是正整數(shù),a和b是整數(shù).如果m|a?b,則稱a模m同余于b,或a與b模m同余,記作a≡b(modm).如果a與b模m不同余,則記作ab(modm).例如,15≡3(mod4),16≡0(mod4),14≡?2(mod4),1516(mod4).下述兩條都是a與b模m同余的充分必要條件:(1)amodm=bmodm.(2)a=b+km,其中k是整數(shù).,3,同余(續(xù)),性質(zhì)11.3.1同余關(guān)系是等價關(guān)系,即同余關(guān)系具有①自反性.a≡a(modm)②傳遞性.a≡b(modm)∧b≡c(modm)?a≡c(modm).③對稱性.a≡b(modm)?b≡a(modm).縮寫a1≡a2≡…≡ak(modm).性質(zhì)11.3.2(模算術(shù)運算)若a≡b(modm),c≡d(modm),則ac≡bd(modm),ac≡bd(modm),ak≡bk(modm),其中k是非負整數(shù).性質(zhì)11.3.3設(shè)d≥1,d|m,則a≡b(modm)?a≡b(modd).性質(zhì)11.3.4設(shè)d≥1,則a≡b(modm)?da≡db(moddm).性質(zhì)11.3.5設(shè)c,m互素,則a≡b(modm)?ca≡cb(modm).,4,模m等價類,模m等價類:在模m同余關(guān)系下的等價類.[a]m,簡記作[a].Zm:Z在模m同余關(guān)系下的商集在Zm上定義加法和乘法如下:?a,b,[a]+[b]=[a+b],[a][b]=[ab].,例1寫出Z4的全部元素以及Z4上的加法表和乘法表.,解Z4={[0],[1],[2],[3]},其中[i]={4k+i|k∈Z},i=0,1,2,3.,[0][1][2][3][1][2][3][0][2][3][0][1][3][0][1][2],[0][0][0][0][0][1][2][3][0][2][0][2][0][3][2][1],5,實例,例23455的個位數(shù)是多少?,解設(shè)3455的個位數(shù)為x,則3455≡x(mod10).,由34≡1(mod10),有3455=34?113+3≡33≡7(mod10),故3455的個位數(shù)是7.,6,實例,例3(續(xù))例如,中華人民共和國成立日1949年10月1日,C=19,X=49,M=8,d=1,是星期六.中國人民抗日戰(zhàn)爭勝利日1945年8月15日,C=19,X=45,M=6,d=15,是星期三.,7,11.4一次同余方程,11.4.1一次同余方程模m逆11.4.2中國剩余定理11.4.3大整數(shù)算術(shù)運算,8,一次同余方程,定理11.9方程ax≡c(modm)有解的充要條件是gcd(a,m)|c.證充分性.記d=gcd(a,m),a=da1,m=dm1,c=dc1,其中a1與m1互素.由定理11.8,存在x1和y1使得a1x1+m1y1=1.令x=c1x1,y=c1y1,得a1x+m1y=c1.等式兩邊同乘d,得ax+my=c.所以,ax≡c(modm).必要性.設(shè)x是方程的解,則存在y使得ax+my=c.由性質(zhì)11.1.1,有d|c.,一次同余方程:ax≡c(modm),其中m>0.一次同余方程的解:使方程成立的整數(shù)例如,2x≡0(mod4)的解為x≡0(mod2),2x≡1(mod4)無解,9,實例,例1解一次同余方程6x≡3(mod9).解gcd(6,9)=3|3,方程有解.取模9等價類的代表x=?4,?3,?2,?1,0,1,2,3,4,檢查它們是否是方程的解,計算結(jié)果如下:6(?4)≡6(?1)≡62≡3(mod9),6(?3)≡60≡63≡0(mod9),6(?2)≡61≡64≡6(mod9),得方程的解x=?4,?1,2(mod9),方程的最小正整數(shù)解是2.,10,模m逆,定理11.10(1)a的模m逆存在的充要條件是a與m互素.(2)設(shè)a與m互素,則在模m下a的模m逆是惟一的.證(1)這是定理11.9的直接推論.(2)設(shè)ab1≡1(modm),ab2≡1(modm).得a(b1?b2)≡0(modm).由a與m互素,b1?b2≡0(modm),得證b1≡b2(modm).,定義11.6如果ab≡1(modm),則稱b是a的模m逆,記作a?1(modm)或a?1.a?1(modm)是方程ax≡1(modm)的解.,11,實例,例2求5的模7逆.,解5與7互素,故5的模7逆存在.,方法1.解方程5x≡1(mod7).,檢查x=?3,?2,?1,0,1,2,3,得到5?1≡3(mod7).,方法2.做輾轉(zhuǎn)相除法,求得整數(shù)b,k使得5b+7k=1,則b是5的模7逆.,計算如下:7=5+2,5=22+1.回代1=5?22=5?2(7?5)=35?27,得5?1≡3(mod7).,12,實例,例2(續(xù)),方法3.直接觀察,5?3=15,15?1(mod7),得5?1≡3(mod7).,13,中國剩余定理(孫子定理),定理11.11(中國剩余定理)設(shè)正整數(shù)m1,m2,…,mk兩兩互素,則一次同余方程組x≡ai(modmi),i=1,2,…,k有整數(shù)解,并且在模m=m1m2…mk下解是惟一的,即任意兩個解都是模m同余的.,《孫子算經(jīng)》“物不知數(shù)”問題:今有物,不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何?x≡2(mod3)x≡3(mod5)x≡2(mod7),14,中國剩余定理的證明,假設(shè)則x=x1+x2+…+xk是所求的解.令Mi=m/mi,i=1,2,…,k.設(shè)xi=Miyi,應(yīng)該有Miyi≡ai(modmi).因為mi與所有的mj(j≠i)互素,mi與Mi也互素,所以Mi有模mi逆,設(shè)為Mi?1.取yi=aiMi?1,則xi=Miyi=aiMi?1Mi滿足要求.得方程組的解x=a1M1?1M1+a2M2?1M2+…+akMk?1Mk,15,最后,證明惟一性.設(shè)同余方程組有兩個解c1和c2,則對每一個i,c1和c2模mi同余,即mi|c1?c2.又m1,m2,…,mk兩兩互素,故有m|c1?c2,即c1和c2模m同余.,中國剩余定理的證明(續(xù)),16,設(shè)正整數(shù)m1,m2,…,mk兩兩互素,一次同余方程組x≡ai(modmi),i=1,2,…,k(1)計算m=m1m2…mk(2)計算Mi=m/mi=m1…mi?1mi+1…mk,i=1,2,…,k(3)計算Mi?1(modmi),i=1,2,…,k(4)計算x≡a1M1?1M1+a2M2?1M2+…+akMk?1Mk(modm),一次同余方程組的求解步驟,17,實例,例3解“物不知數(shù)”問題,即求下述方程組的正整數(shù)解:x≡2(mod3),x≡3(mod5),x≡2(mod7),解這里m1=3,m2=5,m3=7,m=105.M1=57=35,M1≡2(mod3),M1?1=2.M2=37=21,M2≡1(mod5),M2?1=1.M3=35=15,M3≡1(mod7),M3?1=1.x≡2235+3121+2115≡233≡23(mod105).解為105k+23,k=0,1,2,….最小正整數(shù)解是23.,18,大整數(shù)算術(shù)運算,設(shè)m1,m2,…,mk大于1且兩兩互素,m=m1m2…mk.對任意的0≤x下載提示(請認(rèn)真閱讀)
- 1.請仔細閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認(rèn)領(lǐng)！既往收益都歸您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 離散數(shù)學(xué) 11.3
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
相關(guān)搜索
鏈接地址：http://m.jqnhouse.com/p-3494356.html