数论基础（续） 网络安全 推论：给定两个素数p,q,两个整数n,m,使得n=pq,0me,s则对于 任意整数k,下列关系成立：mk中(n)+1三mmod 证明：分两种情况： 1)m与n互素，则由欧拉定理得 m(n)三1modn mk()三1modn mkφ(n)+1≡m mod n 2) gcd(m,n)≠1，由于n=pq,则gcd(m,n)≠1意味着m要么是p的倍数， 要么是q的倍数，不妨设m=tp,其中t为一正整数。此时，gcd(m,q)=1, 否则m也是g的倍数，从而是pq的倍数，与m<n=pq矛盾。 由gcd(m,q)=1及欧拉定理得m(q)=1modq, [mk(q)](p)=1modq,mkΦ(m)≡1modq 因此存在一整数r,使得mk(n)=1+rq,两边同乘以m=tp,得mk(n)+1 =m+rtpq=m+rtn,即mkΦ(m)+1=8modn18 数论基础（续） 推论：给定两个素数p, q , 两个整数 n, m ，使得n=pq, 0<m<n ； 则对于 任意整数k ，下列关系成立：m kф(n)+1 ≡ m mod n 证明：分两种情况： 1）m与n互素，则由欧拉定理得 mф(n) ≡1 mod n m kф(n) ≡1 mod n m kф(n)+1 ≡m mod n 2） gcd(m,n)1，由于n=pq，则gcd(m,n)1意味着m要么是p的倍数， 要么是q的倍数，不妨设m=tp，其中t为一正整数。此时，gcd(m,q)=1， 否则m也是q的倍数，从而是pq的倍数，与m<n=pq矛盾。 由gcd(m,q)=1及欧拉定理得mф(q) ≡1 mod q， [mkф(q)] ф(p)≡1 mod q， mkф(n) ≡1 mod q 因此存在一整数r，使得mkф(n) =1+rq，两边同乘以m=tp，得 mkф(n)+1 =m+rtpq=m+rtn，即m kф(n)+1 ≡m mod n