For every positive integer $n$ and every $\alpha\in\mathbb{Z_n}$, we have $\alpha^n=\alpha^{n-\phi(n)}$
I have found this exercise in Victor Shoup's A Computational Introduction to Number Theory and Algebra ; it's exercise 2.31 on page 35. Sadly, I cannot prove it, so I would appreciate some help.
What I tried was to somehow mimick the proof of Euler's Theorem which uses the fact that multiplying all elements of $\mathbb{Z_n}^*$ by one of the elements of the same set maps precisely the entire set. I also noticed that $ n-\phi(n)$ is precisely the number of non-invertible elements of $\mathbb{Z_n}$.
Let $\phi(n) := \phi$ and also $a := \alpha$ (in order to simplify the typing of the solution).
We can rearrange the equality like this, following Bill Dubuque's advice:
$$a^{n-\phi}(a^\phi -1)=0$$
Now we want to apply Bill Dubuque's theorem from here with $m:= n$, $e:=n-\phi$, $f:=\phi$, which will solve the problem.
Noting that the condition $\phi(p_{i}^{e_i})\mid f=\phi$ is verified for all $i$ because of the multiplicity of the $\phi(\cdot)$ function, we only have to prove that $e\geq e_i,\forall i$.
For this, let $k$ be one of the $e_i$ corresponding to the prime $p:=p_i$, i.e $n=p^kn'$ and $p \nmid n'$.
We now have, following another one of Bill Dubuque's advices :), $$e = n-\phi = p^kn'- \phi(p^kn') \stackrel{\gcd(p,n')=1}{=} p^kn'-\phi(p^k)\phi(n')$$ $$= p^kn' - (p-1)p^{k-1}\phi(n')=p^{k-1}(pn'-(p-1)\phi(n'))$$
Noting that $p>(p-1)>0$ and $n'\geq \phi(n')> 0$ (the latter can be proved by using the expansion of $\phi(n)$ derived from the prime decomposition of $n$), this implies that $pn'>(p-1)\phi(n')$, so the previous paranthesis is $>0$. Since the paranthesis also has an integer value, it must be $\geq 1$, which implies $e\geq p^{k-1}$.
By induction, for $p\geq 2$ and $k-1\geq 0$, we have $p^{k-1}\geq k$, so we have proved that $e\geq k$, which completes our proof.