# If the order of a number (mod n) equals n-1 then n is prime? [duplicate]

I have trouble in understanding the last part of the sufficiency proof of Pépin´s Test (https://en.wikipedia.org/wiki/Pépin%27s_test).

"In particular, there are at least least F_{n}-1 numbers below F_{n} coprime to F_{n}, and this can happen only if F_{n} is prime".

Can anybody explain me that? Is it true that if the order of a number (mod n) equals n-1 then n is prime?

• not true for $n=561$ then $a^{n-1}\equiv 1(mod n)$ for a in $\mathbb{Z}_{n}$ May 13, 2019 at 17:30
• The term "order" applied to an element of a group may be misleading here. The quote describes $\phi(n)=n-1$ where $\phi$ is the totient function.
– robjohn
May 13, 2019 at 17:32
• The set of elements $\pmod n$ which are prime to $n$ form a group under modular multiplication. That group has size $n-1$ if and only if $n$ is prime, and in general the order of that group is $≤n-1$. If that group contains an element of order $n-1$ then the order of the group must have order at least $n-1$ so...
– lulu
May 13, 2019 at 17:34
• To stress: the order of an element $g \pmod n$ means the least positive exponent such that $g^k\equiv 1 \pmod n$. Is that the way you intended to use the term?
– lulu
May 13, 2019 at 17:36
• Yes, Lulu, I was about to write that definition. Would it be possible to explain the reasoning without using group theory? May 13, 2019 at 17:40

It is essentially saying that $$(\mathbb{Z}/n\mathbb{Z})^\times$$ is cyclic of order $$n-1$$ iff $$n$$ is prime. Which is true since if $$n$$ is not prime, then $$|(\mathbb{Z}/n\mathbb{Z})^\times|=\varphi(n).
Edit: In other words, by Euler's theorem we have the order of any element divides $$\varphi(n)$$. So, if the order of an element is $$n-1$$, we would have $$n-1|\varphi(n)$$. But $$\varphi(n) if $$n$$ is not prime. We conclude that $$n$$ has to be prime.