Prove or disprove that $a^{\phi(n) + k} \equiv a^{k} \mod{n}$ 
Prove or disprove that 
$$
a^{\phi(n) + k} \equiv a^{k} \mod{n}
$$
  where $\phi(n)$ is Euler's totient function, for all positive integers $a$ and $n$, as long as $k$ is $\geq$ the multiplicity of all the primes in the factorization of $n$.

I saw the above corollary in Brilliant, so how do you prove (or disaprove) it? Because for $a^{\phi(n) + 1} \equiv a \mod{n}$, it seems to work

Without restriction on $n$ or $a$, it's not always true for small values of $k$ (but always true for "big enough" $k$).
For a counterexample, $\phi(9) = 6$ and $3^7 \not \equiv 3^1 \bmod 9$.
For $a,n$ not coprime, $k$ needs to be big enough to "saturate" the biggest shared prime factor. For any $a$ given $n$, $k\ge\alpha_{max}$ is certainly big enough, where $\alpha_{max}$ is the biggest prime exponent in the prime decomposition of $n$.
