Proof that if $\gcd(a,n) = 1$ then $a^k \equiv a^{k \bmod \phi(n)} \pmod {\!n}$ From Euler's theorem I know that $a^{\phi(n)} \equiv 1 \pmod n$ if $\gcd(a,n) = 1$. However I can't find any proof/explaination of the proof in the title.
 A: Hint: Consider that the the only thing that changes from $a^k$ to $a^{k\!\pmod{\phi(n)}}$ is that the exponents differ by a multiple of $\phi(n)$.
A: The key idea is to use modular order reduction on exponents as in the Theorem below. We can find small exponents $\,e\,$ such that $\,a^{\large \color{#c00}e}\equiv 1\,$ either by Euler's totient or Fermat's little theorem (or by Carmichael's lambda generalization), along with obvious roots of $\,1\,$ such as $\,(-1)^2\equiv 1.$ 
Theorem $ \ \ $ Suppose that: $\,\ \color{#c00}{a^{\large e}\equiv\, 1}\,\pmod{\! m}\ $ and $\, e>0,\ n,k\ge 0\,$ are integers. Then
$\qquad\ \ \ \  n\equiv k\pmod{\! \color{#c00}e}\,\Longrightarrow\,a^{\large n}\equiv a^{\large k}\pmod{\!m}.\: $  The converse holds if $\:\color{#c00}e = {\rm ord}\,a,\,$ i.e.
$\qquad\ \ \ \  n\equiv k\pmod{\! \color{#c00}e}\,\Longleftarrow\,a^{\large n}\equiv a^{\large k}\pmod{\!m}\  $  and $\, a\,$ has order $\,\color{#c00}e\,$ mod $\,m$
Proof $\ $ Wlog $\,n\ge k\,$ so $\,a^{\large n-k} \color{#0a0}{a^{\large k}}\equiv \color{#0a0}{a^{\large k}}\!\iff a^{\large n-k}\equiv 1\iff n\equiv k\pmod{\!e}\,$ by this Corollary, where we cancelled $\,\color{#0a0}{a^{\large k}}\,$ using $\,a^{\large e}\equiv 1\,\Rightarrow\, a\,$ is invertible so cancellable (cf. below Remark).
Corollary $\ \ \bbox[7px,border:1px solid #c00]{\!\bmod m\!:\,\  \color{#c00}{a^{\large e}\equiv 1}\,\Rightarrow\, a^{\large n}\equiv a^{\large n\bmod \color{#c00}e}}\,\ $ by $\ n\equiv n\bmod e\,\pmod{\!\color{#c00}e}$
Remark $ $ If you are familiar with modular inverses then it is not necessary to restrict to nonnegative powers of $\,a\,$ above since $\,a^{\large e}\equiv 1,\ e> 0\,\Rightarrow\,$ $a$ is invertible by $\,a a^{\large e-1}\equiv 1\,$ so $\,a^{\large -1}\equiv a^{\large e-1}$.
