Originally Posted by

**melese** The assumption $\displaystyle (a(a-1),m)=1$ implies both $\displaystyle (a,m)=1$ and $\displaystyle (a-1,m)=1$. So by Euler's Theorem, $\displaystyle a^{\phi(m)}\equiv1\pmod m$, i.e. $\displaystyle a^{\phi(m)}-1\equiv0\pmod m$.

Now, we can divide both sides by $\displaystyle a-1$ to get the **equivalent **congruence $\displaystyle \displaystyle\frac{a^{\phi(m)}-1}{a-1}\equiv0\pmod m$ since $\displaystyle a-1$ is relatively prime to $\displaystyle m $. (The left-hand side is an integer...)

But $\displaystyle \displaystyle\frac{a^{\phi(m)}-1}{a-1}= 1+a+a^2+\cdots+a^{\phi(m)-1}$ (Sum of geometric series). The result follows.

To **Drexel28**, it's not enough to have $\displaystyle (a-1,m)$, simply because $\displaystyle (a,m)=1$ is needed to conclude that $\displaystyle a^{\phi(m)}-1\equiv0\pmod m$.