合同次同余式PPT页).ppt

《合同次同余式PPT页).ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§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、(2-(-1))引入引入一种新的记法来对3

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.1合同及其性质定义.设a,b为二整数，m是任意非0整数。若m

4、a-b，

5、则称a合同于b模m。记为：ab(modm)Note:合同为整除的另一种表示法，故整除的性质在此可用。特别地，若b=0，则a0(modm)表示的就是m

6、a。(2)若m

7、a，则-m

8、a。所以，若未指定m而一般地讨论模m合同时，总假定m是正整数。§5.3.1合同及其性质(3)设a=q1m+r1，0≤r1

9、(a-b)iffm

10、(r1-r2)，但

11、r1-r2

12、

13、(r1-r2)iffr1-r2=0。故a≡b(modm)iff以m除a和b所得的余数相同。有些书中将合同又叫做同余。合同的基本性质合同是整除的

14、又一表达方式，但这种表达有许多好处：（1）直观；（2）合同的很多性质与相等类似。性质1a≡a。性质2若a≡b,则b≡a。性质3若a≡b，b≡c，则a≡c。故合同是一种等价关系。每一个等价类称为模m的一个剩余类。合同的基本性质性质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)合同的基本性质性

15、质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)。合同的基本性质性质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

16、b0(modm);一般情况下，有n个式子ab(modm)成立，根据性质4，有：anbn(modm)。例.证明：正整数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

17、niffn0(mod3)iffak+ak-1+…+a1+a00(mod3)合同的基本性质这8条性质都和相等的性质相同，但对于数的相等，我们还有消去律

18、：若c0而ac=bc则a=b。这对合同并不普遍成立，例如，虽然20(mod6)，却不能从合同式814（mod6）的两边消去2得出47(mod6)。但是，下列两个事实成立：合同的基本性质性质9若c0而acbc(modmc)，则ab(modm)。证明：由题设有q使ac-bc=qmc，c0，于是a-b=qm，因而ab(modm)。性质10若c和m互质，则由acbc(modm)可以推出ab(modm)。证明：acbc(modm)表示m

19、(a-b)c，但c和m互质，所以由定理5.2.2，有m

20、(a-b)，故ab(modm)。例.822(mod7)，（2，7）=1，则411

21、(mod7)。合同的基本性质性质11若acbc(modm)，且（c,m）=d，则ab(modm/d)证明：由acbc(modm)知，m

22、(a-b)c，而(c,m)=d，故m/d

23、(a-b)c/d。注意到（m/d,c/d）=1，所以由定理5.2.2，m/d

24、(a-b)，即ab(modm/d)。结论：若(c,m)=d,则(c/d,m/d)=1①证明：反证法，假设(c/d,m/d)=d’不是1，即d’>1,