同余的性质 如果n|(a-b),则a= b mod n 证明:如果n(a-b),则有(a-b)=kn,k为某些整数, 所以a=b+kn。 故 a mod n=(b+kn)除以n的余数 =b除以n的余数 b mod n a≡ b mod n→b≡ a mod n a= b mod n和b三 cmod n→a≡ cmod n EX:23=8mod5),因为23-8=15=5X3 11=5mod8),因为-11-5=-16=8X(-2 81=0mod27),因为81-0=81=27×3 ad Can futer Science Technolog 都 mfy@ustc.edu.cn 现代密码学理论与实践 13/55mfy@ustc.edu.cn 现代密码学理论与实践 13/55  如果n|(a-b), 则a≡b mod n 证明: 如果n|(a-b), 则有(a-b)=kn, k为某些整数， 所以a=b+kn。 故a mod n = (b + kn)除以n的余数 = b 除以n的余数 = b mod n  a≡b mod n →b≡a mod n  a≡b mod n 和 b≡c mod n →a≡c mod n Ex: 23≡8(mod 5)，因为23-8=15=5x3 -11≡5(mod 8)，因为-11-5=-16=8x(-2) 81≡0(mod 27)，因为81-0=81=27x3