1. Proof an equation

How to proof that equation?
$\displaystyle a^m\equiv a^{m-\phi(m)} mod m$?
I now that if m is primes we have little fermat theorem, but what is when it is not primes. How can I proof this?

2. Originally Posted by oszust001
How to proof that equation?
$\displaystyle a^m\equiv a^{m-\phi(m)} mod m$?
I now that if m is primes we have little fermat theorem, but what is when it is not primes. How can I proof this?
I'm going to assume that $\displaystyle a$ is relatively prime to $\displaystyle m$.

So we have $\displaystyle a^{\phi(m)}\equiv1\pmod m$ by Euler's Theorem (a generalization of Fermat's Theorem). Then we can multiply both sides by $\displaystyle a^m$ to get $\displaystyle a^{\phi(m)+m}\equiv a^m\pmod m$.

Note that $\displaystyle (a^{\phi(m)},m)=1$ since $\displaystyle (a,m)=1$; therefore we can divide both sides of $\displaystyle a^{\phi(m)+m}\equiv a^m\pmod m$ by $\displaystyle a^{\phi(m)}$ to get the equivalent congruence $\displaystyle a^m\equiv a^{m-\phi(m)}\pmod m$.