同余( congruence) 给定整数a,b及n≠0,当且仅当ab=kn时,a与b在 模n时同余,记为a= b mod n或a=nb 例:17=57:17-7=2*5; 53=711∴53-11=6*7 a≡b当且仅当 a mod n= b mod n 如果a是整数,n是正整数,定义a除以n所得之余数为 a模n。对于任意整数a,我们总可写出: a=|a/n」×n+( a mod n) 11mod7=4; 11mod7=3 如果(amodη)=( b mod n),则称整数a和b是模n同 余,表示为a= b mod n或a=nb 073=4mod23;21≡-9mod10 choat al law kuter science technologe 都 mfy@ustc.edu.cn 现代密码学理论与实践 12/55mfy@ustc.edu.cn 现代密码学理论与实践 12/55  给定整数a, b及n≠0, 当且仅当a-b=kn时，a与b 在 模n时同余，记为 a≡b mod n 或 a≡nb 例: 17≡57 ∵17-7=2*5; 53≡711 ∵53-11=6*7 a≡nb 当且仅当 a mod n = b mod n  如果a是整数，n是正整数，定义a除以n所得之余数为 a模n。对于任意整数a，我们总可写出： a =⌊a/n」× n + (a mod n) ◦ 11 mod 7 = 4; -11 mod 7 = 3  如果(a mod n)=(b mod n), 则称整数a和b是模n同 余，表示为 a≡b mod n 或 a≡nb ◦ 73 ≡ 4 mod 23； 21 ≡ -9 mod 10