Why is RSA encryption performed in mod n, but computation of inverse in $\bmod \varphi(n)$ I am studying the principles of RSA and have come across some unintuitive statements. Lets revisit the RSA algorithm:

RSA Key Generation

Output: public key: $k_{pub} = (n,e)$ and private key: $k_{pr} = (d)$


Choose two large primes $p$ and $q$.
Compute $n$ = $pq$.
Compute $\varphi(n) = (p−1)(q−1)$.
Select the public exponent $e \in \{1,2,\ldots,\varphi(n)−1\}$ such that
$\gcd(e,\varphi(n)) = 1.$ 
Compute the private key $d$ such that
$d\cdot e \equiv 1 \bmod \varphi(n)$


Decryption:
$x=d_{kpr}(y)\equiv y^{d} \bmod n$

Encryption:
$y=e_{kpub}(x)\equiv x^{e} \bmod n$

I don't find intuitive on why we perform encryption and decryption in modulus $n$, but compute the inverse of $e$ in modulus $\varphi(n)$. Any help is appreciated.
What's relevant here is that the Carmichael totient $\lambda(n) = \operatorname{lcm}(p-1, q-1)$ is the exponent of the multiplicative group of integers modulo $n$, i.e. the smallest positive integer such that $x^{\lambda(n)} \equiv 1 \pmod n$ for all $x$.*

This means that if $ed$ is one more than an integer multiple of $\lambda(n)$, i.e. if $ed \equiv 1 \pmod{\lambda(n)}$ or, equivalently, if $ed = k\lambda(n)+1$ for some integer $k$, then $$x^{ed} = x^{k\lambda(n)+1} = (x^{\lambda(n)})^k x \equiv 1^kx = x \pmod n.$$

(Of course, the Euler totient $\varphi(n) = (p-1)(q-1)$ is itself an integer multiple of $\lambda(n)$, so $ed \equiv 1 \pmod{\varphi(n)}$ implies $ed \equiv 1 \pmod{\lambda(n)}$.)



*) To be precise, $x^{\lambda(n)} \equiv 1 \pmod n$ only holds for $x$ coprime with $n$, since if $x$ shares a prime factor with $n$, it won't be invertible modulo $n$ and no power of it can be congruent to $1$ modulo $n$.  That's why the definition of the modular multiplicative group requires the elements to be coprime to the modulus.  However, the slightly weaker congruence $x^{\lambda(n)+1} \equiv x \pmod n$ does hold for all $x$ as long as $n$ is squarefree, and that's all we really need for RSA.  Not to mention that finding a positive $x &lt; n$ that's not coprime to the modulus $n$ is literally equivalent to factoring $n$.