Why is RSA decryption the inverse of encryption? In RSA, to encrypt a message, the following formula is used:
$$c=m^e\bmod n$$
For decryption,
$$m = c^d\bmod n$$
is used. 
However, when I try to substitute the value of $c$ from the first into the second formula, I am unable to satisfy the equation, or rather unable to simplify the expression below:
$$m = (m^e\bmod n)^d\bmod n$$
What am I missing here?
RSA is based on the Carmichael function $\lambda$ (or if you prefer Euler's totient function $\varphi$):

$$x^{\lambda(n)} \equiv 1 \pmod n$$

for every integer x that is coprime to n.

From this you trivially get:

$$x^{k\lambda(n)} \equiv (x^{\lambda(n)})^k \equiv 1^k \equiv 1 \pmod n$$

and multiplying both sides with x:

$$x^{k\lambda(n)+1} \equiv x \pmod n$$

the last equation holds for all integers even if they're not co-prime to n.

We chose $e$ and $d$ such that their product is 1 modulo $\lambda(n)$ or equivalently $e \cdot d = k\lambda(n)+1$ for some $k$.

Thus $(x^e)^d \equiv x^{ed} \equiv x \mod n$ which means that encryption followed by decryption returns an integer equivalent to the plaintext. By limiting $x$ to $0 \leq x &lt; n$ you will get the original integer.



The wikipedia page for RSA lists proofs for the correctness of RSA as well.