sp;不是 p 的倍数, 也不是 q 的倍数时, 

则 a^(p-1) == 1 mod p (费马小定理)  =>  a^(k(p-1)(q-1)) == 1 mod p 

a^(q-1) == 1 mod q (费马小定理)  =>  a^(k(p-1)(q-1)) == 1 mod q 

所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1  =>  pq | a^(k(p-1)(q-1)) - 1 

即 a^(k(p-1)(q-1)) == 1 mod pq 

=>  c == a^(k(p-1)(q-1)+1) == a mod pq 



2. 如果 a 是 p 的倍数, 但不是 q 的倍数时, 

则 a^(q-1) == 1 mod q (费马小定理) 

=>  a^(k(p-1)(q-1)) == 1 mod q 

=>  c == a^(k(p-1)(q-1)+1) == a mod q 

=>  q | c - a 

因 p | a 

=>  c == a^(k(p-1)(q-1)+1) == 0 mod p 

=>  p | c - a 

所以, pq | c - a  =>  c == a mod pq 



3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上 



4. 如果 a 同时是 

上一页  [1] [2] [3] [4] [5] 下一页