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?   

Over the complex numbers, $e^{2 \pi i / n}$ is always a primitive root of unity.  Presumably, you mean a root of unity that has order $n - 1$ in the multiplicative group $\Bbb{Z}_n^{\times}$.
The ring $\Bbb{Z}_n$ is an integral domain if and only if $n$ is prime since otherwise the factors of $n$ are zero divisors.  Every finite integral domain is a field and the multiplicative group of a finite field is cyclic.  Therefore, if $n$ is prime, $\Bbb{Z}_n$ has a root of unity of order $n - 1$.  On the other hand, if $n$ is not prime then $\Bbb{Z}_n^{\times}$ contains an element $b$ that is not invertible and so no power of a root $a$ of unity can be equal to $b$.  It follows that the order of $a$ is less than $n - 1$.
