Certificate of primality based on the order of a primitive root Reading my textbook, it tells me that to prove $n$ is prime, all that is necessary is to find one of its primitive roots and verify that the order of one of these primitive roots is $n-1$.
Now, why exactly does this work? It's not making much sense to me.  Also, will any primitive root work?   

If there exists a primitive root, this already means that $(\mathbb Z/n)^{\times} \cong \mathbb Z/\varphi(n)$ is cyclic, where $\varphi$ is Euler's totient function. If $\varphi(n) = n-1$, then $n$ is prime.
