数论基础 网络安全 NETWORK SECURITY a与b的最大公因数：gcd(a,b),简记为(a,b) ·gcd(20,24)=4,gcd(15,16)=1 如果gcd(a,b)=1,称a与b互素 模运算mod a=qn+r 0sr<n;q=[a/n]i [x]表示小于或等于x的最大整数 a=[a/n]n (a mod n)r=a mod n 如果(a mod n)=(b mod n),则称a与b模n同余， 记为a=bm0dn 例如，23=8mod5,8=1mod7 1313 数论基础 • a与b的最大公因数：gcd（a, b），简记为（a, b） ▪ gcd（20, 24）=4 , gcd（15, 16）=1 • 如果gcd（a, b）=1 ，称a与b 互素 • 模运算 mod a= q n +r 0≤r<n ; q=[a/n] ; [x] 表示小于或等于x的最大整数 a=[a/n]n + （a mod n） , r = a mod n 如果 （a mod n ）= （b mod n） ，则称a 与b 模n同余， 记为 a = b mod n 例如， 23 =8 mod 5 , 8 =1 mod 7