# Math Help - Proof an equation

1. ## Proof an equation

How to proof that equation?
$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?
$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 $a$ is relatively prime to $m$.

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

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