最后，我们来证明，为什么用私钥解密，一定可以正确地得到m。也就是证明下面这个式子： > 　　cd ≡ m (mod n) 因为，根据加密规则 > 　　ｍe ≡ c (mod n) 于是，c可以写成下面的形式： > 　　c = me - kn 将c代入要我们要证明的那个解密规则： > 　　(me - kn)d ≡ m (mod n) 它等同于求证 > 　　med ≡ m (mod n) 由于 > 　　ed ≡ 1 (mod φ(n)) 所以 > 　　ed = hφ(n)+1 将ed代入： > 　　mhφ(n)+1 ≡ m (mod n) 接下来，分成两种情况证明上面这个式子。 （1）m与n互质。 根据欧拉定理，此时 > 　　mφ(n) ≡ 1 (mod n) 得到 > 　　(mφ(n))h × m ≡ m (mod n) 原式得到证明。 （2）m与n不是互质关系。 此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。 以 m = kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立： > 　　(kp)q-1 ≡ 1 (mod q) 进一步得到 > 　　[(kp)q-1]h(p-1) × kp ≡ kp (mod q) 即 > 　　(kp)ed ≡ kp (mod q) 将它改写成下面的等式 > 　　(kp)ed = tq + kp 这时t必然能被p整除，即 t=t'p > 　　(kp)ed = t'pq + kp 因为 m=kp，n=pq，所以 > 　　med ≡ m (mod n) 原式得到证明。 （完）