# Show that $m$ is prime if there exists $a\in\Bbb Z$ such that $a^{m-1}\equiv 1\pmod m$

The whole question is here:

Show that, if there exists $a\in\Bbb Z$ such that $a^{m-1}\equiv 1\pmod m$ and $a^k\not\equiv 1\pmod m$ for each $0<k<m-1$, then $m$ is prime.

I know the opposite way is fermat's theorem but don't how to prove in this way.

• Your title misrepresents your question. – Lord Shark the Unknown Feb 14 '18 at 6:20

If $a^{m-1}\equiv 1\pmod m$ then $a$ is an element of the multiplicative group $\Bbb Z_m^*$ since $a$ must be a unit in the ring $\Bbb Z_m$. Furthermore, the condition $a^k\not\equiv 1\pmod m$ for each $0<k<m-1$ implies that $a$ is an element of order $m-1$ in $\Bbb Z_m^*$. Since $|\Bbb Z_m^*|=\varphi (m)\leq m-1$, we must have $|\Bbb Z_m^*|=m-1$, and thus $m$ is prime.