数论基础（续) 网络安全 NETWORK SECURI 定理3令{r1,r2,, r(n为模n的一既约剩余系，且(a,n=1,则 ari,ar2,..., ar(m}也为模n的一既约剩余系 证明设(arj,n)=g,则ga或gr。因此我们得以下两种情况。 1)gla且gln,或2)glr且g1n。 首先1)不可能，因为(a,n)=1；其次2)也不可能，因为r为模n既 约剩余系的一元素。因此(arj,n)=1。此外，ar≠ar,否则r=r。因 此{ar1,ar2,,arm}也为模n的一既约剩余系。 ● 定理4欧拉定理：若(a,n)=1,则a(o)=1modn 证明令{r1,r2,,r(m}为模n的一既约剩余系，由定理3知，若(a, n)=1,则{ar1,ar2,,ar中m)}也为模n的一既约剩余系。因此 Π1<=i<=m)(ar)modn=卫1<=i<=中n(r)modn,由消去法，可得 a(n)=1 mod n 1717 数论基础（续） • 定理3 令{r1，r2，…，rф(n)}为模n的一既约剩余系，且(a，n)=1，则 {ar1，ar2，…，arф(n)}也为模n的一既约剩余系 • 证明 设(arj，n)=g，则g|a或g|rj。因此我们得以下两种情况。 1) g|a且g|n，或 2) g|rj且g|n。 首先 1）不可能，因为(a，n)=1；其次 2）也不可能，因为rj为模n既 约剩余系的一元素。因此(arj，n)=1。此外， ariarj，否则ri=rj。因 此{ar1，ar2，…，arф(n)}也为模n的一既约剩余系。 • 定理4 欧拉定理：若(a，n)=1，则aф(n)=1 mod n • 证明 令{r1，r2，…，rф(n)}为模n的一既约剩余系，由定理3知，若(a， n)=1，则{ar1，ar2，…，arф(n)}也为模n的一既约剩余系。因此 1<=i<=ф(n) ( ari) mod n = 1<=i<=ф(n) (ri) mod n，由消去法，可得 aф(n)=1 mod n