elementary number theory - We have $a^{n-1} equiv 1 (mod n)$ but $a^{m} notequiv 1 (mod n)$ for every divisor $m$ of $n - 1$, other than itself. Prove that $n$ is prime.

The integers $a$ and $n > 1$ satisfy $a^{n-1} \equiv 1\ (mod\ n)$ but $a^{m} \not\equiv 1\ (mod\ n)$ for every divisor $m$ of $n - 1$, other than itself. Prove that $n$ is prime.

The way I went about proving it was,

---

We know for every integer $k \geq 1$, $a^k \equiv 1 (mod\ n) \iff d\ \vert\ k$, where $d$ is the order of $a$.

Note $a^{n-1} \equiv 1\ (mod\ n)$ and all divisors $d\ \vert\ n - 1$ have $a^{d} \not\equiv 1\ (mod\ n)$. $\implies$ $n - 1$ is the order of $a$.

So we know $\{1, a, a^2, ..., a^{n-1}\} \subseteq residue\ class\ mod\ n$
So at least $n - 1$ elements coprime to $n \implies$ $n$ is prime

---

So assuming this proof is correct, I was wondering if anyone had a more formal justification / better explanation for the last two lines. My thought process was because we know the order of $a$ is $n-1$, all powers of $a$ are incongruent to each other and the set of incongruent $n -1$ elements forms a set of residues mod n.

And since there are $n -1$ elements less than and coprime to $n$, we get that $n$ must be prime.

Is this correct? If not, does anyone know of a better proof (using only elementary number theory techniques)?

Answer

Well, if $n-1$ is the order of $a$, then $n-1\mid \varphi(n)$. Since $\varphi(n)\leq n-1$, we know $\varphi(n)=n-1$. This means $n$ is prime.

Not necessarily a better proof, but shorter, and I'd say simpler too.