If there is an $a\in\mathbb{Z}$ with $a^{n-1}\equiv 1\mod n$ but $a^{\frac{n-1}p}\not\equiv 1$ for all primes $p\mid n-1$, then $n$ is a prime

Question

Let $n\in\mathbb{N}$ with $n\ge 3$ and $a\in\mathbb{Z}$ such that $$a^{n-1}\equiv1\text{ mod } n\;\;\;\wedge\;\;\;a^{\frac{n-1}{p}}\not\equiv1\text{ mod }n\;\;\;\forall p\in\mathbb{P}:p\mid n-1$$ where $\mathbb{P}$ denotes the set of prime numbers $\Rightarrow$ $n\in\mathbb{P}$.

What does all that mean? Fermat's little theorem states, that if $p\in\mathbb{P}$, then it holds for all $a\in\mathbb{Z}$ with $p\nmid a$:$$a^{p-1}\equiv 1\text{ mod }p$$ It seem's like this has something in common with the statement above. However, we only know that the congruence is fulfilled for one specific $a$ and Fermat's little theorem doesn't help in this direction.

So, how would one argue?

Answer 1

The assumption implies that $a$ is an element of order $n-1$ in the multiplicative monoid $\mathbb{Z} / n \mathbb{Z}$. (If the order of $a$ were a proper divisor $m$ of $n-1$, consider a prime $p$ dividing $(n-1)/m$, and compute $a^{(n-1)/p} = (a^{m})^{(n-1)/(mp)} \equiv 1 \pmod{n}$, against the assumption.)

Since $a$ is invertible in $\mathbb{Z} / n \mathbb{Z}$, as $a \cdot a^{n-2} \equiv 1 \pmod{n}$, it follows that $\mathbb{Z} / n \mathbb{Z}$ is a field, and thus $n$ is prime.

Answer 2

Hint: The condition says that there is an element $a$ of order $n-1$. But the order of an element is always $\le \varphi(n)$. So $\varphi(n)=n-1$, which for $n\gt 1$ implies that $n$ is prime.

Answer 3

Hint $\ $ Let $\,k =\,$ order of $\,a\,$ modulo $\,n\,$ Then $\,a^j\equiv 1\iff k\mid j,\,$ so our hypotheses become

$$\begin{eqnarray} a^{n-1}\equiv 1 &&\iff k\mid n-1\\ \\ a^{(n-1)/p}\not\equiv 1&&\iff k\nmid (n-1)/p\end{eqnarray}\quad $$

The first says that $\,k\,$ is a factor of $\,n-1\,$ and the second, being true for all primes $\,p\mid n-1,\,$ implies that $\,k\,$ is not a proper factor of $\,n-1\,$ [indeed, by unique factorization any proper factor $\,k\,$ of $\,n-1\,$ arises by deleting at least one prime factor $\,p,\,$ thus $\,k\mid (n-1)/p\ $]

Therefore $\, k = n\!-\!1.\ $ By Euler, $\ k=n\!-\!1\ |\ \phi(n)\ $ so $\ \phi(n) \ge n\!-\!1.\ $ Therefore $\:n\:$ is prime, since $\ \phi(n) \:\le\: n-\color{red}{2}\ $ for composite $\:n = ab,\ a,b > 1,\,$ since it has at least $\:\color{red}2\ $ smaller naturals that are not coprime to $\:n,\,$ namely $\,0\,$ and $\,a.$

Remark $\ $ The idea generalizes, e.g. see the Pocklington-Lehmer primality test.