The above identity holds for any integer $a$. Since my solution(?) does seem neither elegant nor rigorous enough, I want to get some advice to improve it.
My solution: If $(a,m)=1$, this identity is obvious from Euler's Theorem. So, assume that $(a,m)\neq 1$.
Let $g=(a,m)$, and then $\exists k, n\in\mathbb{Z}\:s.t. (k,n)=1$, $a=gk$ and $m=gn$. So the identity can be rewritten as the following:
$$(gk)^m\equiv (gk)^{m-\phi(m)} \pmod{gn}$$ Dividing the both sides by $k$, we obtain: $$g^{m}k^{gn-1}\equiv g^{m-\phi(m)}k^{gn-\phi(gn)-1} \pmod{n}$$ $$g^{m}\equiv g^{m-\phi(m)}k^{-\phi(g)\phi(n)}\equiv g^{m-\phi(m)}\pmod{n}...(*)$$
Thus, we can reduce the identity to the identity (*), and as we continue this process for finite times, we will eventually reach at Euler's identity with $(a,m)=1$.
Hint Let $m=p_1^{\alpha_1}....p_k^{\alpha_k}$.
It suffices to prove that
$$ a^m\equiv a^{m-\phi(m)} \pmod{p_i^{\alpha_i}}$$
Now split the problem in two cases: $p_i |a$ and $p_i \nmid a$. The second case is almost identical with your first case...