# We have $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 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)?

• "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." This last bit is correct and more formal perhaps than your "last two lines". Your argument is probably the most elementary (another one being given in an answer below) – Max Mar 18 '18 at 20:41
• Gotcha, thanks! – SS' Mar 18 '18 at 20:42

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.