数论基础（续） 网络安全 NETWORK SECURITY 定理1若ac=bd mod n且c=d mod n及(c,n)=1,则a=b mod n 证明由(a-b)c+b(c-d)=ac-bd=0modn可得n(a-b)c。因为及 (c,n)=1,故n|(a-b)。因此a=bmod n 定理2若(a,n)=1,则存在唯一整数b,0<b<n,且(b,n)=1,使得 ab=1 mod n 证明由定理1知，若(a,n)=1,且jmod n,则ai≠aj mod n。因此， 集合{ai mod n)1=0,1,,n1为集合0,1，，n-1的一个排列。因 此b为ab=1modn的唯一解。此外，因ab-1=kn,k为正数，若(b, n)=g则g|(ab-1)。因g|ab,所以gl1。因此，g=1。故b也与n互 素。 1616 数论基础（续） • 定理1 若ac=bd mod n 且c=d mod n 及 (c，n)=1，则 a=b mod n • 证明 由(a-b)c+b(c-d)=ac-bd=0 mod n 可得 n | (a-b)c。因为及 (c，n)=1，故n | (a-b)。因此a=b mod n • 定理2 若(a，n)=1，则存在唯一整数b，0<b<n，且(b，n)=1，使得 ab=1 mod n • 证明 由定理1知，若(a，n)=1，且ij mod n，则aiaj mod n。因此， 集合{ai mod n}i=0，1，…，n-1为集合{0，1，…，n-1}的一个排列。因 此b为ab=1 mod n的唯一解。此外，因ab-1=kn，k为正数，若(b， n)=g则g | (ab-1)。因g | ab，所以g|1。因此，g=1。故b也与n互 素