RSA finding the inverse of the public exponent I have a very basic doubt in RSA key generation and its usage.

In RSA key generation you choose two large prime numbers of a very large order. Then you multiply them.(eq $p \cdot q = N$) Now, $\phi(N)=(p-1)(q-1)$. Now you find a number $0 &lt; e &lt; \phi(N)$ such that $e$ and $\phi(N)$ are coprime. {$e,N$} becomes your public key. Now you compute $d$(private key) such that $ed \equiv 1 \bmod{\phi(N)}$.

Now suppose you encrypt something (say $m$) with your the public key: $c=m^e\bmod{N}$. To decrypt with the private key, you do $c^d\bmod{N}$.

Now my doubt is that you found out the inverse of $e$ modulo $\phi(N)$, but when you are decrypting you are doing it in modulo $N$. How is this possible?
The answer comes from Euler's Theorem. Note: math below is done modulo $N$ unless otherwise specified and draws heavily from group theory.

That theorem says that any element of a group (say $m$) raised to the order of the group, in this case $\phi(N)$ is congruent to $1$ (i.e.,  $m^{\phi(N)}\equiv 1\bmod{N}$). Furthermore, this holds for multiples of $\phi(N)$ (i.e., $c\cdot\phi(N)$ where c is an integer).

In the case of RSA, you find $e,d$ such that $ed\equiv 1\bmod{\phi(N)}$. Note then that $ed=c\cdot\phi(N)+1$, where $c$ is some integer.

Thus $c^{d}=m^{ed}=m^{c\cdot\phi(N) + 1}=m^{c\cdot\phi(N)}\cdot m^1$. From the Euler's Theorem, $m^{c\cdot\phi(N)}=1$, so that term goes away and you are left with the original message.