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?
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)<n-1$.
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)<n-1$ if $n$ is not prime. We conclude that $n$ has to be prime.