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
On
Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. Two cases: $\,p_i\mid a\,\stackrel{k\ge\alpha_i}\Rightarrow\, p_i^{\alpha_i}\mid a^k\,\Rightarrow\, a^{\varphi(n)+k}\equiv a^k\equiv 0\pmod{p_i^{\alpha_i}}$
$p_i\nmid a\,\stackrel{\text{ET}}\Rightarrow\, a^{\varphi(p_i^{\alpha_i})}\equiv 1\pmod{\! p_i^{\alpha_i}}$. Raise by $\frac{\varphi(n)}{\varphi(p_i^{\alpha_i})}\in\Bbb N$: $a^{\varphi(n)}\equiv 1\pmod{\!p_i^{\alpha_i}}$. Multiply by $a^k$.
Remarks: ET - Euler's theorem. $\varphi(p_i^{\alpha_i})\mid \varphi(n)$ is because
$p_i^{\alpha_i}-p_i^{\alpha_i-1}\mid \left(p_1^{\alpha_1}-p_1^{\alpha_1-1}\right)\cdots\left(p_k^{\alpha_k}-p_k^{\alpha_k-1}\right)$
We can raise, i.e. $a\equiv b\,\Rightarrow\, a^m\equiv b^m$, because $a^m-b^m=(a-b)(a^{m-1}+\cdots+b^{m-1})$
This is what Bill Dubuque calls Congruence Power Rule (see for another proof).
$a^{\varphi(n)+k}\equiv a^k\pmod{\! p_i^{\alpha_i}}$ for arbitrary $i\in\{1,\ldots,k\}$ iff $a^{\varphi(n)+k}\equiv a^k\pmod{\! n}$
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$.