[proofplan] The congruence $ed \equiv 1 \pmod{\varphi(n)}$ says that the exponent $ed$ differs from $1$ by an integer multiple of $\varphi(n)$. We rewrite $(a^e)^d$ as $a^{ed}$, separate off one factor of $a$, and use Euler's theorem modulo $n$. Since $\gcd(a,n)=1$, Euler's theorem gives $a^{\varphi(n)} \equiv 1 \pmod n$, so every extra factor of $a^{\varphi(n)}$ disappears modulo $n$. [/proofplan] [step:Rewrite the exponent congruence as an exact integer identity] Since $ed \equiv 1 \pmod{\varphi(n)}$, there exists an integer $k \in \mathbb{Z}$ such that $ed = 1 + k\varphi(n)$. Because $e,d \in \mathbb{N}$, we have $ed \geq 1$. Since $p$ and $q$ are primes, $n=pq \geq 2$, so $\varphi(n) \geq 1$. Hence \begin{align*} k = \frac{ed-1}{\varphi(n)} \end{align*} so $k \geq 0$. Thus $k \in \mathbb{N} \cup \{0\}$. [/step] [step:Apply Euler's theorem to the unit residue class of $a$ modulo $n$] The hypothesis $\gcd(a,n)=1$ is exactly the coprimality condition required to apply [citetheorem:7888] with modulus $n$. Therefore $a^{\varphi(n)} \equiv 1 \pmod n$. Raising both sides of this congruence to the nonnegative integer power $k$ gives $\left(a^{\varphi(n)}\right)^k \equiv 1^k \pmod n$. Since $1^k=1$, we obtain $a^{k\varphi(n)} \equiv 1 \pmod n$. [guided] We now use the only number-theoretic input in the proof: Euler's theorem. The theorem [citetheorem:7888] applies to a positive modulus $n$ and an integer $a$ satisfying $\gcd(a,n)=1$. In the present theorem, $n=pq$ with $p$ and $q$ prime, so $n \in \mathbb{N}$, and the hypothesis explicitly gives $\gcd(a,n)=1$. Therefore Euler's theorem gives $a^{\varphi(n)} \equiv 1 \pmod n$. Why is this the useful congruence? The previous step showed that the exponent $ed$ is $1$ plus $k$ copies of $\varphi(n)$, so the factor $a^{k\varphi(n)}$ is the part we want to eliminate modulo $n$. Since congruences are compatible with multiplication, they are also compatible with raising to a nonnegative integer power. Applying this to the congruence $a^{\varphi(n)} \equiv 1 \pmod n$ and to the nonnegative integer $k$ gives $\left(a^{\varphi(n)}\right)^k \equiv 1^k \pmod n$. Using the exponent law $\left(a^{\varphi(n)}\right)^k = a^{k\varphi(n)}$ and the identity $1^k=1$, we conclude $a^{k\varphi(n)} \equiv 1 \pmod n$. [/guided] [/step] [step:Separate the surviving factor of $a$ and conclude the RSA congruence] Using the exponent law for integer powers and the identity $ed=1+k\varphi(n)$, we have \begin{align*} (a^e)^d = a^{ed} = a^{1+k\varphi(n)} = a\,a^{k\varphi(n)} \end{align*} From the previous step, $a^{k\varphi(n)} \equiv 1 \pmod n$. Multiplying this congruence by $a$ gives $a\,a^{k\varphi(n)} \equiv a \pmod n$. Therefore $(a^e)^d \equiv a \pmod n$. This is the desired congruence. [/step]