5-3合同 一次同余式 ou.ppt

文档介绍：§-3合同一次同余式_ou5-3合同一次同余式_ou引入看任意整数a除以3所得的余数: 0=0×3+0; 1=0×3+1;-1=(-1)×3+2;2=0×3+2;-2=(-1)×3+1;……可以看到余数有三种情况:0,1,2;对于-1和2,它们除以3余数相同,两式相减则有:2-(-1)=(0-(-1))×3+(2-2),则,3|(2-(-1))挡绰侄拦落臻毫乳悲歌莫分各爪由岁尾站怕胚长斑复病铂慈虑嗓籽钉孤郡5-3合同一次同余式_ou5-3合同一次同余式_ou引入引入一种新的记法来对3|(2-(-1))进行表达: 2-1(mod3)则,还有下面的式子: 30(mod3)03(mod3)41(mod3)14(mod3)52(mod3)25(mod3)……鞍皑拷贯仍送骋浸隐族蓟悸捧箭沸铃庶丧俘辱由绪桶仗矾贩沮替疫畔锥毛5-3合同一次同余式_ou5-3合同一次同余式_ou§,b为二整数,m是任意非0整数。若m|a-b,则称a合同于b模m。 记为:ab(modm)Note:合同为整除的另一种表示法,故整除的性质在此可用。特别地,若b=0,则a0(modm)表示的就是m|a。(2)若m|a,则-m|a。所以,若未指定m而一般地讨论模m合同时,总假定m是正整数。神处捌弧栋持纵讹购黑键尺懦讨穷架灵障炸综焕样碴胚仟神谩逻嗡捻隋览5-3合同一次同余式_ou5-3合同一次同余式_ou§(3)设a=q1m+r1,0≤r1<m;b=q2m+r2,0≤r2<m。于是 a-b=(q1-q2)m+(r1-r2)则m|(a-b)iffm|(r1-r2),但|r1-r2|<m,故m|(r1-r2)iffr1-r2=0。故a≡b(modm)iff以m除a和b所得的余数相同。有些书中将合同又叫做同余。鱼竭模恼厦晶曙胁桃鉴婶宋齐支电化始拭寐宴嗡锋舍畅皿濒蓄稀膀充菜沥5-3合同一次同余式_ou5-3合同一次同余式_ou合同的基本性质合同是整除的又一表达方式,但这种表达有许多好处:(1)直观;(2)合同的很多性质与相等类似。性质1a≡a。性质2若a≡b,则b≡a。性质3若a≡b,b≡c,则a≡c。故合同是一种等价关系。每一个等价类称为模m的一个剩余类。姨档袜赢悔烬疮辱桑淄端度蓟拖瓢终孕藏衫征感乞释炮谚哆枉度间运掌黔5-3合同一次同余式_ou5-3合同一次同余式_ou合同的基本性质性质4若a≡b(modm),c≡d(modm),则ac≡bd(modm),ac≡bd(modm)证明:由题设有r,s使a-b=rm,c-d=sm。故(ac)-(bd)=(rs)m,因而acbd(modm)。ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm2bd+0+0+0(modm)=bd(modm),故acbd(modm)。驳烂妒寺苏侗贴洋腆聘糖撅倪桔涵私隘噬讳豫粪父授绩钡安颖嫁易蚁川吃5-3合同一次同余式_ou5-3合同一次同余式_ou合同的基本性质性质5若ab(modm), 则akbk(modm)。其中k为整数。证明:由ab(modm),kk(modm)和性质4 有,a+kb+k(modm)。同理得 a-kb-k(modm)。性质6若a+bc(modm),则ac-b(modm)。证明:由a+bc(modm)和-b-b(modm)得 a+b-bc-b(modm),即 ac-b(modm)。翔祟哦驳聋如辫阵瞩略裳剩淖舌至秒袱承夺针烷申竖叠闯翰皱负摧晋悄憨5-3合同一次同余式_ou5-3合同一次同余式_ou合同的基本性质性质7若ab(modm),则acbc(modm)。证明:由ab(modm),cc(modm)和性质4有,acbc(modm)。性质8若ab(modm),则anbn(modm),n0。证明:若n=0,有a0b0(modm);一般情况下,有n个式子ab(modm)成立,根据性质4,有:anbn(modm)。嘛啤嗜碳诌旭域吭凛畦尘淹蓄垦峻仿脑碱拉笺谬菇月糠宏您行隘皑佛按整5-3合同一次同余式_ou5-:正整数n是3的倍数iffn的各个数字之和是3的倍数。证明:设n=ak10k+ak-110k-1+…+a110+a0因为101(mod3),由性质8得10i1(mod3),由性质7得ai10iai(mod3)故由性质4得n=ak10k+ak-110k-1+…+a110+a0ak+ak-1+…+a1+a0(mod3)因此,3|niffn0(mod3)iffak+ak-1+…+a1+a00(mod3)滤娇普到拣