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.

  • $\begingroup$ Your title misrepresents your question. $\endgroup$ – 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.

  • $\begingroup$ Can this been proved by using Euclidean algorithm? Since I have learned the “ring” things. Thank you $\endgroup$ – Zhenqing Xu Feb 15 '18 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.