最后，我們來證明，為什么用私鑰解密，一定可以正確地得到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)
原式得到證明。
（完）
