# 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

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?

• You may wish to consider an Euler pseudoprime ( en.wikipedia.org/wiki/Euler_pseudoprime ) where the set $\mathbb{P} = \{2\}$ is insufficient to show $n$ is prime. Jun 13, 2014 at 17:15
• Your formulation is needlessly confusing. In you title there is, right away, "if" and "there exists", but in the first sentence after the title both are absent, and coming to "$\Rightarrow$" near the end, one suddenly realises there was some condition being formulated. Where did that condition start? Instead of "$\Rightarrow$" I would prefer just ending the first sentence (which is complete); then continue "How can one deduce from this that $n$ is prime?" Jun 15, 2014 at 9:47

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.

• What's the "order" of an elemenet $a$ of a multiplicative monoid? I assume you will answer, that it's the smallest natural number $n$ such that $a^n=1$ - but I thought that would one call the "characteristic" of $a$. But, what's the order of $M$ itself? Why is $n-1$ the order of $\mathbb{Z}/n\mathbb{Z}$ and why must the order of an element be a divisor of the order of the monoid? This seems like Lagrange's theorem, which states something similar for groups. Jun 13, 2014 at 18:22
• I would call it order in this context, keeping characteristic for the (additive!) order of unity in a ring, but maybe there are other usages. It is not difficult to show that $a^{k} = 1$ of and only if the order of $a$ divides $k$. Jun 13, 2014 at 18:37
• So, we want to show $$a^k=1\Leftrightarrow\text{ord }a\mid k$$ While the direction $(\Leftarrow)$ is easy, how would you prove the other direction? Jun 13, 2014 at 20:02
• if $a^{k} = 1$, divide $k$ with remainder by the order of $a$. The remainder $r$ is smaller than the order of $a$, and still satisfies $a^{r} = 1$, so $r$ has to be zero. Jun 13, 2014 at 20:12
• Why does it follow, that $\mathbb{Z}/n\mathbb{Z}$ is a field? It would be a field if and only if each element is invertible, but the only thing we've shown is, that this specific $a$ is invertible, right? Jun 13, 2014 at 22:21

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.

• Talking about the "order" of $a$, you mean the order of $a$ as an element of $(\mathbb{Z}/n\mathbb{Z})^\times$, right? Jun 13, 2014 at 18:37
• Yes, the smallest positive integer $e$ such that $a^e\equiv 1\pmod{n}$. Jun 13, 2014 at 19:16
• @AndréNicolas I read the proof from an article about this theorem. The author shows that $a^{\phi(n)} \equiv 1 \mod{n}$. Any idea why that is the case? We don't assume $a$ and $n$ are relatively prime, otherwise, we can just use the Euler's theorem. Sep 8, 2020 at 5:42

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.

• How do you get $n- 1| \phi(n)$? We don't assume $a$ and $n$ are relatively prime. I am just wondering how people get $a^{\phi(n)} \equiv 1 \mod{n}$. Sep 8, 2020 at 5:46
• @Smith $\,a^{n-1}\equiv 1\pmod{n}\Rightarrow\, a(a^{n-2})+b\,n = 1\,\Rightarrow\,\gcd(a,n)=1.\,$ Or, equivalently, $a$ is invertible hence coprime to the modulus. See here for a clearer presentation. Sep 8, 2020 at 6:00
• That makes sense! Thanks! Sep 8, 2020 at 15:31