• / 51
  • 下载费用:10 金币  

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

关 键 词:
5-3合同 一次同余式_ou.ppt
资源描述:
§5.3 合同 一次同余式,,引入,看任意整数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)),引入,引入一种新的记法来对3|(2-(-1)) 进行表达:2 -1(mod 3)则,还有下面的式子:3  0(mod 3) 0  3(mod 3) 4  1(mod 3) 1  4(mod 3) 5  2(mod 3) 2  5(mod 3) … …,§5.3.1 合同及其性质,定义. 设a,b为二整数,m是任意非0整数。若 m|a-b,则称a合同于b 模m。 记为:ab(mod m) Note: 合同为整除的另一种表示法,故整除的性质在此可用。特别地,若b=0,则a0(mod m)表示的就是m|a。 (2) 若m|a,则- m|a。所以,若未指定m而一般地讨论模m合同时,总假定m是正整数。,§5.3.1 合同及其性质,(3)设a=q1m+r1,0≤r1m;b=q2m+r2,0≤r2m。于是 a-b=(q1-q2)m+(r1-r2) 则 m|(a-b) iff m|(r1-r2),但|r1-r2|m,故m|(r1-r2) iff r1-r2=0。 故 a≡b(mod m) iff 以m除a和b所得的余数相同。 有些书中将合同又叫做同余。,合同的基本性质,合同是整除的又一表达方式,但这种表达有许多好处:(1)直观;(2)合同的很多性质与相等类似。 性质1 a≡a。 性质2 若a≡b,则b≡a。 性质3 若a≡b,b≡c,则a≡c。 故合同是一种等价关系。 每一个等价类称为模m的一个剩余类。,合同的基本性质,性质4 若a≡b(mod m),c≡d(mod m),则ac≡bd(mod m),ac≡bd(mod m) 证明:由题设有r,s使a-b=rm,c-d=sm。 故(ac)-(bd)=(rs)m, 因而 acbd(mod m)。ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm2 bd+0+0+0(mod m)=bd(mod m),故acbd(mod m)。,合同的基本性质,性质5 若ab(mod m),则akbk (mod m)。其中k为整数。 证明:由ab(mod m),k  k(mod m)和性质4有,a+kb+k (mod m)。同理得a-kb-k (mod m)。 性质6 若a+bc(mod m),则ac-b(mod m)。 证明:由a+bc(mod m)和-b-b(mod m) 得a+b-bc-b(mod m),即 ac-b(mod m)。,合同的基本性质,性质7 若ab(mod m),则acbc(mod m)。 证明:由ab(mod m),cc(mod m)和性质4有,acbc(mod m)。 性质8 若ab(mod m),则anbn(mod m), n0。 证明:若n=0,有a0b0(mod m);一般情况下,有n个式子 ab(mod m)成立,根据性质4,有:anbn(mod m)。,例.证明:正整数n是3的倍数 iff n的各个数字之和是3的倍数。 证明:设n=ak10k+ak-110k-1+…+a110+a0 因为101(mod 3),由性质8得10i1(mod 3),由性质7得ai 10i ai (mod 3) 故由性质4得 n=ak10k+ak-110k-1+…+a110+a0  ak+ak-1+…+a1+a0 (mod 3) 因此,3|n iff n 0 (mod 3) iff ak+ak-1+…+a1+a0 0 (mod 3),合同的基本性质,这8条性质都和相等的性质相同,但对于数 的相等,我们还有消去律:若c0而ac=bc 则a=b。这对合同并不普遍成立,例如,虽 然20(mod 6),却不能从合同式 814(mod 6) 的两边消去2得出47(mod 6)。但是,下 列两个事实成立:,,合同的基本性质,性质9 若c0而acbc(mod mc),则ab(mod m)。 证明:由题设有q使ac-bc=qmc, c0,于是a-b=qm,因而ab(mod m)。 性质10 若c和m互质,则由acbc(mod m)可以推出ab(mod m)。 证明:ac  bc(mod m)表示m|(a-b)c,但c和m互质,所以由定理5.2.2,有m|(a-b),故ab(
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:5-3合同 一次同余式_ou.ppt
链接地址:https://www.weizhuannet.com/p-7352645.html
微传网是一个办公文档、学习资料下载的在线文档分享平台

微传网博客

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开