# Solution for generalized Euler's Theorem $a^m\equiv a^{m-\phi(m)} \pmod{m}$?

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}$.
$$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...