Proving $m$ is prime when $a^{m-1}\equiv 1\pmod m$ and factors of $m-1$ satisy $a^n\equiv r\pmod m,r\neq1$

Question

If $a^{m-1}\equiv 1\pmod m$, and all factors of $m-1$, say $n (n< m-1)$ satisfy $$a^n\equiv r\pmod m,r\neq1$$ then $m$ is a prime.

I want to prove this proposition, but it is a little difficult for me. Would anybody give me help? Thanks in advance!

Answer 1

If $\gcd(a,m) = d > 1$, then $\gcd(a^{m-1},m) \geq d > 1$ as well, so our conditions imply that $\gcd(a,m) = 1$. Now suppose $m$ is not prime, then the group $(\mathbb{Z}/m \mathbb{Z})^*$ has order $\phi(m) < m - 1$. The element $a \in (\mathbb{Z}/m \mathbb{Z})^*$ satisfies $a^{m-1} = 1$, so its order divides $m-1$. However this order also divides the group order $\phi(m)$, hence it is smaller than $m-1$. But we are given that $a^n \neq 1$ for all strict divisors $n \mid m - 1$, contradiction.

If you don't feel comfortable using group theory you could write the same proof in a more concrete way. If $m$ is composite, then there are less than $m-1$ classes $r \mod m$ with $\gcd(r,m) = 1$. So the classes $1, a, a^2, a^3, \ldots, a^{m-2} (\mod m)$ cannot all be different, say that $a^{n_1} \equiv a^{n_2} \mod m$. Then $a^{n_1 - n_2} \equiv 1 \mod m$, and by Bezout's lemma also $a^{\gcd(m-1,n_1-n_2)} \equiv 1 \mod m$. However $\gcd(m-1,n_1 - n_2) < m -1$, contradiction.