同余的性质 (a, op a, )mod n=[a, mod n ) op(a, mod n)] mod ms ①反身性( reflexive):a= a mod n ②对称性( symmetrIc):若a= b mod n,则b= a mod n ③传递性 (transitive): 若a= b mod n且b= c mod n,则a= cmod n ④a= b mod n→c= d mod n,则 a+c=(b+d)mod n a-c=(b-d) mod n a·C=(b·d)modn 6(a+b)mod n=(a mod n+b mod n) mod n (a-b)mod n=(a mod n -b mod n) mod n (a·b)modn=( a mod n· b mod r)modn ④如果aC= bd mod n且c= d mod n,gcd(c,n)=1 则a= b mod n证明:留给学生 例:3*2=1*2mod4且2=2mod4,但3≠1mod4 Cheer 之9cd(2,4)≠1 都 mfy@ustc.edu.cn 现代密码学理论与实践 14/55mfy@ustc.edu.cn 现代密码学理论与实践 14/55 (a1 op a2 ) mod n =[(a1 mod n )] op (a2 mod n)] mod n ①反身性(reflexive)：a=a mod n ②对称性(symmetric)：若a=b mod n，则b=a mod n ③传递性(transitive): 若a=b mod n 且b=c mod n，则a=c mod n ④ a=b mod n→ c=d mod n，则 a+c=(b+d) mod n a-c=(b-d) mod n a•c=(b•d) mod n ⑤ (a+b) mod n = (a mod n + b mod n) mod n (a-b) mod n = (a mod n - b mod n) mod n (a•b) mod n = (a mod n • b mod n) mod n ⑥如果ac=bd mod n 且 c=d mod n, gcd(c,n)=1, 则 a=b mod n 证明：留给学生 例： 3*2=1*2 mod 4 且 2=2 mod 4, 但3≠1 mod 4， ∵ gcd(2,4)≠1