同余式 上 handoutnew

《同余式 上 handoutnew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、同余及其基本性质中国剩余定理剩余类环..同余式(上).....课件制作：张晓磊April24,2010课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本性质中国剩余定理剩余类环..2.0同余及其基本性质.....课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本性质中国剩余定理剩余类环.定义...a,b,n2Z，且n6=0.如果n

2、(a−b)则称a与b模n同余.记为.ab(modn),.......1.同余是两个整数间的一种关系....2.同余符号是Gauss引入的....课件制作：张晓磊裴定一、徐详《信息安全

3、数学基础》同余及其基本性质中国剩余定理剩余类环.(同余是一个等价关系).....1.aa(modn)..2.如果ab(modn)，则ba(modn)...3.如果ab(modn),bc(modn)，则ac(modn).....课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本性质中国剩余定理剩余类环.定理(同余的若干性质).....1.若a1b1,a2b2(modn),则a1+a2b1+b2(modn);..2.若a1b1,a2b2(modn),则a1a2b1b2(modn);..3.若adbd(

4、modn)，且(d,n)=1,则ab(modn);..4.若ab(modn),d是a,b,n的任一公因子，则ab(modn);ddd..5.若ab(modni),i=1,2,...,k，则ab(mod[n1,n2,...,nk])，..6.若ab(modn),d

5、n,d>0，则ab(modd);...7.若ab(modn),则(a,n)=(b,n).....课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本性质中国剩余定理剩余类环.(1)...若.a1b1,a2b2(modn),则a1+a2b1+b2

6、(modn).....证明：...1.a1b1(modn))n

7、a1−b1；..2.a2b2(modn))n

8、a2−b2；..3.由上面两条，有n

9、(a1−b1)+(a2−b2)，也就是n

10、(a1+a2)−(b1+b2);...4.所以a1+a2b1+b2(modn).....课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本性质中国剩余定理剩余类环.(2)...若.a1b1,a2b2(modn),则a1a2b1b2(modn)......证明：...1.相当于要证明：n

11、a1a2−b1b2；..2.由a1b

12、1(modn)有：n

13、(a1−b1)；..3.由a2b2(modn)有：n

14、(a2−b2)；..4.a1a2−b1b2=a1a2−a1b2+a1b2−b1b2.=a1(a2−b2)+b2(a1−b1)....课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本性质中国剩余定理剩余类环.(3)...若.adbd(modn)，且(d,n)=1,则ab(modn);.....证明：...1.相当于要证明：n

15、a−b；..2.由adbd(modn))n

16、ad−bd)n

17、(a−b)d...3.由于(n,d)=1，所以n

18、a−b

19、.....课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本性质中国剩余定理剩余类环.(4)...若ab(modn),d是a,b,n的任一公因子，则abn(mod)..ddd.....证明：...1.相当于要证明：n

20、a−b；dddnab..2.由ab(modn))n

21、a−b)−.ddd....课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本性质中国剩余定理剩余类环.(5)...若ab(modni),i=1,2,...,k，则.ab(mod[n1,n2,...,nk])......证明：...1.记[

22、n1,n2,...,nk]=m，相当于要证：m

23、a−b；..2.ab(modni))ni

24、a−b..3.即a−b是ni的公倍数。...4.由最小公倍数的定义知：m

25、a−b.....课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本性质中国剩余定理剩余类环.(6)...若.ab(modn),d

26、n,d>0，则ab(modd);.....证明：...1.相当于要证明d

27、a−b；..2.ab(modn))n

28、a−b...3.d

29、n,n

30、a−b)d

31、a−b....课件制作：张晓磊裴定一、徐详《信息安全数学基础》同余及其基本

32、性质中国剩余定理剩余类环.(7)...若.ab(modn),则(a,n)=(b,n)......证明：...1.ab(modn))n

33、a−b；..2.存在t2Z使得a−b=nt；...3.即a=nt+b)(a,n)=(n,b)..