Show that $(M^{e})^d \equiv M$ (mod n).

Question

I need to show the following. Given $n,e \in \mathbb{Z^+}$ such that $gcd(e,\phi(n)) =1$, let $d$ be an inverse of $e$ (mod $\phi(n)$), and let $M \in \mathbb{Z}$ such that gcd($M,n$) = 1. Show that $(M^{e})^{d} \equiv M$ (mod $n$).

I am unsure what step to take to even begin.

Answer 1

Since $(M,n)=1$, Euler's Theorem gives you $M^{\phi(n)}\equiv1$(mod $n$). Since $e$ and $d$ are inverses (mod $\phi(n)$), then $ed\equiv1$(mod $\phi(n)$), which tells us $\exists k$ such that $ed=k*\phi(n)+1$. Then $$(M^e)^d\equiv M^{ed}\equiv M^{k*\phi(n)+1}$$ $$\equiv(M^{\phi(n)})^kM\equiv 1^kM\equiv M(mod\ n)$$.