$a \in \mathbb{Z}$,$(a^{n-1}\equiv 1 (mod~n) $ and $\forall q|n-1$, $q$ is prime, $a^q\not\equiv 1 (mod~n)$ then $ n$ is a prime number

Question

Consider an integer $n \geq 2$ verifying: $$ \exists a \in \mathbb{Z}, (a^{n-1} \equiv 1 (\textrm{mod}\ n) \text{ and }\forall q|n-1, q\text { is prime numbre }, a^q\not\equiv 1 (\textrm{mod}\ n).$$ Show that $ n$ is a prime number.

Let $m$ be the order of $\bar{a}$ in the group of invertibles of $\mathbb{Z}/n\mathbb{Z}$. We will show that $m = n-1$. Suppose $m < n-1$. As $a^{n-1} \equiv 1 (\textrm{mod}\ n)$, $m | n-1$ and therefore there exists a prime number $q$ dividing $n-1$ such that $m | \frac{n-1}{q}$. This implies that $a^{\frac{n-1}{q}} \equiv 1 (\textrm{mod}\ n)$. According to this test. Can I conclude a contradiction with the assumptions?

Answer 1

A counterexample

Let $n=65$, then the only value of $q$ is $2$.

Let $a=8$, then $8^2\ne 1$ (mod $65$) but $8^{64}= 1$ (mod $65$).

Answer 2

This is wrong as stated, see S. Dolan’s answer.

We can correct this however, and make it into something called Pocklington’s criterion:

If $\exists a\in\mathbb{Z}$ such that $a^{n-1}\equiv 1 \mod n$ and $\forall q|n-1,$ $q$ prime, $a^{\frac{n-1}{q}}\not\equiv 1\mod n$, then $n$ is prime.

Notice that the power of $a$ is $\frac{n-1}{q}$, not $q$.

In fact, this is biconditional. I would give a proof here, but there are various sources online.